<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><div>On Nov 11, 2011, at 12:56 AM, ียภฺ wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><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></span></blockquote><div><br></div><div>Hi Lei,</div><div><br></div><div>Thanks for continuing to refine the checker. I'll make specific comments inline on the patch below.</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><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.</div></span></blockquote><div><br></div><div>Ironically, the kind of report you are looking for is something that Clang's primary diagnostic system handles well, but the static analyzer's diagnostics does not. Since this is not a path-sensitive analysis, what essentially you want is a call-tree, represented with a single diagnostic and a collection of "notes". This is how diagnostics are done in Clang's warnings, but we don't have support for notes in the analyzer diagnostics.</div><div><br></div><div>For now, I think constructing a painfully long diagnostic is acceptable, but the long term solution is to enhance analyzer diagnostics to support notes as well.</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><div> 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></span></blockquote><div><br></div><div>No, unfortunately, this isn't acceptable, and using a SourceRange doesn't change the situation. There are plenty of times where the name of a method won't be a simple identifier, especially in C++. Fortunately, you can just use 'getNameAsString()' instead, and it won't crash.</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><div><br></div><div>And i left several things unconsidered.</div><div><ol><li>The memory consume and reclaim.</li></ol></div></span></blockquote><div>The checker cannot leak memory, so we need to address this (if necessary). It looks to me like there aren't any issues, however. Nothing looks dynamically allocated using the 'new' operator, and the WalkAST object has finite lifetime, so I think everything will get automatically memory managed.</div><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><div><ol start="2"><li>The readabiliy of the code. It's a little hard to read now.</li></ol></div></span></blockquote><div>The code can definitely benefit from a bit more refactoring. For example, error reporting is duplicating in multiple places.</div><div><br></div><div>What I'd also like to see is some comments in the 'Execute' method that actually describes the algorithm. I think that's the main missing piece.</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><div>Do you have any advices on these?</div></span><br class="Apple-interchange-newline"></blockquote></div><br><div><br></div><div>More comments inline in the patch:</div><div><br></div><div><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">--- lib/StaticAnalyzer/Checkers/VirtualCallChecker.cpp<span class="Apple-tab-span" style="white-space:pre"> </span>(revision 0)</font></div><div><font class="Apple-style-span" color="#000000">+++ lib/StaticAnalyzer/Checkers/VirtualCallChecker.cpp<span class="Apple-tab-span" style="white-space:pre"> </span>(revision 0)</font></div><div><font class="Apple-style-span" color="#000000">@@ -0,0 +1,334 @@</font></div><div><font class="Apple-style-span" color="#000000">+//=======- VirtualCallChecker.cpp - Basic security checks --------*- C++ -*-==//</font></div><div><font class="Apple-style-span" color="#000000">+//</font></div><div><font class="Apple-style-span" color="#000000">+// The LLVM Compiler Infrastructure</font></div><div><font class="Apple-style-span" color="#000000">+//</font></div><div><font class="Apple-style-span" color="#000000">+// This file is distributed under the University of Illinois Open Source</font></div><div><font class="Apple-style-span" color="#000000">+// License. See LICENSE.TXT for details.</font></div><div><font class="Apple-style-span" color="#000000">+//</font></div><div><font class="Apple-style-span" color="#000000">+//===----------------------------------------------------------------------===//</font></div><div><font class="Apple-style-span" color="#000000">+//</font></div><div><font class="Apple-style-span" color="#000000">+// This file defines a checker that checks virtual function calls during </font></div><div><font class="Apple-style-span" color="#000000">+// construction or destruction.</font></div><div><font class="Apple-style-span" color="#000000">+//</font></div><div><font class="Apple-style-span" color="#000000">+//===----------------------------------------------------------------------===//</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+#include "ClangSACheckers.h"</font></div><div><font class="Apple-style-span" color="#000000">+#include "clang/StaticAnalyzer/Core/Checker.h"</font></div><div><font class="Apple-style-span" color="#000000">+#include "clang/AST/DeclCXX.h"</font></div><div><font class="Apple-style-span" color="#000000">+#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"</font></div><div><font class="Apple-style-span" color="#000000">+#include "clang/AST/StmtVisitor.h"</font></div><div><font class="Apple-style-span" color="#000000">+#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+using namespace clang;</font></div><div><font class="Apple-style-span" color="#000000">+using namespace ento;</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+namespace {</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+class WalkAST : public StmtVisitor<WalkAST> {</font></div><div><font class="Apple-style-span" color="#000000">+ BugReporter &BR;</font></div><div><font class="Apple-style-span" color="#000000">+ AnalysisDeclContext *AC;</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // WorkList using stack.</font></div><div><font class="Apple-style-span" color="#000000">+ typedef std::pair<const FunctionDecl *, const CallExpr *> TyWorkListUnit;</font></div><div><font class="Apple-style-span" color="#000000">+ SmallVector<TyWorkListUnit, 20> Stack;</font></div></blockquote><div><br></div><div>I typically prefer 'WorkListUnitTy' as opposed to 'TyWorkListUnit'. Similarly, I expected the Stack type to also be typedef'ed, e.g.:</div><div><br></div><div>typedef SmallVector<WorkListUnitTy, 20> WorkListTy;</div><div>WorkListTy WorkList;</div><div><br></div><div>OR</div><div><br></div><div>typedef std::pair<const FunctionDecl *, const CallExpr *> WorkListUnit;</div><div>typedef SmallVector<WorkListUnit, 20> WorkList;</div><div>WorkList WList;</div><div><br></div><div>This keeps the type names cleaner and the name of the worklist object succinct.</div><div><br></div><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // Runtime Stack to record call path.</font></div><div><font class="Apple-style-span" color="#000000">+ SmallVector<const CallExpr *, 20> RuntimeStack;</font></div></blockquote><div><br></div><div>Also, consider using a typedef, which ties in with my next comment. For example:</div><div><br></div><div>typedef SmallVector<const CallExpr *, 20> CallChain;</div><div><div>typedef SmallVectorImpl<const CallExpr *> CallChainImpl;</div></div><div>CallChain RuntimeStack;</div><div><br></div><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // DenseMap from FunctionDecl* to all call paths in its body.</font></div><div><font class="Apple-style-span" color="#000000">+ llvm::DenseMap<const FunctionDecl *,</font></div><div><font class="Apple-style-span" color="#000000">+ SmallVector<SmallVector<const CallExpr *,20>,</font></div><div><font class="Apple-style-span" color="#000000">+ 20> > VirtualCallsMap;</font></div></blockquote><div><br></div><div>This is going to result with unnecessary malloc traffic, as any time the DenseMap gets resized all of the SmallVectors will get copied and destroyed. Instead, try:</div><div><br></div><div><div> typedef llvm::DenseMap<const FunctionDecl *, CallChainImpl *> CallsMap;</div></div><div> CallsMap VirtualCallsMap;</div><div><br></div><div>This will require dynamically allocating CallChain objects, which will need to be manually destroyed, but this will be way more efficient.</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ // Current working FunctionDecl.</font></div><div><font class="Apple-style-span" color="#000000">+ const FunctionDecl *Current;</font></div></blockquote><br></div><div>Why is this state even needed?</div><div><br></div><div><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // Record which functions have be fully handled. A function fully handled </font></div><div><font class="Apple-style-span" color="#000000">+ // means that all function bodies it called have been handled.</font></div><div><font class="Apple-style-span" color="#000000">+ llvm::SmallPtrSet<const FunctionDecl *, 256> CheckedFunctions;</font></div><div><font class="Apple-style-span" color="#000000">+</font></div></blockquote><div><br></div><div>'256' isn't really "small" anymore. Not sure if this is an actual performance issue, but I'd use a DenseSet instead. Try:</div><div><br></div><div> llvm::DenseSet<const FunctionDecl *> CheckedFunctions;</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+public:</font></div><div><font class="Apple-style-span" color="#000000">+ WalkAST(BugReporter &br, AnalysisDeclContext *ac) : BR(br), AC(ac) {</font></div><div><font class="Apple-style-span" color="#000000">+ Current = NULL;</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div></blockquote><div><br></div><div>'Current' can be initialized to NULL in the initializer list as well.</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ bool hasWork() const {</font></div><div><font class="Apple-style-span" color="#000000">+ return !Stack.empty();</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div></blockquote><div><br></div><div>Looks fine.</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ void push(TyWorkListUnit WLUnit) {</font></div><div><font class="Apple-style-span" color="#000000">+ Stack.push_back(WLUnit);</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div></blockquote><div><br></div><div> void push(WorkListUnit WLUnit)</div><div><br></div><div>is much cleaner.</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ TyWorkListUnit pop() {</font></div><div><font class="Apple-style-span" color="#000000">+ assert (!Stack.empty());</font></div><div><font class="Apple-style-span" color="#000000">+ TyWorkListUnit WLUnit = Stack.back();</font></div><div><font class="Apple-style-span" color="#000000">+ Stack.pop_back();</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ return WLUnit;</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div></blockquote><div><br></div><div>I'd rename this to 'pop_back()'. 'pop()' in most data structures just pops the element without actually returning it.</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ void Execute() {</font></div></blockquote><div><br></div><div>Please add a big comment here, explaining what this method does.</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ while (hasWork()) {</font></div><div><font class="Apple-style-span" color="#000000">+ TyWorkListUnit WLUnit = pop();</font></div><div><font class="Apple-style-span" color="#000000">+ const FunctionDecl *FD = WLUnit.second->getDirectCallee();</font></div><div><font class="Apple-style-span" color="#000000">+ assert(FD && FD->getBody());</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // Pop the RuntimeStack top, until the top is caller of current WLUnit.</font></div><div><font class="Apple-style-span" color="#000000">+ while (!RuntimeStack.empty()) {</font></div><div><font class="Apple-style-span" color="#000000">+ // get the top of runtime stack</font></div></blockquote><div><br></div><div>Minor: please keep the comment style consistent. Start with a capital letter, and end with a '.'</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ const CallExpr *Top = RuntimeStack.back();</font></div><div><font class="Apple-style-span" color="#000000">+ if (WLUnit.first == Top->getDirectCallee())</font></div><div><font class="Apple-style-span" color="#000000">+ break;</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ // When we pop_back a CallExpr from the RuntimeStack, its body has been</font></div><div><font class="Apple-style-span" color="#000000">+ // fully checked.</font></div><div><font class="Apple-style-span" color="#000000">+ CheckedFunctions.insert(Top->getDirectCallee());</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ RuntimeStack.pop_back();</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+ // After we find where is the top of the RuntimeStack, push the CallExpr</font></div><div><font class="Apple-style-span" color="#000000">+ // into RuntimeStack.</font></div><div><font class="Apple-style-span" color="#000000">+ RuntimeStack.push_back(WLUnit.second);</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ // set Current to FD.</font></div></blockquote><div><br></div>Minor: please keep the comment style consistent. Start with a capital letter, and end with a '.'</div><div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ Current = FD;</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // Visit the body.</font></div><div><font class="Apple-style-span" color="#000000">+ Visit(FD->getBody());</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // TODO: cleanup the RuntimeStack.</font></div><div><font class="Apple-style-span" color="#000000">+ RuntimeStack.clear();</font></div></blockquote><div><br></div><div>I don't know what this TODO implies. Can you clarify? I think if the worklist empties out, and as long as RuntimeStack doesn't contain anything that its destructor can't automatically cleanup, there is nothing to worry about.</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // Stmt visitor methods.</font></div><div><font class="Apple-style-span" color="#000000">+ void VisitCallExpr(CallExpr *CE);</font></div><div><font class="Apple-style-span" color="#000000">+ void VisitCXXMemberCallExpr(CallExpr *CE);</font></div><div><font class="Apple-style-span" color="#000000">+ void VisitStmt(Stmt *S) { VisitChildren(S); }</font></div><div><font class="Apple-style-span" color="#000000">+ void VisitChildren(Stmt *S);</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ void VisitCXXConstructorDecl(CXXConstructorDecl *Ctor) {</font></div><div><font class="Apple-style-span" color="#000000">+ if (Ctor && Ctor->getBody()) {</font></div><div><font class="Apple-style-span" color="#000000">+ Current = Ctor;</font></div><div><font class="Apple-style-span" color="#000000">+ Visit(Ctor->getBody());</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ // After visit the body of the CXXConstructorDecl, execute the worklist.</font></div><div><font class="Apple-style-span" color="#000000">+ Execute();</font></div></blockquote><div><br></div><div>Why do we need to recursively call 'Execute'? Won't we already be processing the worklist?</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ void VisitCXXDestructorDecl(CXXDestructorDecl *Dtor) {</font></div><div><font class="Apple-style-span" color="#000000">+ if (Dtor && Dtor->getBody()){</font></div><div><font class="Apple-style-span" color="#000000">+ Current = Dtor;</font></div><div><font class="Apple-style-span" color="#000000">+ Visit(Dtor->getBody());</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ // After visit the body of the CXXDestructorDecl, execute the worklist.</font></div><div><font class="Apple-style-span" color="#000000">+ Execute();</font></div></blockquote><div><br></div>Why do we need to recursively call 'Execute'? Won't we already be processing the worklist?</div><div><br></div><div><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ void ReportVirtualCall(const CallExpr *CE, llvm::raw_svector_ostream &os);</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+};</font></div><div><font class="Apple-style-span" color="#000000">+} // end anonymous namespace</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+//===----------------------------------------------------------------------===//</font></div><div><font class="Apple-style-span" color="#000000">+// AST walking.</font></div><div><font class="Apple-style-span" color="#000000">+//===----------------------------------------------------------------------===//</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+void WalkAST::VisitChildren(Stmt *S) {</font></div><div><font class="Apple-style-span" color="#000000">+ for (Stmt::child_iterator I = S->child_begin(), E = S->child_end(); I!=E; ++I)</font></div><div><font class="Apple-style-span" color="#000000">+ if (Stmt *child = *I)</font></div><div><font class="Apple-style-span" color="#000000">+ Visit(child);</font></div><div><font class="Apple-style-span" color="#000000">+}</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+void WalkAST::VisitCallExpr(CallExpr *CE) {</font></div><div><font class="Apple-style-span" color="#000000">+ VisitChildren(CE);</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ // Get the callee.</font></div><div><font class="Apple-style-span" color="#000000">+ const FunctionDecl *FD = CE->getDirectCallee();</font></div><div><font class="Apple-style-span" color="#000000">+ if (!FD)</font></div><div><font class="Apple-style-span" color="#000000">+ return;</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ // If FD is already fully checked, no need to push the body into worklist</font></div><div><font class="Apple-style-span" color="#000000">+ // again.</font></div><div><font class="Apple-style-span" color="#000000">+ if (CheckedFunctions.count(FD)) {</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ // get the runtime stack depth.</font></div></blockquote><div><br></div><div>Minor: please keep the comment style consistent. Start with a capital letter, and end with a '.'</div><div><br></div><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ unsigned StackDepth = RuntimeStack.size();</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ // If there are virtual calls in the body of FD, we need to generate new</font></div><div><font class="Apple-style-span" color="#000000">+ // bug reports. Otherwise we will do nothing.</font></div><div><font class="Apple-style-span" color="#000000">+ if (VirtualCallsMap.count(FD)) {</font></div><div><font class="Apple-style-span" color="#000000">+ for (unsigned i = 0; i < VirtualCallsMap[FD].size(); i++) {</font></div></blockquote><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // Update virtual call paths of current function.</font></div><div><font class="Apple-style-span" color="#000000">+ VirtualCallsMap[Current].push_back(VirtualCallsMap[FD][i]);</font></div><div><font class="Apple-style-span" color="#000000">+ VirtualCallsMap[Current][VirtualCallsMap[Current].size()-1].</font></div><div><font class="Apple-style-span" color="#000000">+ push_back(CE);</font></div></blockquote><div><br></div><div><br></div><div>This is a bit gross and really inefficient. Please hoist the VirtualCallsMap[FD].size() out of the loop, or better yet, do a find for the entry so you don't lazily create entries that don't need to exist (you avoid this with the call to 'count', but this double lookup is a bit wasteful). This is a bunch of hashtable lookups to the same entry, when is really inefficient. Consider:</div><div><br></div><div> // If there are virtual calls in the body of FD, we need to generate new</div><div> // bug reports. Otherwise we will do nothing.</div><div> CallsMap::iterator I = VirtualCallsMap.find(FD);</div><div> if (I == VirtualCallsMap.end())</div><div> return;</div><div><br></div><div> assert(I->second);</div><div> CallChainImpl &Chain = *I->second;</div><div><br></div><div> for (Chain::iterator it = Chain.begin(), et = Chain.end(); it != et; ++it) {</div><div> // Update virtual call paths of current function.</div><div> CallChainImpl *&CurrentChain = VirtualCallsMap[Current];</div><div> if (!CurrentChain)</div><div> <span class="Apple-tab-span" style="white-space:pre"> </span>CurrentChain = new CallChain();</div><div> CurrentChain->push_back(*it);</div><div> CurrentChain->back().push_back(CE);</div><div><br></div><div>This is much more efficient.</div><div><br></div><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ // Generate the call path string for bug report.</font></div><div><font class="Apple-style-span" color="#000000">+ llvm::SmallString<100> buf;</font></div><div><font class="Apple-style-span" color="#000000">+ llvm::raw_svector_ostream os(buf);</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ os << "\n" << VirtualCallsMap[FD][i][0]->getDirectCallee()->getName();</font></div><div><font class="Apple-style-span" color="#000000">+ for (unsigned j = 1; j < VirtualCallsMap[FD][i].size(); i++)</font></div><div><font class="Apple-style-span" color="#000000">+ os << " <-- "</font></div><div><font class="Apple-style-span" color="#000000">+ << VirtualCallsMap[FD][i][j]->getDirectCallee()->getName();</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ os << " <-- " << CE->getDirectCallee()->getName();</font></div><div><font class="Apple-style-span" color="#000000">+ for (unsigned k = 1; k <= StackDepth; k++)</font></div><div><font class="Apple-style-span" color="#000000">+ // R[i] = RuntimeStack[StackDepth-i]->getCallee()->getSourceRange();</font></div><div><font class="Apple-style-span" color="#000000">+ os << " <-- " </font></div><div><font class="Apple-style-span" color="#000000">+ << RuntimeStack[StackDepth-k]->getDirectCallee()->getName();</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ os << "\n" ;</font></div></blockquote><div><br></div><div>This string generation logic looks identical to the logic in VisitCXXMemberCallExpr. Why can't this just be refactored into ReportVirtualCall, or into a separate method which generates the string in the SmallString which we then just pass to ReportVirtualCall as a StringRef? We shouldn't be copy-pasting string generation logic, as it means if we change it we need to change it in multiple places.</div><div><br></div><div>There is also a ton of redundant lookups to VirtualCallsMap. Those aren't free. While strictly speaking not a performance issue here (since it occurs when generating a bug report), we generally like to enforce the same kind of good performance conventions everywhere in the codebase to encourage best practice. Please clean it up using the same kind of tricks I used just above.</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ ReportVirtualCall(VirtualCallsMap[FD][i][0], os);</font></div></blockquote><div><br></div><div>No need to do yet another lookup to VirtualCallsMap[FD]. We already have the CurrentChain object.</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ return;</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ if (FD->getBody()) </font></div><div><font class="Apple-style-span" color="#000000">+ push(std::make_pair(Current, CE));</font></div></blockquote><div><br></div><div>Looks good.</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+}</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+void WalkAST::VisitCXXMemberCallExpr(CallExpr *CE) {</font></div><div><font class="Apple-style-span" color="#000000">+ VisitChildren(CE);</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // If there is a qualifier to this CallExpr, return.</font></div><div><font class="Apple-style-span" color="#000000">+ if (MemberExpr *CME = dyn_cast<MemberExpr>(CE->getCallee())) {</font></div><div><font class="Apple-style-span" color="#000000">+ if (CME->getQualifier())</font></div><div><font class="Apple-style-span" color="#000000">+ return;</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // Get the callee.</font></div><div><font class="Apple-style-span" color="#000000">+ const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(CE->getDirectCallee());</font></div><div><font class="Apple-style-span" color="#000000">+ if (!MD)</font></div><div><font class="Apple-style-span" color="#000000">+ return;</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ // get the runtime stack depth.</font></div><div><font class="Apple-style-span" color="#000000">+ unsigned StackDepth = RuntimeStack.size();</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ if (MD->isVirtual()) {</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ VirtualCallsMap[Current].</font></div><div><font class="Apple-style-span" color="#000000">+ push_back(llvm::SmallVector<const CallExpr *, 20>(1, CE));</font></div></blockquote><div><br></div><div>Do not create container objects in this way. This implicitly results in a temporary object getting created, and then copied. Instead:</div><div><br></div><div> CallChainImpl *Chain = new CallChain()l</div><div> Chain->push_back(CE);</div><div> VirtualCallsMap[Current] = Chain;</div><div><br></div><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ llvm::SmallString<100> buf;</font></div><div><font class="Apple-style-span" color="#000000">+ llvm::raw_svector_ostream os(buf);</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ os << "\n" << CE->getDirectCallee()->getName();</font></div><div><font class="Apple-style-span" color="#000000">+ for (unsigned i = 1; i <= StackDepth; i++) </font></div><div><font class="Apple-style-span" color="#000000">+ // R[i] = RuntimeStack[StackDepth-i]->getCallee()->getSourceRange();</font></div><div><font class="Apple-style-span" color="#000000">+ os << " <-- " << RuntimeStack[StackDepth-i]->getDirectCallee()->getName();</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ os << "\n" ;</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ ReportVirtualCall(CE, os);</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // Do not check the body.</font></div><div><font class="Apple-style-span" color="#000000">+ return;</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // If the MethodDecl is already fully checked, no need to push the body into </font></div><div><font class="Apple-style-span" color="#000000">+ // worklist again.</font></div><div><font class="Apple-style-span" color="#000000">+ if (CheckedFunctions.count(MD)) {</font></div><div><font class="Apple-style-span" color="#000000">+ // If there are virtual calls in the body of the MethodDecl, we need to </font></div><div><font class="Apple-style-span" color="#000000">+ // generate new bug reports. Otherwise we should do nothing.</font></div><div><font class="Apple-style-span" color="#000000">+ if (VirtualCallsMap.count(MD)) {</font></div><div><font class="Apple-style-span" color="#000000">+ for (unsigned i = 0; i < VirtualCallsMap[MD].size(); i++) {</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ VirtualCallsMap[Current].push_back(VirtualCallsMap[MD][i]);</font></div><div><font class="Apple-style-span" color="#000000">+ VirtualCallsMap[Current][VirtualCallsMap[Current].size()-1].</font></div><div><font class="Apple-style-span" color="#000000">+ push_back(CE);</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ llvm::SmallString<100> buf;</font></div><div><font class="Apple-style-span" color="#000000">+ llvm::raw_svector_ostream os(buf);</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ os << "\n" << VirtualCallsMap[MD][i][0]->getDirectCallee()->getName();</font></div><div><font class="Apple-style-span" color="#000000">+ for (unsigned j = 1; j < VirtualCallsMap[MD][i].size(); i++)</font></div><div><font class="Apple-style-span" color="#000000">+ os << " <-- "</font></div><div><font class="Apple-style-span" color="#000000">+ << VirtualCallsMap[MD][i][j]->getDirectCallee()->getName();</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ os << " <-- " << CE->getDirectCallee()->getName();</font></div><div><font class="Apple-style-span" color="#000000">+ for (unsigned k = 1; k <= StackDepth; k++)</font></div><div><font class="Apple-style-span" color="#000000">+ // R[i] = RuntimeStack[StackDepth-i]->getCallee()->getSourceRange();</font></div><div><font class="Apple-style-span" color="#000000">+ os << " <-- " </font></div><div><font class="Apple-style-span" color="#000000">+ << RuntimeStack[StackDepth-k]->getDirectCallee()->getName();</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ os << "\n" ;</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ ReportVirtualCall(VirtualCallsMap[MD][i][0], os);</font></div></blockquote><div><br></div><div>This logic is practically identical to the logic in VisitCallExpr(). This can be completely refactored to much simpler and avoid the duplication.</div><br><blockquote type="cite"><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ return;</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // Push the body into the worklist.</font></div><div><font class="Apple-style-span" color="#000000">+ if (MD->getBody())</font></div><div><font class="Apple-style-span" color="#000000">+ push(std::make_pair(Current, CE));</font></div><div><font class="Apple-style-span" color="#000000">+}</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+void WalkAST::ReportVirtualCall(const CallExpr *CE,</font></div><div><font class="Apple-style-span" color="#000000">+ llvm::raw_svector_ostream &os) {</font></div><div><font class="Apple-style-span" color="#000000">+ PathDiagnosticLocation CELoc =</font></div><div><font class="Apple-style-span" color="#000000">+ PathDiagnosticLocation::createBegin(CE, BR.getSourceManager(), AC);</font></div><div><font class="Apple-style-span" color="#000000">+ SourceRange R = CE->getCallee()->getSourceRange();</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ // Get the callee.</font></div><div><font class="Apple-style-span" color="#000000">+ const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(CE->getDirectCallee());</font></div><div><font class="Apple-style-span" color="#000000">+ </font></div><div><font class="Apple-style-span" color="#000000">+ if (MD->isPure()) {</font></div><div><font class="Apple-style-span" color="#000000">+ os << "Call pure virtual functions during construction or "</font></div><div><font class="Apple-style-span" color="#000000">+ << "destruction may leads undefined behaviour";</font></div><div><font class="Apple-style-span" color="#000000">+ BR.EmitBasicReport("Call pure virtual function during construction or "</font></div><div><font class="Apple-style-span" color="#000000">+ "Destruction",</font></div><div><font class="Apple-style-span" color="#000000">+ "Cplusplus",</font></div><div><font class="Apple-style-span" color="#000000">+ os.str(), CELoc, &R, 1);</font></div><div><font class="Apple-style-span" color="#000000">+ return;</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+ else {</font></div><div><font class="Apple-style-span" color="#000000">+ os << "\n" << "Call virtual functions during construction or "</font></div><div><font class="Apple-style-span" color="#000000">+ << "destruction will never go to a more derived class";</font></div><div><font class="Apple-style-span" color="#000000">+ BR.EmitBasicReport("Call virtual function during construction or "</font></div><div><font class="Apple-style-span" color="#000000">+ "Destruction",</font></div><div><font class="Apple-style-span" color="#000000">+ "Cplusplus",</font></div><div><font class="Apple-style-span" color="#000000">+ os.str(), CELoc, &R, 1);</font></div><div><font class="Apple-style-span" color="#000000">+ return;</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+}</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+//===----------------------------------------------------------------------===//</font></div><div><font class="Apple-style-span" color="#000000">+// VirtualCallChecker</font></div><div><font class="Apple-style-span" color="#000000">+//===----------------------------------------------------------------------===//</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+namespace {</font></div><div><font class="Apple-style-span" color="#000000">+class VirtualCallChecker : public Checker<check::ASTDecl<CXXRecordDecl> > {</font></div><div><font class="Apple-style-span" color="#000000">+public:</font></div><div><font class="Apple-style-span" color="#000000">+ void checkASTDecl(const CXXRecordDecl *RD, AnalysisManager& mgr,</font></div><div><font class="Apple-style-span" color="#000000">+ BugReporter &BR) const {</font></div><div><font class="Apple-style-span" color="#000000">+ WalkAST walker(BR, mgr.getAnalysisDeclContext(RD));</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // Check the constructors.</font></div><div><font class="Apple-style-span" color="#000000">+ for (CXXRecordDecl::ctor_iterator I = RD->ctor_begin(), E = RD->ctor_end();</font></div><div><font class="Apple-style-span" color="#000000">+ I != E; ++I) {</font></div><div><font class="Apple-style-span" color="#000000">+ if (I->isCopyOrMoveConstructor())</font></div><div><font class="Apple-style-span" color="#000000">+ continue;</font></div><div><font class="Apple-style-span" color="#000000">+ walker.VisitCXXConstructorDecl(*I);</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+ // Check the destructor.</font></div><div><font class="Apple-style-span" color="#000000">+ CXXDestructorDecl *DD = RD->getDestructor();</font></div><div><font class="Apple-style-span" color="#000000">+ walker.VisitCXXDestructorDecl(DD);</font></div><div><font class="Apple-style-span" color="#000000">+ }</font></div><div><font class="Apple-style-span" color="#000000">+};</font></div><div><font class="Apple-style-span" color="#000000">+}</font></div><div><font class="Apple-style-span" color="#000000">+</font></div><div><font class="Apple-style-span" color="#000000">+void ento::registerVirtualCallChecker(CheckerManager &mgr) {</font></div><div><font class="Apple-style-span" color="#000000">+ mgr.registerChecker<VirtualCallChecker>();</font></div><div><font class="Apple-style-span" color="#000000">+}</font></div></blockquote><br></div><div>I think my main high level concern, beyond the code duplication, is that the algorithm seems a bit hard to follow. For example, I see two code paths in VisitCallExpr(), one for the case where the body of the callee has been analyzed before, and another one where it has not. Error reporting seems duplicated in a bunch of places, which is likely because the logic isn't quite factored the way it should be.</div><div><br></div><div>Stepping back, I think it's worth re-evaluating the overall algorithm. Here's an abstraction that I think will help.</div><div><br></div><div>Essentially we are building a virtual function callgraph. Once we have the callgraph, we can determine if any of the constructors/destructors can call a virtual function. Here's a simple decoupling of the algorithm:</div><div><br></div><div>(1) Do a DFS worklist algorithm to build the callgraph. This is basically the walk you are doing now, but you don't have to do any error reporting. You also don't need to keep track of the current call stack; all you care about is the current function you are analyzing, and the functions it calls. The worklist just consists of enqueueing FunctionDecls, dequeing them and walking their bodies looking for calls. When you see a call, you add the called function to the set of functions called by that function. Of course we only want to restrict ourselves to calls on the 'this' object.</div><div><br></div><div>(2) Once you have the (sparse) callgraph, you can iterate over all the constructors and destructors (you can cache a list of them on the side while doing step 1). For each one, do a BFS over the callgraph, looking for virtual functions. The BFS can be done as a worklist. The advantage of using a BFS is you just report the shortest call chain from the constructor/destructor to the virtual function. For each constructor/destructor, only report calling a specific virtual function once.</div><div><br></div><div>(2a) As a refinement to (2), you can cache when certain functions *never* call a virtual function, thus pruning the search. This is an optional step to improve performance.</div><div><br></div><div>(2b) Error reporting comes down to just reporting a path through the callgraph. Thus error reporting just becomes centralized in one place. No code duplication.</div><div><br></div><div>The nice thing about this approach is you get a really nice separation of concerns. You decouple to problem of finding the call graph (which conceptually could be extended to incorporate path-sensitive information, etc.) from the process of finding a bug (a path through the callgraph from constructor to virtual function). You also decouple the string generation from the logic of finding bugs.</div><div><br></div><div>I hope my comments are not discouraging. I think you are on the right track. I think taking a step back and looking at how the algorithm could be restructured would be really beneficial to cleaning up the code and also potentially making the checker more powerful in the long run. I also think you should pay a bit more attention to the accesses to containers. While doing redundant hash table lookups on a error reporting case is not so bad, having redundant lookups in the fast path of the checker really adds unnecessary sluggishness to your code.</div><div><br></div><div>I hope this helps.</div><div><br></div><div>Cheers,</div><div>Ted</div><div><br></div></body></html>