<div>Hi Ted,</div><div><br></div><div>I re-implement this checker again.</div><div><br></div><div>This time i introduce several data structure to do DP and the bugreport.</div><div><ol><li>I modified the worklist a bit, now its unit is a <FunctionDecl *, CallExpr *> pair from the caller's function decl to the call expr.</li>
<li>RuntimeStack(vector of CallExpr) to simulate the call graph dynamiclly. This is for report the entire chain of the call path.</li><li>A DenseMap from a FunctionDecl to all call paths in its body.</li><li>A SmallPtrSet to Record which functions have be fully handled. A function fully handled means that all function bodies it called have been handled.</li>
</ol></div><div>I could not find a right way for this kind of bug report, it's not path diagnostic and we need to annotate the call expr in the call path. So i simply output the name with " <-- " to show the call-called relationship. It will crash on some code because "Name is not a simple identifier"? But if we use the SourceRange, there would not be any crash like this, right?</div>
<div><br></div><div>And i left several things unconsidered.</div><div><ol><li>The memory consume and reclaim.</li><li>The readabiliy of the code. It's a little hard to read now.</li></ol></div><div>Do you have any advices on these?</div>
<div><br></div><div>More comments inline, and looking forward to your reply.</div><div><br></div><div class="gmail_quote">在 2011年10月27日 下午12:20，Ted Kremenek <span dir="ltr"><<a href="mailto:kremenek@apple.com">kremenek@apple.com</a>></span>写道：<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div style="word-wrap:break-word"><div>Hi Lei,</div><div><br></div><div>This is looking good.</div><div><br></div><div>
I think one way to do DP is by modifying CheckedFunctions slightly. Instead of CheckedFunctions just recording whether or not a function has been put on the worklist, you record whether or not it calls a virtual method (perhaps by registering the callsite?). You could thus have three possibilities:</div>
<div><br></div><div>(1) Function hasn't been analyzed (if not, enqueue on the worklist)</div><div><br></div><div>(2) Function has been analyzed, and calls a virtual function.</div><div><br></div><div>(3) Function has been analyzed, and doesn't call a virtual function.</div>
<div><br></div><div>This should be easy to model with a DenseMap, mapping from the Decl* to the appropriate information. You can consult the information for 1-3 before deciding the "recurse" into analyzing a called method.</div>
<div><br></div><div>As for propagating the information via dynamic programming, since your worklist is a stack, you know the immediate caller. Once you see that a virtual method is called, essentially that means the entire chain of calls results in the call of a virtual method. You can then annotate them all in one swoop. This is essentially what you are assuming when you emit a warning.</div>
<br><div><div><div></div><div class="h5"><div>On Oct 25, 2011, at 11:50 PM, 章磊 wrote:</div><br></div></div><blockquote type="cite"><div><div></div><div class="h5"><div>Hi Ted,</div>
<div> </div>
<div>I re-implement this check as a static analyzer checker, and i make the recursion a work list as you suggested.</div>
<div> </div>
<div>Currently I'm not using dynamic programming but introduced a SmallPtrSet to avoid analyzing the same methods again. It's a top-down analysis, how could i introduce dynamic programming? By adjust the work list? It seems that if we introduce DP we still need a set to record those method we have analyzed.</div>
<div> </div>
<div>What you Say?</div>
<div> </div>
<div>2011/10/4, Ted Kremenek <<a href="mailto:kremenek@apple.com" target="_blank">kremenek@apple.com</a>>:</div>
<div>> Hi Lei,</div>
<div>></div>
<div>> The part that scares me is the recursive walk of the callee's body. That's</div>
<div>> not likely to have good enough performance for a compile-time warning. For</div>
<div>> a compile-time warning, I think it is fine to just check the body of the</div>
<div>> constructor, but if you want to analyze the bodies of called functions you'd</div>
<div>> need to be extremely clever to do it efficiently enough for it to be a</div>
<div>> compile-time warning. We really like compiler warnings to have highly</div>
<div>> predictable performance, and recursively walking the entire classes's method</div>
<div>> bodies is not really amendable to that.</div>
<div>></div>
<div>> If you think walking through all the bodies is necessary, then I'd leave it</div>
<div>> as a static analyzer checker. You'd certainly get better coverage. To</div>
<div>> handle the recursion, I'd probably make it a worklist (i.e., data recursive)</div>
<div>> to avoid stack blowup and to keep your memory footprint small. You should</div>
<div>> also employ dynamic programming to avoid analyzing the same methods again.</div>
<div>> The other nice thing about this approach is that it probably can be nicely</div>
<div>> generalized to global IPA once we have it.</div>
<div>></div>
<div>> One caveat about doing a recursive analysis of method bodies without any</div>
<div>> path-based analysis is that you are introducing additional risk of a false</div>
<div>> positive. There could be unreachable paths where a constructor can't</div>
<div>> actually transitively trigger a call to a virtual function because of the</div>
<div>> context, but your check may report an issue. I don't think this will</div>
<div>> typically be a problem, but it is something to consider.</div>
<div>></div>
<div>> Cheers,</div>
<div>> Ted</div>
<div>></div>
<div>> On Sep 27, 2011, at 1:39 AM, 章磊 wrote:</div>
<div>></div>
<div>>> Hi Ted,</div>
<div>>></div>
<div>>> My goal is to check whether there is a virtual call (directly or</div>
<div>>> indirectly) in construction or destruction.</div>
<div>>></div>
<div>>> In my former patch i do this check to all the constructors and the</div>
<div>>> destructor in checkASTDecl(const CXXRecordDecl ...). My way is walk</div>
<div>>> through the ast body of ctor/dtor: if there is virtual call, warn it; if</div>
<div>>> there is a call, walk through the callee's body recursively.</div>
<div>>></div>
<div>>> I think it's ok to do this check without the analysis engine and the</div>
<div>>> inline IPA.</div>
<div>>></div>
<div>>> What you say?</div>
<div>>> 在 2011年9月26日 下午9:37，Ted Kremenek <<a href="mailto:kremenek@apple.com" target="_blank">kremenek@apple.com</a>>写道：</div>
<div>>> On Sep 25, 2011, at 2:32 AM, 章磊 wrote:</div>
<div>>></div>
<div>>>> Hi Ted,</div>
<div>>>></div>
<div>>>> I tried to implement this as a compiler warning. But i had some</div>
<div>>>> problem in how to get the body of the ctor or dtor.</div>
<div>>>></div>
<div>>>> I implemented this in Sema::CheckConstructor and</div>
<div>>>> Sema::CheckDestructor, but i can not get the body of them when there</div>
<div>>>> is no body with the declaration yet.</div>
<div>>></div>
<div>>> The idea how I thought this would be implemented was to do the analysis</div>
<div>>> when processing CallExprs as we are building them. We should know up</div>
<div>>> front when we are about to process a constructor body. Simply set/clear a</div>
<div>>> Sema flag when processing the constructor body, and your check can consult</div>
<div>>> that flag when processing a CallExpr to see if it needs to do the check.</div>
<div>>> Alternatively, checking the DeclContext may be all that is needed to see</div>
<div>>> if we are currently in a constructor body.</div>
<div>>></div>
<div>>> The advantage of this approach is that it keeps all the checking local.</div>
<div>>> Walking the AST of a constructor body *after* we have constructed it is</div>
<div>>> slow, and not really a great approach for doing compiler warnings in the</div>
<div>>> frontend (if we can at all help it).</div>
<div>>></div>
<div>>>> And i also need the function body</div>
<div>>>> of the CallExpr in the ctor/dtor to do recursive analysis.</div>
<div>>></div>
<div>>> Interesting. If your goal is to do inter procedural analysis, then this</div>
<div>>> should remain a static analyzer check, or that should be a case caught</div>
<div>>> beyond what a compiler warning should do. That wasn't clear to me before</div>
<div>>> that this was something you wanted to do.</div>
<div>>></div>
<div>>> The tradeoffs between compiler and static analyzer warnings are fairly</div>
<div>>> simple:</div>
<div>>></div>
<div>>> 1) Compiler warnings have higher visibility because all users see them all</div>
<div>>> the time when building their code.</div>
<div>>></div>
<div>>> 2) The logic behind compiler warnings must be as fast as possible.</div>
<div>>> Inter-procedural analysis is usually a show stopper, and ideally the</div>
<div>>> checks are highly local. Sema is already "walking" all of the code as it</div>
<div>>> builds the AST, so often the warning logic can be put in key places,</div>
<div>>> essentially where the warning would be issued.</div>
<div>>></div>
<div>>></div>
<div>>></div>
<div>>></div>
<div>>></div>
<div>>> --</div>
<div>>> Best regards!</div>
<div>>></div>
<div>>> Lei Zhang</div>
<div>></div>
<div>></div>
<div> </div>
<div> </div>
<div>-- </div>
<div>Best regards!</div>
<div> </div>
<div>Lei Zhang</div>
<div> </div>
</div></div><span><VirtualCallinCtorOrDtor.patch></span></blockquote></div><br></div></blockquote></div><br><br clear="all"><div><br></div>-- <br>Best regards!<br><br>Lei Zhang<br>