Index: cfe/trunk/lib/StaticAnalyzer/Core/BugReporter.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/BugReporter.cpp +++ cfe/trunk/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -556,330 +556,330 @@ static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM); -static bool GenerateMinimalPathDiagnostic( - PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, - LocationContextMap &LCM, - ArrayRef> visitors) { +/// Add path diagnostic for statement associated with node \p N +/// to diagnostics \p PD. +/// Precondition: location associated with \p N is a \c BlockEdge. +static void generateMinimalDiagnosticsForBlockEdge(const ExplodedNode *N, + PathDiagnosticBuilder &PDB, + PathDiagnostic &PD) { + + const LocationContext *LC = N->getLocationContext(); SourceManager& SMgr = PDB.getSourceManager(); - const LocationContext *LC = PDB.LC; - const ExplodedNode *NextNode = N->pred_empty() - ? nullptr : *(N->pred_begin()); + BlockEdge BE = N->getLocation().castAs(); + const CFGBlock *Src = BE.getSrc(); + const CFGBlock *Dst = BE.getDst(); + const Stmt *T = Src->getTerminator(); + if (!T) + return; - StackDiagVector CallStack; + auto Start = PathDiagnosticLocation::createBegin(T, SMgr, LC); + switch (T->getStmtClass()) { + default: + break; - while (NextNode) { - N = NextNode; - PDB.LC = N->getLocationContext(); - NextNode = N->getFirstPred(); + case Stmt::GotoStmtClass: + case Stmt::IndirectGotoStmtClass: { + const Stmt *S = PathDiagnosticLocation::getNextStmt(N); - ProgramPoint P = N->getLocation(); + if (!S) + break; - do { - if (Optional CE = P.getAs()) { - auto C = PathDiagnosticCallPiece::construct(N, *CE, SMgr); - // Record the mapping from call piece to LocationContext. - LCM[&C->path] = CE->getCalleeContext(); - auto *P = C.get(); - PD.getActivePath().push_front(std::move(C)); - PD.pushActivePath(&P->path); - CallStack.push_back(StackDiagPair(P, N)); + std::string sbuf; + llvm::raw_string_ostream os(sbuf); + const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S); + + os << "Control jumps to line " << End.asLocation().getExpansionLineNumber(); + PD.getActivePath().push_front( + std::make_shared(Start, End, os.str())); + break; + } + + case Stmt::SwitchStmtClass: { + // Figure out what case arm we took. + std::string sbuf; + llvm::raw_string_ostream os(sbuf); + + if (const Stmt *S = Dst->getLabel()) { + PathDiagnosticLocation End(S, SMgr, LC); + + switch (S->getStmtClass()) { + default: + os << "No cases match in the switch statement. " + "Control jumps to line " + << End.asLocation().getExpansionLineNumber(); + break; + case Stmt::DefaultStmtClass: + os << "Control jumps to the 'default' case at line " + << End.asLocation().getExpansionLineNumber(); break; - } - if (Optional CE = P.getAs()) { - // Flush all locations, and pop the active path. - bool VisitedEntireCall = PD.isWithinCall(); - PD.popActivePath(); - - // Either we just added a bunch of stuff to the top-level path, or - // we have a previous CallExitEnd. If the former, it means that the - // path terminated within a function call. We must then take the - // current contents of the active path and place it within - // a new PathDiagnosticCallPiece. - PathDiagnosticCallPiece *C; - if (VisitedEntireCall) { - C = cast(PD.getActivePath().front().get()); - } else { - const Decl *Caller = CE->getLocationContext()->getDecl(); - C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); - // Record the mapping from call piece to LocationContext. - LCM[&C->path] = CE->getCalleeContext(); - } + case Stmt::CaseStmtClass: { + os << "Control jumps to 'case "; + const CaseStmt *Case = cast(S); + const Expr *LHS = Case->getLHS()->IgnoreParenCasts(); + + // Determine if it is an enum. + bool GetRawInt = true; + + if (const DeclRefExpr *DR = dyn_cast(LHS)) { + // FIXME: Maybe this should be an assertion. Are there cases + // were it is not an EnumConstantDecl? + const EnumConstantDecl *D = dyn_cast(DR->getDecl()); - C->setCallee(*CE, SMgr); - if (!CallStack.empty()) { - assert(CallStack.back().first == C); - CallStack.pop_back(); + if (D) { + GetRawInt = false; + os << *D; + } } + + if (GetRawInt) + os << LHS->EvaluateKnownConstInt(PDB.getASTContext()); + + os << ":' at line " << End.asLocation().getExpansionLineNumber(); break; } + } + PD.getActivePath().push_front( + std::make_shared(Start, End, + os.str())); + } else { + os << "'Default' branch taken. "; + const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N); + PD.getActivePath().push_front( + std::make_shared(Start, End, + os.str())); + } - if (Optional BE = P.getAs()) { - const CFGBlock *Src = BE->getSrc(); - const CFGBlock *Dst = BE->getDst(); - const Stmt *T = Src->getTerminator(); + break; + } - if (!T) - break; + case Stmt::BreakStmtClass: + case Stmt::ContinueStmtClass: { + std::string sbuf; + llvm::raw_string_ostream os(sbuf); + PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); + PD.getActivePath().push_front( + std::make_shared(Start, End, os.str())); + break; + } - PathDiagnosticLocation Start = - PathDiagnosticLocation::createBegin(T, SMgr, - N->getLocationContext()); + // Determine control-flow for ternary '?'. + case Stmt::BinaryConditionalOperatorClass: + case Stmt::ConditionalOperatorClass: { + std::string sbuf; + llvm::raw_string_ostream os(sbuf); + os << "'?' condition is "; - switch (T->getStmtClass()) { - default: - break; + if (*(Src->succ_begin() + 1) == Dst) + os << "false"; + else + os << "true"; - case Stmt::GotoStmtClass: - case Stmt::IndirectGotoStmtClass: { - const Stmt *S = PathDiagnosticLocation::getNextStmt(N); + PathDiagnosticLocation End = PDB.ExecutionContinues(N); - if (!S) - break; + if (const Stmt *S = End.asStmt()) + End = PDB.getEnclosingStmtLocation(S); - std::string sbuf; - llvm::raw_string_ostream os(sbuf); - const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S); - - os << "Control jumps to line " - << End.asLocation().getExpansionLineNumber(); - PD.getActivePath().push_front( - std::make_shared(Start, End, - os.str())); - break; - } + PD.getActivePath().push_front( + std::make_shared(Start, End, os.str())); + break; + } - case Stmt::SwitchStmtClass: { - // Figure out what case arm we took. - std::string sbuf; - llvm::raw_string_ostream os(sbuf); - - if (const Stmt *S = Dst->getLabel()) { - PathDiagnosticLocation End(S, SMgr, LC); - - switch (S->getStmtClass()) { - default: - os << "No cases match in the switch statement. " - "Control jumps to line " - << End.asLocation().getExpansionLineNumber(); - break; - case Stmt::DefaultStmtClass: - os << "Control jumps to the 'default' case at line " - << End.asLocation().getExpansionLineNumber(); - break; + // Determine control-flow for short-circuited '&&' and '||'. + case Stmt::BinaryOperatorClass: { + if (!PDB.supportsLogicalOpControlFlow()) + break; - case Stmt::CaseStmtClass: { - os << "Control jumps to 'case "; - const CaseStmt *Case = cast(S); - const Expr *LHS = Case->getLHS()->IgnoreParenCasts(); - - // Determine if it is an enum. - bool GetRawInt = true; - - if (const DeclRefExpr *DR = dyn_cast(LHS)) { - // FIXME: Maybe this should be an assertion. Are there cases - // were it is not an EnumConstantDecl? - const EnumConstantDecl *D = - dyn_cast(DR->getDecl()); - - if (D) { - GetRawInt = false; - os << *D; - } - } + const BinaryOperator *B = cast(T); + std::string sbuf; + llvm::raw_string_ostream os(sbuf); + os << "Left side of '"; + + if (B->getOpcode() == BO_LAnd) { + os << "&&" + << "' is "; + + if (*(Src->succ_begin() + 1) == Dst) { + os << "false"; + PathDiagnosticLocation End(B->getLHS(), SMgr, LC); + PathDiagnosticLocation Start = + PathDiagnosticLocation::createOperatorLoc(B, SMgr); + PD.getActivePath().push_front( + std::make_shared(Start, End, + os.str())); + } else { + os << "true"; + PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); + PathDiagnosticLocation End = PDB.ExecutionContinues(N); + PD.getActivePath().push_front( + std::make_shared(Start, End, + os.str())); + } + } else { + assert(B->getOpcode() == BO_LOr); + os << "||" + << "' is "; + + if (*(Src->succ_begin() + 1) == Dst) { + os << "false"; + PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); + PathDiagnosticLocation End = PDB.ExecutionContinues(N); + PD.getActivePath().push_front( + std::make_shared(Start, End, + os.str())); + } else { + os << "true"; + PathDiagnosticLocation End(B->getLHS(), SMgr, LC); + PathDiagnosticLocation Start = + PathDiagnosticLocation::createOperatorLoc(B, SMgr); + PD.getActivePath().push_front( + std::make_shared(Start, End, + os.str())); + } + } - if (GetRawInt) - os << LHS->EvaluateKnownConstInt(PDB.getASTContext()); + break; + } - os << ":' at line " - << End.asLocation().getExpansionLineNumber(); - break; - } - } - PD.getActivePath().push_front( - std::make_shared(Start, End, - os.str())); - } - else { - os << "'Default' branch taken. "; - const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N); - PD.getActivePath().push_front( - std::make_shared(Start, End, - os.str())); - } + case Stmt::DoStmtClass: { + if (*(Src->succ_begin()) == Dst) { + std::string sbuf; + llvm::raw_string_ostream os(sbuf); + + os << "Loop condition is true. "; + PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); + + if (const Stmt *S = End.asStmt()) + End = PDB.getEnclosingStmtLocation(S); + + PD.getActivePath().push_front( + std::make_shared(Start, End, + os.str())); + } else { + PathDiagnosticLocation End = PDB.ExecutionContinues(N); - break; - } + if (const Stmt *S = End.asStmt()) + End = PDB.getEnclosingStmtLocation(S); - case Stmt::BreakStmtClass: - case Stmt::ContinueStmtClass: { - std::string sbuf; - llvm::raw_string_ostream os(sbuf); - PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); - PD.getActivePath().push_front( - std::make_shared(Start, End, - os.str())); - break; - } + PD.getActivePath().push_front( + std::make_shared( + Start, End, "Loop condition is false. Exiting loop")); + } - // Determine control-flow for ternary '?'. - case Stmt::BinaryConditionalOperatorClass: - case Stmt::ConditionalOperatorClass: { - std::string sbuf; - llvm::raw_string_ostream os(sbuf); - os << "'?' condition is "; - - if (*(Src->succ_begin()+1) == Dst) - os << "false"; - else - os << "true"; - - PathDiagnosticLocation End = PDB.ExecutionContinues(N); - - if (const Stmt *S = End.asStmt()) - End = PDB.getEnclosingStmtLocation(S); - - PD.getActivePath().push_front( - std::make_shared(Start, End, - os.str())); - break; - } + break; + } - // Determine control-flow for short-circuited '&&' and '||'. - case Stmt::BinaryOperatorClass: { - if (!PDB.supportsLogicalOpControlFlow()) - break; + case Stmt::WhileStmtClass: + case Stmt::ForStmtClass: { + if (*(Src->succ_begin() + 1) == Dst) { + std::string sbuf; + llvm::raw_string_ostream os(sbuf); + + os << "Loop condition is false. "; + PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); + if (const Stmt *S = End.asStmt()) + End = PDB.getEnclosingStmtLocation(S); + + PD.getActivePath().push_front( + std::make_shared(Start, End, + os.str())); + } else { + PathDiagnosticLocation End = PDB.ExecutionContinues(N); + if (const Stmt *S = End.asStmt()) + End = PDB.getEnclosingStmtLocation(S); + + PD.getActivePath().push_front( + std::make_shared( + Start, End, "Loop condition is true. Entering loop body")); + } - const BinaryOperator *B = cast(T); - std::string sbuf; - llvm::raw_string_ostream os(sbuf); - os << "Left side of '"; - - if (B->getOpcode() == BO_LAnd) { - os << "&&" << "' is "; - - if (*(Src->succ_begin()+1) == Dst) { - os << "false"; - PathDiagnosticLocation End(B->getLHS(), SMgr, LC); - PathDiagnosticLocation Start = - PathDiagnosticLocation::createOperatorLoc(B, SMgr); - PD.getActivePath().push_front( - std::make_shared(Start, End, - os.str())); - } - else { - os << "true"; - PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); - PathDiagnosticLocation End = PDB.ExecutionContinues(N); - PD.getActivePath().push_front( - std::make_shared(Start, End, - os.str())); - } - } - else { - assert(B->getOpcode() == BO_LOr); - os << "||" << "' is "; - - if (*(Src->succ_begin()+1) == Dst) { - os << "false"; - PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); - PathDiagnosticLocation End = PDB.ExecutionContinues(N); - PD.getActivePath().push_front( - std::make_shared(Start, End, - os.str())); - } - else { - os << "true"; - PathDiagnosticLocation End(B->getLHS(), SMgr, LC); - PathDiagnosticLocation Start = - PathDiagnosticLocation::createOperatorLoc(B, SMgr); - PD.getActivePath().push_front( - std::make_shared(Start, End, - os.str())); - } - } + break; + } - break; - } + case Stmt::IfStmtClass: { + PathDiagnosticLocation End = PDB.ExecutionContinues(N); - case Stmt::DoStmtClass: { - if (*(Src->succ_begin()) == Dst) { - std::string sbuf; - llvm::raw_string_ostream os(sbuf); - - os << "Loop condition is true. "; - PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); - - if (const Stmt *S = End.asStmt()) - End = PDB.getEnclosingStmtLocation(S); - - PD.getActivePath().push_front( - std::make_shared(Start, End, - os.str())); - } - else { - PathDiagnosticLocation End = PDB.ExecutionContinues(N); + if (const Stmt *S = End.asStmt()) + End = PDB.getEnclosingStmtLocation(S); - if (const Stmt *S = End.asStmt()) - End = PDB.getEnclosingStmtLocation(S); + if (*(Src->succ_begin() + 1) == Dst) + PD.getActivePath().push_front( + std::make_shared( + Start, End, "Taking false branch")); + else + PD.getActivePath().push_front( + std::make_shared( + Start, End, "Taking true branch")); - PD.getActivePath().push_front( - std::make_shared( - Start, End, "Loop condition is false. Exiting loop")); - } + break; + } + } +} - break; - } +/// Generate minimal diagnostics for node \p N, and write it into path +/// diagnostics \p PD. +void generateMinimalDiagnosticsForNode(const ExplodedNode *N, + PathDiagnosticBuilder &PDB, + PathDiagnostic &PD, + LocationContextMap &LCM, + StackDiagVector &CallStack) { - case Stmt::WhileStmtClass: - case Stmt::ForStmtClass: { - if (*(Src->succ_begin()+1) == Dst) { - std::string sbuf; - llvm::raw_string_ostream os(sbuf); - - os << "Loop condition is false. "; - PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); - if (const Stmt *S = End.asStmt()) - End = PDB.getEnclosingStmtLocation(S); - - PD.getActivePath().push_front( - std::make_shared(Start, End, - os.str())); - } - else { - PathDiagnosticLocation End = PDB.ExecutionContinues(N); - if (const Stmt *S = End.asStmt()) - End = PDB.getEnclosingStmtLocation(S); - - PD.getActivePath().push_front( - std::make_shared( - Start, End, "Loop condition is true. Entering loop body")); - } + SourceManager &SMgr = PDB.getSourceManager(); + ProgramPoint P = N->getLocation(); - break; - } + if (Optional CE = P.getAs()) { + auto C = PathDiagnosticCallPiece::construct(N, *CE, SMgr); + // Record the mapping from call piece to LocationContext. + LCM[&C->path] = CE->getCalleeContext(); + auto *P = C.get(); + PD.getActivePath().push_front(std::move(C)); + PD.pushActivePath(&P->path); + CallStack.push_back(StackDiagPair(P, N)); + } else if (Optional CE = P.getAs()) { + // Flush all locations, and pop the active path. + bool VisitedEntireCall = PD.isWithinCall(); + PD.popActivePath(); + + // Either we just added a bunch of stuff to the top-level path, or + // we have a previous CallExitEnd. If the former, it means that the + // path terminated within a function call. We must then take the + // current contents of the active path and place it within + // a new PathDiagnosticCallPiece. + PathDiagnosticCallPiece *C; + if (VisitedEntireCall) { + C = cast(PD.getActivePath().front().get()); + } else { + const Decl *Caller = CE->getLocationContext()->getDecl(); + C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); + // Record the mapping from call piece to LocationContext. + LCM[&C->path] = CE->getCalleeContext(); + } - case Stmt::IfStmtClass: { - PathDiagnosticLocation End = PDB.ExecutionContinues(N); + C->setCallee(*CE, SMgr); + if (!CallStack.empty()) { + assert(CallStack.back().first == C); + CallStack.pop_back(); + } + } else if (P.getKind() == ProgramPoint::BlockEdgeKind) { + generateMinimalDiagnosticsForBlockEdge(N, PDB, PD); + } +} - if (const Stmt *S = End.asStmt()) - End = PDB.getEnclosingStmtLocation(S); +static bool GenerateMinimalPathDiagnostic( + PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, + LocationContextMap &LCM, + ArrayRef> visitors) { + const ExplodedNode *NextNode = N->pred_empty() + ? nullptr : *(N->pred_begin()); + StackDiagVector CallStack; - if (*(Src->succ_begin()+1) == Dst) - PD.getActivePath().push_front( - std::make_shared( - Start, End, "Taking false branch")); - else - PD.getActivePath().push_front( - std::make_shared( - Start, End, "Taking true branch")); + while (NextNode) { + N = NextNode; + PDB.LC = N->getLocationContext(); + NextNode = N->getFirstPred(); - break; - } - } - } - } while(0); + generateMinimalDiagnosticsForNode(N, PDB, PD, LCM, CallStack); if (NextNode) { // Add diagnostic pieces from custom visitors. @@ -1315,6 +1315,8 @@ } } + + //===----------------------------------------------------------------------===// // Functions for determining if a loop was executed 0 times. //===----------------------------------------------------------------------===// @@ -1404,6 +1406,169 @@ return isContainedByStmt(PM, LoopBody, S); } +/// Generate extensive diagnostics for statement associated with node \p N, +/// and write it into \p PD. +static void generateExtensiveDiagnosticsForNode( + const ExplodedNode *N, + PathDiagnosticBuilder &PDB, + LocationContextMap &LCM, + EdgeBuilder &EB, + StackDiagVector &CallStack, + PathDiagnostic &PD, + InterestingExprs &IE) { + + const ExplodedNode *NextNode = N->getFirstPred(); + ProgramPoint P = N->getLocation(); + const SourceManager& SM = PDB.getSourceManager(); + + if (Optional PS = P.getAs()) { + if (const Expr *Ex = PS->getStmtAs()) + reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, + N->getState().get(), Ex, + N->getLocationContext()); + return; + } else if (Optional CE = P.getAs()) { + const Stmt *S = CE->getCalleeContext()->getCallSite(); + if (const Expr *Ex = dyn_cast_or_null(S)) { + reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, + N->getState().get(), Ex, + N->getLocationContext()); + } + + auto C = PathDiagnosticCallPiece::construct(N, *CE, SM); + LCM[&C->path] = CE->getCalleeContext(); + + EB.addEdge(C->callReturn, /*AlwaysAdd=*/true, /*IsPostJump=*/true); + EB.flushLocations(); + + auto *P = C.get(); + PD.getActivePath().push_front(std::move(C)); + PD.pushActivePath(&P->path); + CallStack.push_back(StackDiagPair(P, N)); + return; + } else if (Optional CE = P.getAs()) { + + // Pop the call hierarchy if we are done walking the contents + // of a function call. + + // Add an edge to the start of the function. + const Decl *D = CE->getCalleeContext()->getDecl(); + PathDiagnosticLocation pos = + PathDiagnosticLocation::createBegin(D, SM); + EB.addEdge(pos); + + // Flush all locations, and pop the active path. + bool VisitedEntireCall = PD.isWithinCall(); + EB.flushLocations(); + PD.popActivePath(); + PDB.LC = N->getLocationContext(); + + // Either we just added a bunch of stuff to the top-level path, or + // we have a previous CallExitEnd. If the former, it means that the + // path terminated within a function call. We must then take the + // current contents of the active path and place it within + // a new PathDiagnosticCallPiece. + PathDiagnosticCallPiece *C; + if (VisitedEntireCall) { + C = cast(PD.getActivePath().front().get()); + } else { + const Decl *Caller = CE->getLocationContext()->getDecl(); + C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); + LCM[&C->path] = CE->getCalleeContext(); + } + + C->setCallee(*CE, SM); + EB.addContext(C->getLocation()); + + if (!CallStack.empty()) { + assert(CallStack.back().first == C); + CallStack.pop_back(); + } + return; + } + + // Note that is important that we update the LocationContext + // after looking at CallExits. CallExit basically adds an + // edge in the *caller*, so we don't want to update the LocationContext + // too soon. + PDB.LC = N->getLocationContext(); + + if (Optional BE = P.getAs()) { + // Does this represent entering a call? If so, look at propagating + // interesting symbols across call boundaries. + if (NextNode) { + const LocationContext *CallerCtx = NextNode->getLocationContext(); + const LocationContext *CalleeCtx = PDB.LC; + if (CallerCtx != CalleeCtx) { + reversePropagateInterestingSymbols(*PDB.getBugReport(), IE, + N->getState().get(), + CalleeCtx, CallerCtx); + } + } + + // Are we jumping to the head of a loop? Add a special diagnostic. + if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { + PathDiagnosticLocation L(Loop, SM, PDB.LC); + const CompoundStmt *CS = nullptr; + + if (const ForStmt *FS = dyn_cast(Loop)) + CS = dyn_cast(FS->getBody()); + else if (const WhileStmt *WS = dyn_cast(Loop)) + CS = dyn_cast(WS->getBody()); + + auto p = std::make_shared( + L, "Looping back to the head of the loop"); + p->setPrunable(true); + + EB.addEdge(p->getLocation(), true); + PD.getActivePath().push_front(std::move(p)); + + if (CS) { + PathDiagnosticLocation BL = + PathDiagnosticLocation::createEndBrace(CS, SM); + EB.addEdge(BL); + } + } + + const CFGBlock *BSrc = BE->getSrc(); + ParentMap &PM = PDB.getParentMap(); + + if (const Stmt *Term = BSrc->getTerminator()) { + // Are we jumping past the loop body without ever executing the + // loop (because the condition was false)? + if (isLoopJumpPastBody(Term, &*BE) && + !isInLoopBody(PM, + getStmtBeforeCond(PM, + BSrc->getTerminatorCondition(), + N), + Term)) { + PathDiagnosticLocation L(Term, SM, PDB.LC); + auto PE = std::make_shared( + L, "Loop body executed 0 times"); + PE->setPrunable(true); + + EB.addEdge(PE->getLocation(), true); + PD.getActivePath().push_front(std::move(PE)); + } + + // In any case, add the terminator as the current statement + // context for control edges. + EB.addContext(Term); + } + } else if (Optional BE = P.getAs()) { + Optional First = BE->getFirstElement(); + if (Optional S = First ? First->getAs() : None) { + const Stmt *stmt = S->getStmt(); + if (IsControlFlowExpr(stmt)) { + // Add the proper context for '&&', '||', and '?'. + EB.addContext(stmt); + } + else + EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt()); + } + } +} + //===----------------------------------------------------------------------===// // Top-level logic for generating extensive path diagnostics. //===----------------------------------------------------------------------===// @@ -1413,174 +1578,15 @@ LocationContextMap &LCM, ArrayRef> visitors) { EdgeBuilder EB(PD, PDB); - const SourceManager& SM = PDB.getSourceManager(); StackDiagVector CallStack; - InterestingExprs IE; + InterestingExprs IE; const ExplodedNode *NextNode = N->pred_empty() ? nullptr : *(N->pred_begin()); while (NextNode) { N = NextNode; NextNode = N->getFirstPred(); - ProgramPoint P = N->getLocation(); - do { - if (Optional PS = P.getAs()) { - if (const Expr *Ex = PS->getStmtAs()) - reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, - N->getState().get(), Ex, - N->getLocationContext()); - } - - if (Optional CE = P.getAs()) { - const Stmt *S = CE->getCalleeContext()->getCallSite(); - if (const Expr *Ex = dyn_cast_or_null(S)) { - reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, - N->getState().get(), Ex, - N->getLocationContext()); - } - - auto C = PathDiagnosticCallPiece::construct(N, *CE, SM); - LCM[&C->path] = CE->getCalleeContext(); - - EB.addEdge(C->callReturn, /*AlwaysAdd=*/true, /*IsPostJump=*/true); - EB.flushLocations(); - - auto *P = C.get(); - PD.getActivePath().push_front(std::move(C)); - PD.pushActivePath(&P->path); - CallStack.push_back(StackDiagPair(P, N)); - break; - } - - // Pop the call hierarchy if we are done walking the contents - // of a function call. - if (Optional CE = P.getAs()) { - // Add an edge to the start of the function. - const Decl *D = CE->getCalleeContext()->getDecl(); - PathDiagnosticLocation pos = - PathDiagnosticLocation::createBegin(D, SM); - EB.addEdge(pos); - - // Flush all locations, and pop the active path. - bool VisitedEntireCall = PD.isWithinCall(); - EB.flushLocations(); - PD.popActivePath(); - PDB.LC = N->getLocationContext(); - - // Either we just added a bunch of stuff to the top-level path, or - // we have a previous CallExitEnd. If the former, it means that the - // path terminated within a function call. We must then take the - // current contents of the active path and place it within - // a new PathDiagnosticCallPiece. - PathDiagnosticCallPiece *C; - if (VisitedEntireCall) { - C = cast(PD.getActivePath().front().get()); - } else { - const Decl *Caller = CE->getLocationContext()->getDecl(); - C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); - LCM[&C->path] = CE->getCalleeContext(); - } - - C->setCallee(*CE, SM); - EB.addContext(C->getLocation()); - - if (!CallStack.empty()) { - assert(CallStack.back().first == C); - CallStack.pop_back(); - } - break; - } - - // Note that is important that we update the LocationContext - // after looking at CallExits. CallExit basically adds an - // edge in the *caller*, so we don't want to update the LocationContext - // too soon. - PDB.LC = N->getLocationContext(); - - // Block edges. - if (Optional BE = P.getAs()) { - // Does this represent entering a call? If so, look at propagating - // interesting symbols across call boundaries. - if (NextNode) { - const LocationContext *CallerCtx = NextNode->getLocationContext(); - const LocationContext *CalleeCtx = PDB.LC; - if (CallerCtx != CalleeCtx) { - reversePropagateInterestingSymbols(*PDB.getBugReport(), IE, - N->getState().get(), - CalleeCtx, CallerCtx); - } - } - - // Are we jumping to the head of a loop? Add a special diagnostic. - if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { - PathDiagnosticLocation L(Loop, SM, PDB.LC); - const CompoundStmt *CS = nullptr; - - if (const ForStmt *FS = dyn_cast(Loop)) - CS = dyn_cast(FS->getBody()); - else if (const WhileStmt *WS = dyn_cast(Loop)) - CS = dyn_cast(WS->getBody()); - - auto p = std::make_shared( - L, "Looping back to the head of the loop"); - p->setPrunable(true); - - EB.addEdge(p->getLocation(), true); - PD.getActivePath().push_front(std::move(p)); - - if (CS) { - PathDiagnosticLocation BL = - PathDiagnosticLocation::createEndBrace(CS, SM); - EB.addEdge(BL); - } - } - - const CFGBlock *BSrc = BE->getSrc(); - ParentMap &PM = PDB.getParentMap(); - - if (const Stmt *Term = BSrc->getTerminator()) { - // Are we jumping past the loop body without ever executing the - // loop (because the condition was false)? - if (isLoopJumpPastBody(Term, &*BE) && - !isInLoopBody(PM, - getStmtBeforeCond(PM, - BSrc->getTerminatorCondition(), - N), - Term)) { - PathDiagnosticLocation L(Term, SM, PDB.LC); - auto PE = std::make_shared( - L, "Loop body executed 0 times"); - PE->setPrunable(true); - - EB.addEdge(PE->getLocation(), true); - PD.getActivePath().push_front(std::move(PE)); - } - - // In any case, add the terminator as the current statement - // context for control edges. - EB.addContext(Term); - } - - break; - } - - if (Optional BE = P.getAs()) { - Optional First = BE->getFirstElement(); - if (Optional S = First ? First->getAs() : None) { - const Stmt *stmt = S->getStmt(); - if (IsControlFlowExpr(stmt)) { - // Add the proper context for '&&', '||', and '?'. - EB.addContext(stmt); - } - else - EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt()); - } - - break; - } - - - } while (0); + generateExtensiveDiagnosticsForNode(N, PDB, LCM, EB, CallStack, PD, IE); if (!NextNode) continue; @@ -1651,6 +1657,223 @@ static const char StrLoopCollectionEmpty[] = "Loop body skipped when collection is empty"; +/// Generate alternate-extensive diagnostics for the node \p N, +/// and write it into \p PD. +static void generateAlternateExtensiveDiagnosticsForNode(const ExplodedNode *N, + PathDiagnostic &PD, + PathDiagnosticLocation &PrevLoc, + PathDiagnosticBuilder &PDB, + LocationContextMap &LCM, + StackDiagVector &CallStack, + InterestingExprs &IE) { + const ExplodedNode *NextNode = N->getFirstPred(); + ProgramPoint P = N->getLocation(); + const SourceManager& SM = PDB.getSourceManager(); + + // Have we encountered an entrance to a call? It may be + // the case that we have not encountered a matching + // call exit before this point. This means that the path + // terminated within the call itself. + if (Optional CE = P.getAs()) { + // Add an edge to the start of the function. + const StackFrameContext *CalleeLC = CE->getCalleeContext(); + const Decl *D = CalleeLC->getDecl(); + // Add the edge only when the callee has body. We jump to the beginning + // of the *declaration*, however we expect it to be followed by the + // body. This isn't the case for autosynthesized property accessors in + // Objective-C. No need for a similar extra check for CallExit points + // because the exit edge comes from a statement (i.e. return), + // not from declaration. + if (D->hasBody()) + addEdgeToPath(PD.getActivePath(), PrevLoc, + PathDiagnosticLocation::createBegin(D, SM), CalleeLC); + + // Did we visit an entire call? + bool VisitedEntireCall = PD.isWithinCall(); + PD.popActivePath(); + + PathDiagnosticCallPiece *C; + if (VisitedEntireCall) { + PathDiagnosticPiece *P = PD.getActivePath().front().get(); + C = cast(P); + } else { + const Decl *Caller = CE->getLocationContext()->getDecl(); + C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); + + // Since we just transferred the path over to the call piece, + // reset the mapping from active to location context. + assert(PD.getActivePath().size() == 1 && + PD.getActivePath().front().get() == C); + LCM[&PD.getActivePath()] = nullptr; + + // Record the location context mapping for the path within + // the call. + assert(LCM[&C->path] == nullptr || + LCM[&C->path] == CE->getCalleeContext()); + LCM[&C->path] = CE->getCalleeContext(); + + // If this is the first item in the active path, record + // the new mapping from active path to location context. + const LocationContext *&NewLC = LCM[&PD.getActivePath()]; + if (!NewLC) + NewLC = N->getLocationContext(); + + PDB.LC = NewLC; + } + C->setCallee(*CE, SM); + + // Update the previous location in the active path. + PrevLoc = C->getLocation(); + + if (!CallStack.empty()) { + assert(CallStack.back().first == C); + CallStack.pop_back(); + } + return; + } + + // Query the location context here and the previous location + // as processing CallEnter may change the active path. + PDB.LC = N->getLocationContext(); + + // Record the mapping from the active path to the location + // context. + assert(!LCM[&PD.getActivePath()] || + LCM[&PD.getActivePath()] == PDB.LC); + LCM[&PD.getActivePath()] = PDB.LC; + + // Have we encountered an exit from a function call? + if (Optional CE = P.getAs()) { + const Stmt *S = CE->getCalleeContext()->getCallSite(); + // Propagate the interesting symbols accordingly. + if (const Expr *Ex = dyn_cast_or_null(S)) { + reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, + N->getState().get(), Ex, + N->getLocationContext()); + } + + // We are descending into a call (backwards). Construct + // a new call piece to contain the path pieces for that call. + auto C = PathDiagnosticCallPiece::construct(N, *CE, SM); + + // Record the location context for this call piece. + LCM[&C->path] = CE->getCalleeContext(); + + // Add the edge to the return site. + addEdgeToPath(PD.getActivePath(), PrevLoc, C->callReturn, PDB.LC); + auto *P = C.get(); + PD.getActivePath().push_front(std::move(C)); + PrevLoc.invalidate(); + + // Make the contents of the call the active path for now. + PD.pushActivePath(&P->path); + CallStack.push_back(StackDiagPair(P, N)); + } else if (Optional PS = P.getAs()) { + // For expressions, make sure we propagate the + // interesting symbols correctly. + if (const Expr *Ex = PS->getStmtAs()) + reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, + N->getState().get(), Ex, + N->getLocationContext()); + + // Add an edge. If this is an ObjCForCollectionStmt do + // not add an edge here as it appears in the CFG both + // as a terminator and as a terminator condition. + if (!isa(PS->getStmt())) { + PathDiagnosticLocation L = + PathDiagnosticLocation(PS->getStmt(), SM, PDB.LC); + addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); + } + } else if (Optional BE = P.getAs()) { + // Does this represent entering a call? If so, look at propagating + // interesting symbols across call boundaries. + if (NextNode) { + const LocationContext *CallerCtx = NextNode->getLocationContext(); + const LocationContext *CalleeCtx = PDB.LC; + if (CallerCtx != CalleeCtx) { + reversePropagateInterestingSymbols(*PDB.getBugReport(), IE, + N->getState().get(), + CalleeCtx, CallerCtx); + } + } + + // Are we jumping to the head of a loop? Add a special diagnostic. + if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { + PathDiagnosticLocation L(Loop, SM, PDB.LC); + const Stmt *Body = nullptr; + + if (const ForStmt *FS = dyn_cast(Loop)) + Body = FS->getBody(); + else if (const WhileStmt *WS = dyn_cast(Loop)) + Body = WS->getBody(); + else if (const ObjCForCollectionStmt *OFS = + dyn_cast(Loop)) { + Body = OFS->getBody(); + } else if (const CXXForRangeStmt *FRS = + dyn_cast(Loop)) { + Body = FRS->getBody(); + } + // do-while statements are explicitly excluded here + + auto p = std::make_shared( + L, "Looping back to the head " + "of the loop"); + p->setPrunable(true); + + addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC); + PD.getActivePath().push_front(std::move(p)); + + if (const CompoundStmt *CS = dyn_cast_or_null(Body)) { + addEdgeToPath(PD.getActivePath(), PrevLoc, + PathDiagnosticLocation::createEndBrace(CS, SM), + PDB.LC); + } + } + + const CFGBlock *BSrc = BE->getSrc(); + ParentMap &PM = PDB.getParentMap(); + + if (const Stmt *Term = BSrc->getTerminator()) { + // Are we jumping past the loop body without ever executing the + // loop (because the condition was false)? + if (isLoop(Term)) { + const Stmt *TermCond = getTerminatorCondition(BSrc); + bool IsInLoopBody = + isInLoopBody(PM, getStmtBeforeCond(PM, TermCond, N), Term); + + const char *str = nullptr; + + if (isJumpToFalseBranch(&*BE)) { + if (!IsInLoopBody) { + if (isa(Term)) { + str = StrLoopCollectionEmpty; + } else if (isa(Term)) { + str = StrLoopRangeEmpty; + } else { + str = StrLoopBodyZero; + } + } + } else { + str = StrEnteringLoop; + } + + if (str) { + PathDiagnosticLocation L(TermCond ? TermCond : Term, SM, PDB.LC); + auto PE = std::make_shared(L, str); + PE->setPrunable(true); + addEdgeToPath(PD.getActivePath(), PrevLoc, + PE->getLocation(), PDB.LC); + PD.getActivePath().push_front(std::move(PE)); + } + } else if (isa(Term) || isa(Term) || + isa(Term)) { + PathDiagnosticLocation L(Term, SM, PDB.LC); + addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); + } + } + } +} + static bool GenerateAlternateExtensivePathDiagnostic( PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, LocationContextMap &LCM, @@ -1667,220 +1890,9 @@ while (NextNode) { N = NextNode; NextNode = N->getFirstPred(); - ProgramPoint P = N->getLocation(); - - do { - // Have we encountered an entrance to a call? It may be - // the case that we have not encountered a matching - // call exit before this point. This means that the path - // terminated within the call itself. - if (Optional CE = P.getAs()) { - // Add an edge to the start of the function. - const StackFrameContext *CalleeLC = CE->getCalleeContext(); - const Decl *D = CalleeLC->getDecl(); - // Add the edge only when the callee has body. We jump to the beginning - // of the *declaration*, however we expect it to be followed by the - // body. This isn't the case for autosynthesized property accessors in - // Objective-C. No need for a similar extra check for CallExit points - // because the exit edge comes from a statement (i.e. return), - // not from declaration. - if (D->hasBody()) - addEdgeToPath(PD.getActivePath(), PrevLoc, - PathDiagnosticLocation::createBegin(D, SM), CalleeLC); - - // Did we visit an entire call? - bool VisitedEntireCall = PD.isWithinCall(); - PD.popActivePath(); - - PathDiagnosticCallPiece *C; - if (VisitedEntireCall) { - PathDiagnosticPiece *P = PD.getActivePath().front().get(); - C = cast(P); - } else { - const Decl *Caller = CE->getLocationContext()->getDecl(); - C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); - - // Since we just transferred the path over to the call piece, - // reset the mapping from active to location context. - assert(PD.getActivePath().size() == 1 && - PD.getActivePath().front().get() == C); - LCM[&PD.getActivePath()] = nullptr; - - // Record the location context mapping for the path within - // the call. - assert(LCM[&C->path] == nullptr || - LCM[&C->path] == CE->getCalleeContext()); - LCM[&C->path] = CE->getCalleeContext(); - - // If this is the first item in the active path, record - // the new mapping from active path to location context. - const LocationContext *&NewLC = LCM[&PD.getActivePath()]; - if (!NewLC) - NewLC = N->getLocationContext(); - PDB.LC = NewLC; - } - C->setCallee(*CE, SM); - - // Update the previous location in the active path. - PrevLoc = C->getLocation(); - - if (!CallStack.empty()) { - assert(CallStack.back().first == C); - CallStack.pop_back(); - } - break; - } - - // Query the location context here and the previous location - // as processing CallEnter may change the active path. - PDB.LC = N->getLocationContext(); - - // Record the mapping from the active path to the location - // context. - assert(!LCM[&PD.getActivePath()] || - LCM[&PD.getActivePath()] == PDB.LC); - LCM[&PD.getActivePath()] = PDB.LC; - - // Have we encountered an exit from a function call? - if (Optional CE = P.getAs()) { - const Stmt *S = CE->getCalleeContext()->getCallSite(); - // Propagate the interesting symbols accordingly. - if (const Expr *Ex = dyn_cast_or_null(S)) { - reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, - N->getState().get(), Ex, - N->getLocationContext()); - } - - // We are descending into a call (backwards). Construct - // a new call piece to contain the path pieces for that call. - auto C = PathDiagnosticCallPiece::construct(N, *CE, SM); - - // Record the location context for this call piece. - LCM[&C->path] = CE->getCalleeContext(); - - // Add the edge to the return site. - addEdgeToPath(PD.getActivePath(), PrevLoc, C->callReturn, PDB.LC); - auto *P = C.get(); - PD.getActivePath().push_front(std::move(C)); - PrevLoc.invalidate(); - - // Make the contents of the call the active path for now. - PD.pushActivePath(&P->path); - CallStack.push_back(StackDiagPair(P, N)); - break; - } - - if (Optional PS = P.getAs()) { - // For expressions, make sure we propagate the - // interesting symbols correctly. - if (const Expr *Ex = PS->getStmtAs()) - reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, - N->getState().get(), Ex, - N->getLocationContext()); - - // Add an edge. If this is an ObjCForCollectionStmt do - // not add an edge here as it appears in the CFG both - // as a terminator and as a terminator condition. - if (!isa(PS->getStmt())) { - PathDiagnosticLocation L = - PathDiagnosticLocation(PS->getStmt(), SM, PDB.LC); - addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); - } - break; - } - - // Block edges. - if (Optional BE = P.getAs()) { - // Does this represent entering a call? If so, look at propagating - // interesting symbols across call boundaries. - if (NextNode) { - const LocationContext *CallerCtx = NextNode->getLocationContext(); - const LocationContext *CalleeCtx = PDB.LC; - if (CallerCtx != CalleeCtx) { - reversePropagateInterestingSymbols(*PDB.getBugReport(), IE, - N->getState().get(), - CalleeCtx, CallerCtx); - } - } - - // Are we jumping to the head of a loop? Add a special diagnostic. - if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { - PathDiagnosticLocation L(Loop, SM, PDB.LC); - const Stmt *Body = nullptr; - - if (const ForStmt *FS = dyn_cast(Loop)) - Body = FS->getBody(); - else if (const WhileStmt *WS = dyn_cast(Loop)) - Body = WS->getBody(); - else if (const ObjCForCollectionStmt *OFS = - dyn_cast(Loop)) { - Body = OFS->getBody(); - } else if (const CXXForRangeStmt *FRS = - dyn_cast(Loop)) { - Body = FRS->getBody(); - } - // do-while statements are explicitly excluded here - - auto p = std::make_shared( - L, "Looping back to the head " - "of the loop"); - p->setPrunable(true); - - addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC); - PD.getActivePath().push_front(std::move(p)); - - if (const CompoundStmt *CS = dyn_cast_or_null(Body)) { - addEdgeToPath(PD.getActivePath(), PrevLoc, - PathDiagnosticLocation::createEndBrace(CS, SM), - PDB.LC); - } - } - - const CFGBlock *BSrc = BE->getSrc(); - ParentMap &PM = PDB.getParentMap(); - - if (const Stmt *Term = BSrc->getTerminator()) { - // Are we jumping past the loop body without ever executing the - // loop (because the condition was false)? - if (isLoop(Term)) { - const Stmt *TermCond = getTerminatorCondition(BSrc); - bool IsInLoopBody = - isInLoopBody(PM, getStmtBeforeCond(PM, TermCond, N), Term); - - const char *str = nullptr; - - if (isJumpToFalseBranch(&*BE)) { - if (!IsInLoopBody) { - if (isa(Term)) { - str = StrLoopCollectionEmpty; - } else if (isa(Term)) { - str = StrLoopRangeEmpty; - } else { - str = StrLoopBodyZero; - } - } - } else { - str = StrEnteringLoop; - } - - if (str) { - PathDiagnosticLocation L(TermCond ? TermCond : Term, SM, PDB.LC); - auto PE = std::make_shared(L, str); - PE->setPrunable(true); - addEdgeToPath(PD.getActivePath(), PrevLoc, - PE->getLocation(), PDB.LC); - PD.getActivePath().push_front(std::move(PE)); - } - } else if (isa(Term) || isa(Term) || - isa(Term)) { - PathDiagnosticLocation L(Term, SM, PDB.LC); - addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); - } - } - break; - } - } while (0); + generateAlternateExtensiveDiagnosticsForNode( + N, PD, PrevLoc, PDB, LCM, CallStack, IE); if (!NextNode) continue;