diff options
Diffstat (limited to 'lib/StaticAnalyzer/Core')
27 files changed, 1880 insertions, 869 deletions
diff --git a/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp b/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp index ae70739..9dcf58b 100644 --- a/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp +++ b/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp @@ -140,6 +140,12 @@ bool AnalyzerOptions::mayInlineCXXContainerCtorsAndDtors() { /*Default=*/false); } +bool AnalyzerOptions::mayInlineCXXSharedPtrDtor() { + return getBooleanOption(InlineCXXSharedPtrDtor, + "c++-shared_ptr-inlining", + /*Default=*/false); +} + bool AnalyzerOptions::mayInlineObjCMethod() { return getBooleanOption(ObjCInliningMode, @@ -171,6 +177,12 @@ bool AnalyzerOptions::shouldSuppressFromCXXStandardLibrary() { /* Default = */ false); } +bool AnalyzerOptions::shouldReportIssuesInMainSourceFile() { + return getBooleanOption(ReportIssuesInMainSourceFile, + "report-in-main-source-file", + /* Default = */ false); +} + int AnalyzerOptions::getOptionAsInteger(StringRef Name, int DefaultVal) { SmallString<10> StrBuf; llvm::raw_svector_ostream OS(StrBuf); diff --git a/lib/StaticAnalyzer/Core/BugReporter.cpp b/lib/StaticAnalyzer/Core/BugReporter.cpp index a85235c..1940fa7 100644 --- a/lib/StaticAnalyzer/Core/BugReporter.cpp +++ b/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -18,8 +18,10 @@ #include "clang/AST/ASTContext.h" #include "clang/AST/DeclObjC.h" #include "clang/AST/Expr.h" +#include "clang/AST/ExprCXX.h" #include "clang/AST/ParentMap.h" #include "clang/AST/StmtObjC.h" +#include "clang/AST/StmtCXX.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/ProgramPoint.h" #include "clang/Basic/SourceManager.h" @@ -162,13 +164,6 @@ static bool removeUnneededCalls(PathPieces &pieces, BugReport *R, IntrusiveRefCntPtr<PathDiagnosticPiece> piece(pieces.front()); pieces.pop_front(); - // Throw away pieces with invalid locations. Note that we can't throw away - // calls just yet because they might have something interesting inside them. - // If so, their locations will be adjusted as necessary later. - if (piece->getKind() != PathDiagnosticPiece::Call && - piece->getLocation().asLocation().isInvalid()) - continue; - switch (piece->getKind()) { case PathDiagnosticPiece::Call: { PathDiagnosticCallPiece *call = cast<PathDiagnosticCallPiece>(piece); @@ -210,9 +205,15 @@ static bool removeUnneededCalls(PathPieces &pieces, BugReport *R, return containsSomethingInteresting; } +/// Returns true if the given decl has been implicitly given a body, either by +/// the analyzer or by the compiler proper. +static bool hasImplicitBody(const Decl *D) { + assert(D); + return D->isImplicit() || !D->hasBody(); +} + /// Recursively scan through a path and make sure that all call pieces have -/// valid locations. Note that all other pieces with invalid locations should -/// have already been pruned out. +/// valid locations. static void adjustCallLocations(PathPieces &Pieces, PathDiagnosticLocation *LastCallLocation = 0) { for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E; ++I) { @@ -224,11 +225,10 @@ static void adjustCallLocations(PathPieces &Pieces, } if (LastCallLocation) { - if (!Call->callEnter.asLocation().isValid() || - Call->getCaller()->isImplicit()) + bool CallerIsImplicit = hasImplicitBody(Call->getCaller()); + if (CallerIsImplicit || !Call->callEnter.asLocation().isValid()) Call->callEnter = *LastCallLocation; - if (!Call->callReturn.asLocation().isValid() || - Call->getCaller()->isImplicit()) + if (CallerIsImplicit || !Call->callReturn.asLocation().isValid()) Call->callReturn = *LastCallLocation; } @@ -236,7 +236,7 @@ static void adjustCallLocations(PathPieces &Pieces, // it contains any informative diagnostics. PathDiagnosticLocation *ThisCallLocation; if (Call->callEnterWithin.asLocation().isValid() && - !Call->getCallee()->isImplicit()) + !hasImplicitBody(Call->getCallee())) ThisCallLocation = &Call->callEnterWithin; else ThisCallLocation = &Call->callEnter; @@ -246,6 +246,61 @@ static void adjustCallLocations(PathPieces &Pieces, } } +/// Remove edges in and out of C++ default initializer expressions. These are +/// for fields that have in-class initializers, as opposed to being initialized +/// explicitly in a constructor or braced list. +static void removeEdgesToDefaultInitializers(PathPieces &Pieces) { + for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) { + if (PathDiagnosticCallPiece *C = dyn_cast<PathDiagnosticCallPiece>(*I)) + removeEdgesToDefaultInitializers(C->path); + + if (PathDiagnosticMacroPiece *M = dyn_cast<PathDiagnosticMacroPiece>(*I)) + removeEdgesToDefaultInitializers(M->subPieces); + + if (PathDiagnosticControlFlowPiece *CF = + dyn_cast<PathDiagnosticControlFlowPiece>(*I)) { + const Stmt *Start = CF->getStartLocation().asStmt(); + const Stmt *End = CF->getEndLocation().asStmt(); + if (Start && isa<CXXDefaultInitExpr>(Start)) { + I = Pieces.erase(I); + continue; + } else if (End && isa<CXXDefaultInitExpr>(End)) { + PathPieces::iterator Next = llvm::next(I); + if (Next != E) { + if (PathDiagnosticControlFlowPiece *NextCF = + dyn_cast<PathDiagnosticControlFlowPiece>(*Next)) { + NextCF->setStartLocation(CF->getStartLocation()); + } + } + I = Pieces.erase(I); + continue; + } + } + + I++; + } +} + +/// Remove all pieces with invalid locations as these cannot be serialized. +/// We might have pieces with invalid locations as a result of inlining Body +/// Farm generated functions. +static void removePiecesWithInvalidLocations(PathPieces &Pieces) { + for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) { + if (PathDiagnosticCallPiece *C = dyn_cast<PathDiagnosticCallPiece>(*I)) + removePiecesWithInvalidLocations(C->path); + + if (PathDiagnosticMacroPiece *M = dyn_cast<PathDiagnosticMacroPiece>(*I)) + removePiecesWithInvalidLocations(M->subPieces); + + if (!(*I)->getLocation().isValid() || + !(*I)->getLocation().asLocation().isValid()) { + I = Pieces.erase(I); + continue; + } + I++; + } +} + //===----------------------------------------------------------------------===// // PathDiagnosticBuilder and its associated routines and helper objects. //===----------------------------------------------------------------------===// @@ -344,42 +399,40 @@ PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os, return Loc; } -static bool IsNested(const Stmt *S, ParentMap &PM) { +static const Stmt *getEnclosingParent(const Stmt *S, const ParentMap &PM) { if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S))) - return true; + return PM.getParentIgnoreParens(S); const Stmt *Parent = PM.getParentIgnoreParens(S); + if (!Parent) + return 0; - if (Parent) - switch (Parent->getStmtClass()) { - case Stmt::ForStmtClass: - case Stmt::DoStmtClass: - case Stmt::WhileStmtClass: - return true; - default: - break; - } + switch (Parent->getStmtClass()) { + case Stmt::ForStmtClass: + case Stmt::DoStmtClass: + case Stmt::WhileStmtClass: + case Stmt::ObjCForCollectionStmtClass: + case Stmt::CXXForRangeStmtClass: + return Parent; + default: + break; + } - return false; + return 0; } -PathDiagnosticLocation -PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { - assert(S && "Null Stmt *passed to getEnclosingStmtLocation"); - ParentMap &P = getParentMap(); - SourceManager &SMgr = getSourceManager(); - - while (IsNested(S, P)) { - const Stmt *Parent = P.getParentIgnoreParens(S); - - if (!Parent) - break; +static PathDiagnosticLocation +getEnclosingStmtLocation(const Stmt *S, SourceManager &SMgr, const ParentMap &P, + const LocationContext *LC, bool allowNestedContexts) { + if (!S) + return PathDiagnosticLocation(); + while (const Stmt *Parent = getEnclosingParent(S, P)) { switch (Parent->getStmtClass()) { case Stmt::BinaryOperatorClass: { const BinaryOperator *B = cast<BinaryOperator>(Parent); if (B->isLogicalOp()) - return PathDiagnosticLocation(S, SMgr, LC); + return PathDiagnosticLocation(allowNestedContexts ? B : S, SMgr, LC); break; } case Stmt::CompoundStmtClass: @@ -388,7 +441,7 @@ PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { case Stmt::ChooseExprClass: // Similar to '?' if we are referring to condition, just have the edge // point to the entire choose expression. - if (cast<ChooseExpr>(Parent)->getCond() == S) + if (allowNestedContexts || cast<ChooseExpr>(Parent)->getCond() == S) return PathDiagnosticLocation(Parent, SMgr, LC); else return PathDiagnosticLocation(S, SMgr, LC); @@ -396,10 +449,15 @@ PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { case Stmt::ConditionalOperatorClass: // For '?', if we are referring to condition, just have the edge point // to the entire '?' expression. - if (cast<AbstractConditionalOperator>(Parent)->getCond() == S) + if (allowNestedContexts || + cast<AbstractConditionalOperator>(Parent)->getCond() == S) return PathDiagnosticLocation(Parent, SMgr, LC); else return PathDiagnosticLocation(S, SMgr, LC); + case Stmt::CXXForRangeStmtClass: + if (cast<CXXForRangeStmt>(Parent)->getBody() == S) + return PathDiagnosticLocation(S, SMgr, LC); + break; case Stmt::DoStmtClass: return PathDiagnosticLocation(S, SMgr, LC); case Stmt::ForStmtClass: @@ -427,33 +485,16 @@ PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { assert(S && "Cannot have null Stmt for PathDiagnosticLocation"); - // Special case: DeclStmts can appear in for statement declarations, in which - // case the ForStmt is the context. - if (isa<DeclStmt>(S)) { - if (const Stmt *Parent = P.getParent(S)) { - switch (Parent->getStmtClass()) { - case Stmt::ForStmtClass: - case Stmt::ObjCForCollectionStmtClass: - return PathDiagnosticLocation(Parent, SMgr, LC); - default: - break; - } - } - } - else if (isa<BinaryOperator>(S)) { - // Special case: the binary operator represents the initialization - // code in a for statement (this can happen when the variable being - // initialized is an old variable. - if (const ForStmt *FS = - dyn_cast_or_null<ForStmt>(P.getParentIgnoreParens(S))) { - if (FS->getInit() == S) - return PathDiagnosticLocation(FS, SMgr, LC); - } - } - return PathDiagnosticLocation(S, SMgr, LC); } +PathDiagnosticLocation +PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { + assert(S && "Null Stmt passed to getEnclosingStmtLocation"); + return ::getEnclosingStmtLocation(S, getSourceManager(), getParentMap(), LC, + /*allowNestedContexts=*/false); +} + //===----------------------------------------------------------------------===// // "Visitors only" path diagnostic generation algorithm. //===----------------------------------------------------------------------===// @@ -1261,25 +1302,35 @@ static void reversePropagateInterestingSymbols(BugReport &R, // Functions for determining if a loop was executed 0 times. //===----------------------------------------------------------------------===// -/// Return true if the terminator is a loop and the destination is the -/// false branch. -static bool isLoopJumpPastBody(const Stmt *Term, const BlockEdge *BE) { +static bool isLoop(const Stmt *Term) { switch (Term->getStmtClass()) { case Stmt::ForStmtClass: case Stmt::WhileStmtClass: case Stmt::ObjCForCollectionStmtClass: - break; + case Stmt::CXXForRangeStmtClass: + return true; default: // Note that we intentionally do not include do..while here. return false; } +} - // Did we take the false branch? +static bool isJumpToFalseBranch(const BlockEdge *BE) { const CFGBlock *Src = BE->getSrc(); assert(Src->succ_size() == 2); return (*(Src->succ_begin()+1) == BE->getDst()); } +/// Return true if the terminator is a loop and the destination is the +/// false branch. +static bool isLoopJumpPastBody(const Stmt *Term, const BlockEdge *BE) { + if (!isLoop(Term)) + return false; + + // Did we take the false branch? + return isJumpToFalseBranch(BE); +} + static bool isContainedByStmt(ParentMap &PM, const Stmt *S, const Stmt *SubS) { while (SubS) { if (SubS == S) @@ -1306,6 +1357,15 @@ static const Stmt *getStmtBeforeCond(ParentMap &PM, const Stmt *Term, static bool isInLoopBody(ParentMap &PM, const Stmt *S, const Stmt *Term) { const Stmt *LoopBody = 0; switch (Term->getStmtClass()) { + case Stmt::CXXForRangeStmtClass: { + const CXXForRangeStmt *FR = cast<CXXForRangeStmt>(Term); + if (isContainedByStmt(PM, FR->getInc(), S)) + return true; + if (isContainedByStmt(PM, FR->getLoopVarStmt(), S)) + return true; + LoopBody = FR->getBody(); + break; + } case Stmt::ForStmtClass: { const ForStmt *FS = cast<ForStmt>(Term); if (isContainedByStmt(PM, FS->getInc(), S)) @@ -1539,17 +1599,17 @@ static void addEdgeToPath(PathPieces &path, return; SourceLocation NewLocL = NewLoc.asLocation(); - if (NewLocL.isInvalid() || NewLocL.isMacroID()) + if (NewLocL.isInvalid()) return; - if (!PrevLoc.isValid()) { + if (!PrevLoc.isValid() || !PrevLoc.asLocation().isValid()) { PrevLoc = NewLoc; return; } - // FIXME: ignore intra-macro edges for now. - if (NewLoc.asLocation().getExpansionLoc() == - PrevLoc.asLocation().getExpansionLoc()) + // Ignore self-edges, which occur when there are multiple nodes at the same + // statement. + if (NewLoc.asStmt() && NewLoc.asStmt() == PrevLoc.asStmt()) return; path.push_front(new PathDiagnosticControlFlowPiece(NewLoc, @@ -1557,6 +1617,23 @@ static void addEdgeToPath(PathPieces &path, PrevLoc = NewLoc; } +/// A customized wrapper for CFGBlock::getTerminatorCondition() +/// which returns the element for ObjCForCollectionStmts. +static const Stmt *getTerminatorCondition(const CFGBlock *B) { + const Stmt *S = B->getTerminatorCondition(); + if (const ObjCForCollectionStmt *FS = + dyn_cast_or_null<ObjCForCollectionStmt>(S)) + return FS->getElement(); + return S; +} + +static const char StrEnteringLoop[] = "Entering loop body"; +static const char StrLoopBodyZero[] = "Loop body executed 0 times"; +static const char StrLoopRangeEmpty[] = + "Loop body skipped when range is empty"; +static const char StrLoopCollectionEmpty[] = + "Loop body skipped when collection is empty"; + static bool GenerateAlternateExtensivePathDiagnostic(PathDiagnostic& PD, PathDiagnosticBuilder &PDB, @@ -1569,35 +1646,81 @@ GenerateAlternateExtensivePathDiagnostic(PathDiagnostic& PD, StackDiagVector CallStack; InterestingExprs IE; - // Record the last location for a given visited stack frame. - llvm::DenseMap<const StackFrameContext *, PathDiagnosticLocation> - PrevLocMap; + PathDiagnosticLocation PrevLoc = PD.getLocation(); const ExplodedNode *NextNode = N->getFirstPred(); while (NextNode) { N = NextNode; NextNode = N->getFirstPred(); ProgramPoint P = N->getLocation(); - const LocationContext *LC = N->getLocationContext(); - assert(!LCM[&PD.getActivePath()] || LCM[&PD.getActivePath()] == LC); - LCM[&PD.getActivePath()] = LC; - PathDiagnosticLocation &PrevLoc = PrevLocMap[LC->getCurrentStackFrame()]; do { - if (Optional<PostStmt> PS = P.getAs<PostStmt>()) { - // For expressions, make sure we propagate the - // interesting symbols correctly. - if (const Expr *Ex = PS->getStmtAs<Expr>()) - reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, - N->getState().getPtr(), Ex, - N->getLocationContext()); + // 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<CallEnter> CE = P.getAs<CallEnter>()) { + // Add an edge to the start of the function. + const StackFrameContext *CalleeLC = CE->getCalleeContext(); + const Decl *D = CalleeLC->getDecl(); + 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().getPtr(); + C = cast<PathDiagnosticCallPiece>(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() == C); + LCM[&PD.getActivePath()] = 0; + + // Record the location context mapping for the path within + // the call. + assert(LCM[&C->path] == 0 || + 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(); - PathDiagnosticLocation L = - PathDiagnosticLocation(PS->getStmt(), SM, LC); - addEdgeToPath(PD.getActivePath(), PrevLoc, L, LC); + 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<CallExitEnd> CE = P.getAs<CallExitEnd>()) { const Stmt *S = CE->getCalleeContext()->getCallSite(); @@ -1617,7 +1740,9 @@ GenerateAlternateExtensivePathDiagnostic(PathDiagnostic& PD, LCM[&C->path] = CE->getCalleeContext(); // Add the edge to the return site. - addEdgeToPath(PD.getActivePath(), PrevLoc, C->callReturn, LC); + addEdgeToPath(PD.getActivePath(), PrevLoc, C->callReturn, PDB.LC); + PD.getActivePath().push_front(C); + PrevLoc.invalidate(); // Make the contents of the call the active path for now. PD.pushActivePath(&C->path); @@ -1625,33 +1750,21 @@ GenerateAlternateExtensivePathDiagnostic(PathDiagnostic& PD, break; } - // 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<CallEnter> CE = P.getAs<CallEnter>()) { - // Add an edge to the start of the function. - const Decl *D = CE->getCalleeContext()->getDecl(); - addEdgeToPath(PD.getActivePath(), PrevLoc, - PathDiagnosticLocation::createBegin(D, SM), LC); - - // Did we visit an entire call? - bool VisitedEntireCall = PD.isWithinCall(); - PD.popActivePath(); - - PathDiagnosticCallPiece *C; - if (VisitedEntireCall) { - C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front()); - } else { - const Decl *Caller = CE->getLocationContext()->getDecl(); - C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); - LCM[&C->path] = CE->getCalleeContext(); - } - C->setCallee(*CE, SM); + if (Optional<PostStmt> PS = P.getAs<PostStmt>()) { + // For expressions, make sure we propagate the + // interesting symbols correctly. + if (const Expr *Ex = PS->getStmtAs<Expr>()) + reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE, + N->getState().getPtr(), Ex, + N->getLocationContext()); - if (!CallStack.empty()) { - assert(CallStack.back().first == C); - CallStack.pop_back(); + // 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<ObjCForCollectionStmt>(PS->getStmt())) { + PathDiagnosticLocation L = + PathDiagnosticLocation(PS->getStmt(), SM, PDB.LC); + addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); } break; } @@ -1673,47 +1786,76 @@ GenerateAlternateExtensivePathDiagnostic(PathDiagnostic& PD, // 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 = NULL; + const Stmt *Body = NULL; if (const ForStmt *FS = dyn_cast<ForStmt>(Loop)) - CS = dyn_cast<CompoundStmt>(FS->getBody()); + Body = FS->getBody(); else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop)) - CS = dyn_cast<CompoundStmt>(WS->getBody()); + Body = WS->getBody(); + else if (const ObjCForCollectionStmt *OFS = + dyn_cast<ObjCForCollectionStmt>(Loop)) { + Body = OFS->getBody(); + } else if (const CXXForRangeStmt *FRS = + dyn_cast<CXXForRangeStmt>(Loop)) { + Body = FRS->getBody(); + } + // do-while statements are explicitly excluded here PathDiagnosticEventPiece *p = new PathDiagnosticEventPiece(L, "Looping back to the head " "of the loop"); p->setPrunable(true); - addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), LC); + addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC); PD.getActivePath().push_front(p); - if (CS) { + if (const CompoundStmt *CS = dyn_cast_or_null<CompoundStmt>(Body)) { addEdgeToPath(PD.getActivePath(), PrevLoc, - PathDiagnosticLocation::createEndBrace(CS, SM), LC); + 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 (isLoopJumpPastBody(Term, &*BE) && - !isInLoopBody(PM, - getStmtBeforeCond(PM, - BSrc->getTerminatorCondition(), - N), - Term)) - { + if (isLoop(Term)) { + const Stmt *TermCond = getTerminatorCondition(BSrc); + bool IsInLoopBody = + isInLoopBody(PM, getStmtBeforeCond(PM, TermCond, N), Term); + + const char *str = 0; + + if (isJumpToFalseBranch(&*BE)) { + if (!IsInLoopBody) { + if (isa<ObjCForCollectionStmt>(Term)) { + str = StrLoopCollectionEmpty; + } else if (isa<CXXForRangeStmt>(Term)) { + str = StrLoopRangeEmpty; + } else { + str = StrLoopBodyZero; + } + } + } else { + str = StrEnteringLoop; + } + + if (str) { + PathDiagnosticLocation L(TermCond ? TermCond : Term, SM, PDB.LC); + PathDiagnosticEventPiece *PE = + new PathDiagnosticEventPiece(L, str); + PE->setPrunable(true); + addEdgeToPath(PD.getActivePath(), PrevLoc, + PE->getLocation(), PDB.LC); + PD.getActivePath().push_front(PE); + } + } else if (isa<BreakStmt>(Term) || isa<ContinueStmt>(Term) || + isa<GotoStmt>(Term)) { PathDiagnosticLocation L(Term, SM, PDB.LC); - PathDiagnosticEventPiece *PE = - new PathDiagnosticEventPiece(L, "Loop body executed 0 times"); - PE->setPrunable(true); - addEdgeToPath(PD.getActivePath(), PrevLoc, - PE->getLocation(), LC); - PD.getActivePath().push_front(PE); + addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC); } } break; @@ -1728,32 +1870,61 @@ GenerateAlternateExtensivePathDiagnostic(PathDiagnostic& PD, E = visitors.end(); I != E; ++I) { if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *report)) { - addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), LC); + addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC); PD.getActivePath().push_front(p); updateStackPiecesWithMessage(p, CallStack); } } } + // Add an edge to the start of the function. + // We'll prune it out later, but it helps make diagnostics more uniform. + const StackFrameContext *CalleeLC = PDB.LC->getCurrentStackFrame(); + const Decl *D = CalleeLC->getDecl(); + addEdgeToPath(PD.getActivePath(), PrevLoc, + PathDiagnosticLocation::createBegin(D, SM), + CalleeLC); + return report->isValid(); } -const Stmt *getLocStmt(PathDiagnosticLocation L) { +static const Stmt *getLocStmt(PathDiagnosticLocation L) { if (!L.isValid()) return 0; return L.asStmt(); } -const Stmt *getStmtParent(const Stmt *S, ParentMap &PM) { +static const Stmt *getStmtParent(const Stmt *S, const ParentMap &PM) { if (!S) return 0; - return PM.getParentIgnoreParens(S); + + while (true) { + S = PM.getParentIgnoreParens(S); + + if (!S) + break; + + if (isa<ExprWithCleanups>(S) || + isa<CXXBindTemporaryExpr>(S) || + isa<SubstNonTypeTemplateParmExpr>(S)) + continue; + + break; + } + + return S; } -#if 0 static bool isConditionForTerminator(const Stmt *S, const Stmt *Cond) { - // Note that we intentionally to do not handle || and && here. switch (S->getStmtClass()) { + case Stmt::BinaryOperatorClass: { + const BinaryOperator *BO = cast<BinaryOperator>(S); + if (!BO->isLogicalOp()) + return false; + return BO->getLHS() == Cond || BO->getRHS() == Cond; + } + case Stmt::IfStmtClass: + return cast<IfStmt>(S)->getCond() == Cond; case Stmt::ForStmtClass: return cast<ForStmt>(S)->getCond() == Cond; case Stmt::WhileStmtClass: @@ -1768,46 +1939,410 @@ static bool isConditionForTerminator(const Stmt *S, const Stmt *Cond) { return cast<SwitchStmt>(S)->getCond() == Cond; case Stmt::BinaryConditionalOperatorClass: return cast<BinaryConditionalOperator>(S)->getCond() == Cond; - case Stmt::ConditionalOperatorClass: - return cast<ConditionalOperator>(S)->getCond() == Cond; + case Stmt::ConditionalOperatorClass: { + const ConditionalOperator *CO = cast<ConditionalOperator>(S); + return CO->getCond() == Cond || + CO->getLHS() == Cond || + CO->getRHS() == Cond; + } case Stmt::ObjCForCollectionStmtClass: return cast<ObjCForCollectionStmt>(S)->getElement() == Cond; + case Stmt::CXXForRangeStmtClass: { + const CXXForRangeStmt *FRS = cast<CXXForRangeStmt>(S); + return FRS->getCond() == Cond || FRS->getRangeInit() == Cond; + } default: return false; } } -#endif -typedef llvm::DenseSet<const PathDiagnosticControlFlowPiece *> - ControlFlowBarrierSet; +static bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL) { + if (const ForStmt *FS = dyn_cast<ForStmt>(FL)) + return FS->getInc() == S || FS->getInit() == S; + if (const CXXForRangeStmt *FRS = dyn_cast<CXXForRangeStmt>(FL)) + return FRS->getInc() == S || FRS->getRangeStmt() == S || + FRS->getLoopVarStmt() || FRS->getRangeInit() == S; + return false; +} typedef llvm::DenseSet<const PathDiagnosticCallPiece *> OptimizedCallsSet; -static bool isBarrier(ControlFlowBarrierSet &CFBS, - const PathDiagnosticControlFlowPiece *P) { - return CFBS.count(P); +/// Adds synthetic edges from top-level statements to their subexpressions. +/// +/// This avoids a "swoosh" effect, where an edge from a top-level statement A +/// points to a sub-expression B.1 that's not at the start of B. In these cases, +/// we'd like to see an edge from A to B, then another one from B to B.1. +static void addContextEdges(PathPieces &pieces, SourceManager &SM, + const ParentMap &PM, const LocationContext *LCtx) { + PathPieces::iterator Prev = pieces.end(); + for (PathPieces::iterator I = pieces.begin(), E = Prev; I != E; + Prev = I, ++I) { + PathDiagnosticControlFlowPiece *Piece = + dyn_cast<PathDiagnosticControlFlowPiece>(*I); + + if (!Piece) + continue; + + PathDiagnosticLocation SrcLoc = Piece->getStartLocation(); + SmallVector<PathDiagnosticLocation, 4> SrcContexts; + + PathDiagnosticLocation NextSrcContext = SrcLoc; + const Stmt *InnerStmt = 0; + while (NextSrcContext.isValid() && NextSrcContext.asStmt() != InnerStmt) { + SrcContexts.push_back(NextSrcContext); + InnerStmt = NextSrcContext.asStmt(); + NextSrcContext = getEnclosingStmtLocation(InnerStmt, SM, PM, LCtx, + /*allowNested=*/true); + } + + // Repeatedly split the edge as necessary. + // This is important for nested logical expressions (||, &&, ?:) where we + // want to show all the levels of context. + while (true) { + const Stmt *Dst = getLocStmt(Piece->getEndLocation()); + + // We are looking at an edge. Is the destination within a larger + // expression? + PathDiagnosticLocation DstContext = + getEnclosingStmtLocation(Dst, SM, PM, LCtx, /*allowNested=*/true); + if (!DstContext.isValid() || DstContext.asStmt() == Dst) + break; + + // If the source is in the same context, we're already good. + if (std::find(SrcContexts.begin(), SrcContexts.end(), DstContext) != + SrcContexts.end()) + break; + + // Update the subexpression node to point to the context edge. + Piece->setStartLocation(DstContext); + + // Try to extend the previous edge if it's at the same level as the source + // context. + if (Prev != E) { + PathDiagnosticControlFlowPiece *PrevPiece = + dyn_cast<PathDiagnosticControlFlowPiece>(*Prev); + + if (PrevPiece) { + if (const Stmt *PrevSrc = getLocStmt(PrevPiece->getStartLocation())) { + const Stmt *PrevSrcParent = getStmtParent(PrevSrc, PM); + if (PrevSrcParent == getStmtParent(getLocStmt(DstContext), PM)) { + PrevPiece->setEndLocation(DstContext); + break; + } + } + } + } + + // Otherwise, split the current edge into a context edge and a + // subexpression edge. Note that the context statement may itself have + // context. + Piece = new PathDiagnosticControlFlowPiece(SrcLoc, DstContext); + I = pieces.insert(I, Piece); + } + } +} + +/// \brief Move edges from a branch condition to a branch target +/// when the condition is simple. +/// +/// This restructures some of the work of addContextEdges. That function +/// creates edges this may destroy, but they work together to create a more +/// aesthetically set of edges around branches. After the call to +/// addContextEdges, we may have (1) an edge to the branch, (2) an edge from +/// the branch to the branch condition, and (3) an edge from the branch +/// condition to the branch target. We keep (1), but may wish to remove (2) +/// and move the source of (3) to the branch if the branch condition is simple. +/// +static void simplifySimpleBranches(PathPieces &pieces) { + for (PathPieces::iterator I = pieces.begin(), E = pieces.end(); I != E; ++I) { + + PathDiagnosticControlFlowPiece *PieceI = + dyn_cast<PathDiagnosticControlFlowPiece>(*I); + + if (!PieceI) + continue; + + const Stmt *s1Start = getLocStmt(PieceI->getStartLocation()); + const Stmt *s1End = getLocStmt(PieceI->getEndLocation()); + + if (!s1Start || !s1End) + continue; + + PathPieces::iterator NextI = I; ++NextI; + if (NextI == E) + break; + + PathDiagnosticControlFlowPiece *PieceNextI = 0; + + while (true) { + if (NextI == E) + break; + + PathDiagnosticEventPiece *EV = dyn_cast<PathDiagnosticEventPiece>(*NextI); + if (EV) { + StringRef S = EV->getString(); + if (S == StrEnteringLoop || S == StrLoopBodyZero || + S == StrLoopCollectionEmpty || S == StrLoopRangeEmpty) { + ++NextI; + continue; + } + break; + } + + PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); + break; + } + + if (!PieceNextI) + continue; + + const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation()); + const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation()); + + if (!s2Start || !s2End || s1End != s2Start) + continue; + + // We only perform this transformation for specific branch kinds. + // We don't want to do this for do..while, for example. + if (!(isa<ForStmt>(s1Start) || isa<WhileStmt>(s1Start) || + isa<IfStmt>(s1Start) || isa<ObjCForCollectionStmt>(s1Start) || + isa<CXXForRangeStmt>(s1Start))) + continue; + + // Is s1End the branch condition? + if (!isConditionForTerminator(s1Start, s1End)) + continue; + + // Perform the hoisting by eliminating (2) and changing the start + // location of (3). + PieceNextI->setStartLocation(PieceI->getStartLocation()); + I = pieces.erase(I); + } +} + +/// Returns the number of bytes in the given (character-based) SourceRange. +/// +/// If the locations in the range are not on the same line, returns None. +/// +/// Note that this does not do a precise user-visible character or column count. +static Optional<size_t> getLengthOnSingleLine(SourceManager &SM, + SourceRange Range) { + SourceRange ExpansionRange(SM.getExpansionLoc(Range.getBegin()), + SM.getExpansionRange(Range.getEnd()).second); + + FileID FID = SM.getFileID(ExpansionRange.getBegin()); + if (FID != SM.getFileID(ExpansionRange.getEnd())) + return None; + + bool Invalid; + const llvm::MemoryBuffer *Buffer = SM.getBuffer(FID, &Invalid); + if (Invalid) + return None; + + unsigned BeginOffset = SM.getFileOffset(ExpansionRange.getBegin()); + unsigned EndOffset = SM.getFileOffset(ExpansionRange.getEnd()); + StringRef Snippet = Buffer->getBuffer().slice(BeginOffset, EndOffset); + + // We're searching the raw bytes of the buffer here, which might include + // escaped newlines and such. That's okay; we're trying to decide whether the + // SourceRange is covering a large or small amount of space in the user's + // editor. + if (Snippet.find_first_of("\r\n") != StringRef::npos) + return None; + + // This isn't Unicode-aware, but it doesn't need to be. + return Snippet.size(); +} + +/// \sa getLengthOnSingleLine(SourceManager, SourceRange) +static Optional<size_t> getLengthOnSingleLine(SourceManager &SM, + const Stmt *S) { + return getLengthOnSingleLine(SM, S->getSourceRange()); +} + +/// Eliminate two-edge cycles created by addContextEdges(). +/// +/// Once all the context edges are in place, there are plenty of cases where +/// there's a single edge from a top-level statement to a subexpression, +/// followed by a single path note, and then a reverse edge to get back out to +/// the top level. If the statement is simple enough, the subexpression edges +/// just add noise and make it harder to understand what's going on. +/// +/// This function only removes edges in pairs, because removing only one edge +/// might leave other edges dangling. +/// +/// This will not remove edges in more complicated situations: +/// - if there is more than one "hop" leading to or from a subexpression. +/// - if there is an inlined call between the edges instead of a single event. +/// - if the whole statement is large enough that having subexpression arrows +/// might be helpful. +static void removeContextCycles(PathPieces &Path, SourceManager &SM, + ParentMap &PM) { + for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) { + // Pattern match the current piece and its successor. + PathDiagnosticControlFlowPiece *PieceI = + dyn_cast<PathDiagnosticControlFlowPiece>(*I); + + if (!PieceI) { + ++I; + continue; + } + + const Stmt *s1Start = getLocStmt(PieceI->getStartLocation()); + const Stmt *s1End = getLocStmt(PieceI->getEndLocation()); + + PathPieces::iterator NextI = I; ++NextI; + if (NextI == E) + break; + + PathDiagnosticControlFlowPiece *PieceNextI = + dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); + + if (!PieceNextI) { + if (isa<PathDiagnosticEventPiece>(*NextI)) { + ++NextI; + if (NextI == E) + break; + PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(*NextI); + } + + if (!PieceNextI) { + ++I; + continue; + } + } + + const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation()); + const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation()); + + if (s1Start && s2Start && s1Start == s2End && s2Start == s1End) { + const size_t MAX_SHORT_LINE_LENGTH = 80; + Optional<size_t> s1Length = getLengthOnSingleLine(SM, s1Start); + if (s1Length && *s1Length <= MAX_SHORT_LINE_LENGTH) { + Optional<size_t> s2Length = getLengthOnSingleLine(SM, s2Start); + if (s2Length && *s2Length <= MAX_SHORT_LINE_LENGTH) { + Path.erase(I); + I = Path.erase(NextI); + continue; + } + } + } + + ++I; + } +} + +/// \brief Return true if X is contained by Y. +static bool lexicalContains(ParentMap &PM, + const Stmt *X, + const Stmt *Y) { + while (X) { + if (X == Y) + return true; + X = PM.getParent(X); + } + return false; +} + +// Remove short edges on the same line less than 3 columns in difference. +static void removePunyEdges(PathPieces &path, + SourceManager &SM, + ParentMap &PM) { + + bool erased = false; + + for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; + erased ? I : ++I) { + + erased = false; + + PathDiagnosticControlFlowPiece *PieceI = + dyn_cast<PathDiagnosticControlFlowPiece>(*I); + + if (!PieceI) + continue; + + const Stmt *start = getLocStmt(PieceI->getStartLocation()); + const Stmt *end = getLocStmt(PieceI->getEndLocation()); + + if (!start || !end) + continue; + + const Stmt *endParent = PM.getParent(end); + if (!endParent) + continue; + + if (isConditionForTerminator(end, endParent)) + continue; + + SourceLocation FirstLoc = start->getLocStart(); + SourceLocation SecondLoc = end->getLocStart(); + + if (!SM.isWrittenInSameFile(FirstLoc, SecondLoc)) + continue; + if (SM.isBeforeInTranslationUnit(SecondLoc, FirstLoc)) + std::swap(SecondLoc, FirstLoc); + + SourceRange EdgeRange(FirstLoc, SecondLoc); + Optional<size_t> ByteWidth = getLengthOnSingleLine(SM, EdgeRange); + + // If the statements are on different lines, continue. + if (!ByteWidth) + continue; + + const size_t MAX_PUNY_EDGE_LENGTH = 2; + if (*ByteWidth <= MAX_PUNY_EDGE_LENGTH) { + // FIXME: There are enough /bytes/ between the endpoints of the edge, but + // there might not be enough /columns/. A proper user-visible column count + // is probably too expensive, though. + I = path.erase(I); + erased = true; + continue; + } + } +} + +static void removeIdenticalEvents(PathPieces &path) { + for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) { + PathDiagnosticEventPiece *PieceI = + dyn_cast<PathDiagnosticEventPiece>(*I); + + if (!PieceI) + continue; + + PathPieces::iterator NextI = I; ++NextI; + if (NextI == E) + return; + + PathDiagnosticEventPiece *PieceNextI = + dyn_cast<PathDiagnosticEventPiece>(*NextI); + + if (!PieceNextI) + continue; + + // Erase the second piece if it has the same exact message text. + if (PieceI->getString() == PieceNextI->getString()) { + path.erase(NextI); + } + } } static bool optimizeEdges(PathPieces &path, SourceManager &SM, - ControlFlowBarrierSet &CFBS, OptimizedCallsSet &OCS, LocationContextMap &LCM) { bool hasChanges = false; const LocationContext *LC = LCM[&path]; assert(LC); - bool isFirst = true; + ParentMap &PM = LC->getParentMap(); for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) { - bool wasFirst = isFirst; - isFirst = false; - // Optimize subpaths. if (PathDiagnosticCallPiece *CallI = dyn_cast<PathDiagnosticCallPiece>(*I)){ // Record the fact that a call has been optimized so we only do the // effort once. if (!OCS.count(CallI)) { - while (optimizeEdges(CallI->path, SM, CFBS, OCS, LCM)) {} + while (optimizeEdges(CallI->path, SM, OCS, LCM)) {} OCS.insert(CallI); } ++I; @@ -1823,33 +2358,11 @@ static bool optimizeEdges(PathPieces &path, SourceManager &SM, continue; } - ParentMap &PM = LC->getParentMap(); const Stmt *s1Start = getLocStmt(PieceI->getStartLocation()); const Stmt *s1End = getLocStmt(PieceI->getEndLocation()); const Stmt *level1 = getStmtParent(s1Start, PM); const Stmt *level2 = getStmtParent(s1End, PM); - if (wasFirst) { -#if 0 - // Apply the "first edge" case for Rule V. here. - if (s1Start && level1 && isConditionForTerminator(level1, s1Start)) { - PathDiagnosticLocation NewLoc(level2, SM, LC); - PieceI->setStartLocation(NewLoc); - CFBS.insert(PieceI); - return true; - } -#endif - // Apply the "first edge" case for Rule III. here. - if (!isBarrier(CFBS, PieceI) && - level1 && level2 && level2 == PM.getParent(level1)) { - path.erase(I); - // Since we are erasing the current edge at the start of the - // path, just return now so we start analyzing the start of the path - // again. - return true; - } - } - PathPieces::iterator NextI = I; ++NextI; if (NextI == E) break; @@ -1891,101 +2404,137 @@ static bool optimizeEdges(PathPieces &path, SourceManager &SM, // Rule II. // - // If we have two consecutive control edges where we decend to a - // subexpression and then pop out merge them. + // Eliminate edges between subexpressions and parent expressions + // when the subexpression is consumed. // // NOTE: this will be limited later in cases where we add barriers // to prevent this optimization. // - // For example: - // - // (1.1 -> 1.1.1) -> (1.1.1 -> 1.2) becomes (1.1 -> 1.2). - if (level1 && level2 && - level1 == level4 && - level2 == level3 && PM.getParentIgnoreParens(level2) == level1) { - PieceI->setEndLocation(PieceNextI->getEndLocation()); - path.erase(NextI); - hasChanges = true; - continue; - } + if (s1End && s1End == s2Start && level2) { + bool removeEdge = false; + // Remove edges into the increment or initialization of a + // loop that have no interleaving event. This means that + // they aren't interesting. + if (isIncrementOrInitInForLoop(s1End, level2)) + removeEdge = true; + // Next only consider edges that are not anchored on + // the condition of a terminator. This are intermediate edges + // that we might want to trim. + else if (!isConditionForTerminator(level2, s1End)) { + // Trim edges on expressions that are consumed by + // the parent expression. + if (isa<Expr>(s1End) && PM.isConsumedExpr(cast<Expr>(s1End))) { + removeEdge = true; + } + // Trim edges where a lexical containment doesn't exist. + // For example: + // + // X -> Y -> Z + // + // If 'Z' lexically contains Y (it is an ancestor) and + // 'X' does not lexically contain Y (it is a descendant OR + // it has no lexical relationship at all) then trim. + // + // This can eliminate edges where we dive into a subexpression + // and then pop back out, etc. + else if (s1Start && s2End && + lexicalContains(PM, s2Start, s2End) && + !lexicalContains(PM, s1End, s1Start)) { + removeEdge = true; + } + // Trim edges from a subexpression back to the top level if the + // subexpression is on a different line. + // + // A.1 -> A -> B + // becomes + // A.1 -> B + // + // These edges just look ugly and don't usually add anything. + else if (s1Start && s2End && + lexicalContains(PM, s1Start, s1End)) { + SourceRange EdgeRange(PieceI->getEndLocation().asLocation(), + PieceI->getStartLocation().asLocation()); + if (!getLengthOnSingleLine(SM, EdgeRange).hasValue()) + removeEdge = true; + } + } - // Rule III. - // - // Eliminate unnecessary edges where we descend to a subexpression from - // a statement at the same level as our parent. - // - // NOTE: this will be limited later in cases where we add barriers - // to prevent this optimization. - // - // For example: - // - // (1.1 -> 1.1.1) -> (1.1.1 -> X) becomes (1.1 -> X). - // - if (level1 && level2 && level1 == PM.getParentIgnoreParens(level2)) { - PieceI->setEndLocation(PieceNextI->getEndLocation()); - path.erase(NextI); - hasChanges = true; - continue; + if (removeEdge) { + PieceI->setEndLocation(PieceNextI->getEndLocation()); + path.erase(NextI); + hasChanges = true; + continue; + } } - // Rule IV. + // Optimize edges for ObjC fast-enumeration loops. // - // Eliminate unnecessary edges where we ascend from a subexpression to - // a statement at the same level as our parent. + // (X -> collection) -> (collection -> element) // - // NOTE: this will be limited later in cases where we add barriers - // to prevent this optimization. - // - // For example: + // becomes: // - // (X -> 1.1.1) -> (1.1.1 -> 1.1) becomes (X -> 1.1). - // [first edge] (1.1.1 -> 1.1) -> eliminate - // - if (level2 && level4 && level2 == level3 && level4 == PM.getParent(level2)){ - PieceI->setEndLocation(PieceNextI->getEndLocation()); - path.erase(NextI); - hasChanges = true; - continue; - } -#if 0 - // Rule V. - // - // Replace terminator conditions with terminators when the condition - // itself has no control-flow. - // - // For example: - // - // (X -> condition) -> (condition -> Y) becomes (X -> term) -> (term -> Y) - // [first edge] (condition -> Y) becomes (term -> Y) - // - // This applies to 'if', 'for', 'while', 'do .. while', 'switch'... - // - if (!isBarrier(CFBS, PieceNextI) && - s1End && s1End == s2Start && level2) { - if (isConditionForTerminator(level2, s1End)) { - PathDiagnosticLocation NewLoc(level2, SM, LC); - PieceI->setEndLocation(NewLoc); - PieceNextI->setStartLocation(NewLoc); - CFBS.insert(PieceI); + // (X -> element) + if (s1End == s2Start) { + const ObjCForCollectionStmt *FS = + dyn_cast_or_null<ObjCForCollectionStmt>(level3); + if (FS && FS->getCollection()->IgnoreParens() == s2Start && + s2End == FS->getElement()) { + PieceI->setEndLocation(PieceNextI->getEndLocation()); + path.erase(NextI); hasChanges = true; continue; } - } -#endif // No changes at this index? Move to the next one. ++I; } - // No changes. + if (!hasChanges) { + // Adjust edges into subexpressions to make them more uniform + // and aesthetically pleasing. + addContextEdges(path, SM, PM, LC); + // Remove "cyclical" edges that include one or more context edges. + removeContextCycles(path, SM, PM); + // Hoist edges originating from branch conditions to branches + // for simple branches. + simplifySimpleBranches(path); + // Remove any puny edges left over after primary optimization pass. + removePunyEdges(path, SM, PM); + // Remove identical events. + removeIdenticalEvents(path); + } + return hasChanges; } +/// Drop the very first edge in a path, which should be a function entry edge. +/// +/// If the first edge is not a function entry edge (say, because the first +/// statement had an invalid source location), this function does nothing. +// FIXME: We should just generate invalid edges anyway and have the optimizer +// deal with them. +static void dropFunctionEntryEdge(PathPieces &Path, + LocationContextMap &LCM, + SourceManager &SM) { + const PathDiagnosticControlFlowPiece *FirstEdge = + dyn_cast<PathDiagnosticControlFlowPiece>(Path.front()); + if (!FirstEdge) + return; + + const Decl *D = LCM[&Path]->getDecl(); + PathDiagnosticLocation EntryLoc = PathDiagnosticLocation::createBegin(D, SM); + if (FirstEdge->getStartLocation() != EntryLoc) + return; + + Path.pop_front(); +} + + //===----------------------------------------------------------------------===// // Methods for BugType and subclasses. //===----------------------------------------------------------------------===// -BugType::~BugType() { } +void BugType::anchor() { } void BugType::FlushReports(BugReporter &BR) {} @@ -2148,10 +2697,8 @@ void BugReport::pushInterestingSymbolsAndRegions() { } void BugReport::popInterestingSymbolsAndRegions() { - delete interestingSymbols.back(); - interestingSymbols.pop_back(); - delete interestingRegions.back(); - interestingRegions.pop_back(); + delete interestingSymbols.pop_back_val(); + delete interestingRegions.pop_back_val(); } const Stmt *BugReport::getStmt() const { @@ -2238,7 +2785,7 @@ void BugReporter::FlushReports() { SmallVector<const BugType*, 16> bugTypes; for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I) bugTypes.push_back(*I); - for (SmallVector<const BugType*, 16>::iterator + for (SmallVectorImpl<const BugType *>::iterator I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I) const_cast<BugType*>(*I)->FlushReports(*this); @@ -2561,8 +3108,8 @@ bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD, PathGenerationScheme ActiveScheme = PC.getGenerationScheme(); if (ActiveScheme == PathDiagnosticConsumer::Extensive) { - AnalyzerOptions &options = getEngine().getAnalysisManager().options; - if (options.getBooleanOption("path-diagnostics-alternate", false)) { + AnalyzerOptions &options = getAnalyzerOptions(); + if (options.getBooleanOption("path-diagnostics-alternate", true)) { ActiveScheme = PathDiagnosticConsumer::AlternateExtensive; } } @@ -2654,24 +3201,35 @@ bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD, // Finally, prune the diagnostic path of uninteresting stuff. if (!PD.path.empty()) { - // Remove messages that are basically the same. - removeRedundantMsgs(PD.getMutablePieces()); - - if (R->shouldPrunePath() && - getEngine().getAnalysisManager().options.shouldPrunePaths()) { + if (R->shouldPrunePath() && getAnalyzerOptions().shouldPrunePaths()) { bool stillHasNotes = removeUnneededCalls(PD.getMutablePieces(), R, LCM); assert(stillHasNotes); (void)stillHasNotes; } + // Redirect all call pieces to have valid locations. adjustCallLocations(PD.getMutablePieces()); + removePiecesWithInvalidLocations(PD.getMutablePieces()); if (ActiveScheme == PathDiagnosticConsumer::AlternateExtensive) { - ControlFlowBarrierSet CFBS; + SourceManager &SM = getSourceManager(); + + // Reduce the number of edges from a very conservative set + // to an aesthetically pleasing subset that conveys the + // necessary information. OptimizedCallsSet OCS; - while (optimizeEdges(PD.getMutablePieces(), getSourceManager(), CFBS, - OCS, LCM)) {} + while (optimizeEdges(PD.getMutablePieces(), SM, OCS, LCM)) {} + + // Drop the very first function-entry edge. It's not really necessary + // for top-level functions. + dropFunctionEntryEdge(PD.getMutablePieces(), LCM, SM); } + + // Remove messages that are basically the same, and edges that may not + // make sense. + // We have to do this after edge optimization in the Extensive mode. + removeRedundantMsgs(PD.getMutablePieces()); + removeEdgesToDefaultInitializers(PD.getMutablePieces()); } // We found a report and didn't suppress it. @@ -2689,6 +3247,25 @@ void BugReporter::Register(BugType *BT) { } void BugReporter::emitReport(BugReport* R) { + // Defensive checking: throw the bug away if it comes from a BodyFarm- + // generated body. We do this very early because report processing relies + // on the report's location being valid. + // FIXME: Valid bugs can occur in BodyFarm-generated bodies, so really we + // need to just find a reasonable location like we do later on with the path + // pieces. + if (const ExplodedNode *E = R->getErrorNode()) { + const LocationContext *LCtx = E->getLocationContext(); + if (LCtx->getAnalysisDeclContext()->isBodyAutosynthesized()) + return; + } + + bool ValidSourceLoc = R->getLocation(getSourceManager()).isValid(); + assert(ValidSourceLoc); + // If we mess up in a release build, we'd still prefer to just drop the bug + // instead of trying to go on. + if (!ValidSourceLoc) + return; + // Compute the bug report's hash to determine its equivalence class. llvm::FoldingSetNodeID ID; R->Profile(ID); @@ -2865,6 +3442,12 @@ void BugReporter::FlushReport(BugReport *exampleReport, MaxValidBugClassSize = std::max(bugReports.size(), static_cast<size_t>(MaxValidBugClassSize)); + // Examine the report and see if the last piece is in a header. Reset the + // report location to the last piece in the main source file. + AnalyzerOptions& Opts = getAnalyzerOptions(); + if (Opts.shouldReportIssuesInMainSourceFile() && !Opts.AnalyzeAll) + D->resetDiagnosticLocationToMainFile(); + // If the path is empty, generate a single step path with the location // of the issue. if (D->path.empty()) { @@ -2892,13 +3475,15 @@ void BugReporter::EmitBasicReport(const Decl *DeclWithIssue, StringRef name, StringRef category, StringRef str, PathDiagnosticLocation Loc, - SourceRange* RBeg, unsigned NumRanges) { + ArrayRef<SourceRange> Ranges) { // 'BT' is owned by BugReporter. BugType *BT = getBugTypeForName(name, category); BugReport *R = new BugReport(*BT, str, Loc); R->setDeclWithIssue(DeclWithIssue); - for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg); + for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end(); + I != E; ++I) + R->addRange(*I); emitReport(R); } @@ -2915,3 +3500,78 @@ BugType *BugReporter::getBugTypeForName(StringRef name, } return BT; } + + +void PathPieces::dump() const { + unsigned index = 0; + for (PathPieces::const_iterator I = begin(), E = end(); I != E; ++I) { + llvm::errs() << "[" << index++ << "] "; + (*I)->dump(); + llvm::errs() << "\n"; + } +} + +void PathDiagnosticCallPiece::dump() const { + llvm::errs() << "CALL\n--------------\n"; + + if (const Stmt *SLoc = getLocStmt(getLocation())) + SLoc->dump(); + else if (const NamedDecl *ND = dyn_cast<NamedDecl>(getCallee())) + llvm::errs() << *ND << "\n"; + else + getLocation().dump(); +} + +void PathDiagnosticEventPiece::dump() const { + llvm::errs() << "EVENT\n--------------\n"; + llvm::errs() << getString() << "\n"; + llvm::errs() << " ---- at ----\n"; + getLocation().dump(); +} + +void PathDiagnosticControlFlowPiece::dump() const { + llvm::errs() << "CONTROL\n--------------\n"; + getStartLocation().dump(); + llvm::errs() << " ---- to ----\n"; + getEndLocation().dump(); +} + +void PathDiagnosticMacroPiece::dump() const { + llvm::errs() << "MACRO\n--------------\n"; + // FIXME: Print which macro is being invoked. +} + +void PathDiagnosticLocation::dump() const { + if (!isValid()) { + llvm::errs() << "<INVALID>\n"; + return; + } + + switch (K) { + case RangeK: + // FIXME: actually print the range. + llvm::errs() << "<range>\n"; + break; + case SingleLocK: + asLocation().dump(); + llvm::errs() << "\n"; + break; + case StmtK: + if (S) + S->dump(); + else + llvm::errs() << "<NULL STMT>\n"; + break; + case DeclK: + if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D)) + llvm::errs() << *ND << "\n"; + else if (isa<BlockDecl>(D)) + // FIXME: Make this nicer. + llvm::errs() << "<block>\n"; + else if (D) + llvm::errs() << "<unknown decl>\n"; + else + llvm::errs() << "<NULL DECL>\n"; + break; + } +} diff --git a/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp b/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp index e078745..e1a92b3 100644 --- a/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp +++ b/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp @@ -532,7 +532,8 @@ PathDiagnosticPiece *FindLastStoreBRVisitor::VisitNode(const ExplodedNode *Succ, // If we have an expression that provided the value, try to track where it // came from. if (InitE) { - if (V.isUndef() || V.getAs<loc::ConcreteInt>()) { + if (V.isUndef() || + V.getAs<loc::ConcreteInt>() || V.getAs<nonloc::ConcreteInt>()) { if (!IsParam) InitE = InitE->IgnoreParenCasts(); bugreporter::trackNullOrUndefValue(StoreSite, InitE, BR, IsParam, @@ -697,10 +698,13 @@ PathDiagnosticPiece *FindLastStoreBRVisitor::VisitNode(const ExplodedNode *Succ, if (P.getAs<CallEnter>() && InitE) L = PathDiagnosticLocation(InitE, BRC.getSourceManager(), P.getLocationContext()); - else + + if (!L.isValid() || !L.asLocation().isValid()) L = PathDiagnosticLocation::create(P, BRC.getSourceManager()); - if (!L.isValid()) + + if (!L.isValid() || !L.asLocation().isValid()) return NULL; + return new PathDiagnosticEventPiece(L, os.str()); } @@ -993,12 +997,15 @@ bool bugreporter::trackNullOrUndefValue(const ExplodedNode *N, BugReporterVisitor *ConstraintTracker = new TrackConstraintBRVisitor(V.castAs<DefinedSVal>(), false); report.addVisitor(ConstraintTracker); + } - // Add visitor, which will suppress inline defensive checks. - if (LVState->isNull(V).isConstrainedTrue() && - EnableNullFPSuppression) { + // Add visitor, which will suppress inline defensive checks. + if (Optional<DefinedSVal> DV = V.getAs<DefinedSVal>()) { + if (!DV->isZeroConstant() && + LVState->isNull(*DV).isConstrainedTrue() && + EnableNullFPSuppression) { BugReporterVisitor *IDCSuppressor = - new SuppressInlineDefensiveChecksVisitor(V.castAs<DefinedSVal>(), + new SuppressInlineDefensiveChecksVisitor(*DV, LVNode); report.addVisitor(IDCSuppressor); } @@ -1350,7 +1357,8 @@ ConditionBRVisitor::VisitTrueTest(const Expr *Cond, // For non-assignment operations, we require that we can understand // both the LHS and RHS. - if (LhsString.empty() || RhsString.empty()) + if (LhsString.empty() || RhsString.empty() || + !BinaryOperator::isComparisonOp(Op)) return 0; // Should we invert the strings if the LHS is not a variable name? @@ -1462,9 +1470,7 @@ ConditionBRVisitor::VisitTrueTest(const Expr *Cond, SmallString<256> Buf; llvm::raw_svector_ostream Out(Buf); - Out << "Assuming '"; - VD->getDeclName().printName(Out); - Out << "' is "; + Out << "Assuming '" << VD->getDeclName() << "' is "; QualType VDTy = VD->getType(); @@ -1516,18 +1522,59 @@ LikelyFalsePositiveSuppressionBRVisitor::getEndPath(BugReporterContext &BRC, BugReport &BR) { // Here we suppress false positives coming from system headers. This list is // based on known issues. - - // Skip reports within the 'std' namespace. Although these can sometimes be - // the user's fault, we currently don't report them very well, and - // Note that this will not help for any other data structure libraries, like - // TR1, Boost, or llvm/ADT. ExprEngine &Eng = BRC.getBugReporter().getEngine(); AnalyzerOptions &Options = Eng.getAnalysisManager().options; - if (Options.shouldSuppressFromCXXStandardLibrary()) { - const LocationContext *LCtx = N->getLocationContext(); - if (isInStdNamespace(LCtx->getDecl())) { + const Decl *D = N->getLocationContext()->getDecl(); + + if (isInStdNamespace(D)) { + // Skip reports within the 'std' namespace. Although these can sometimes be + // the user's fault, we currently don't report them very well, and + // Note that this will not help for any other data structure libraries, like + // TR1, Boost, or llvm/ADT. + if (Options.shouldSuppressFromCXXStandardLibrary()) { BR.markInvalid(getTag(), 0); return 0; + + } else { + // If the the complete 'std' suppression is not enabled, suppress reports + // from the 'std' namespace that are known to produce false positives. + + // The analyzer issues a false use-after-free when std::list::pop_front + // or std::list::pop_back are called multiple times because we cannot + // reason about the internal invariants of the datastructure. + if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) { + const CXXRecordDecl *CD = MD->getParent(); + if (CD->getName() == "list") { + BR.markInvalid(getTag(), 0); + return 0; + } + } + + // The analyzer issues a false positive on + // std::basic_string<uint8_t> v; v.push_back(1); + // and + // std::u16string s; s += u'a'; + // because we cannot reason about the internal invariants of the + // datastructure. + const LocationContext *LCtx = N->getLocationContext(); + do { + const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(LCtx->getDecl()); + if (!MD) + break; + + const CXXRecordDecl *CD = MD->getParent(); + if (CD->getName() == "basic_string") { + BR.markInvalid(getTag(), 0); + return 0; + } else if (CD->getName().find("allocator") == StringRef::npos) { + // Only keep searching if the current method is in a class with the + // word "allocator" in its name, e.g. std::allocator or + // allocator_traits. + break; + } + + LCtx = LCtx->getParent(); + } while (LCtx); } } @@ -1536,12 +1583,11 @@ LikelyFalsePositiveSuppressionBRVisitor::getEndPath(BugReporterContext &BRC, SourceManager &SM = BRC.getSourceManager(); FullSourceLoc Loc = BR.getLocation(SM).asLocation(); while (Loc.isMacroID()) { - if (SM.isInSystemMacro(Loc) && - (SM.getFilename(SM.getSpellingLoc(Loc)).endswith("sys/queue.h"))) { + Loc = Loc.getSpellingLoc(); + if (SM.getFilename(Loc).endswith("sys/queue.h")) { BR.markInvalid(getTag(), 0); return 0; } - Loc = Loc.getSpellingLoc(); } return 0; diff --git a/lib/StaticAnalyzer/Core/CMakeLists.txt b/lib/StaticAnalyzer/Core/CMakeLists.txt index 91f15b3..013f8a5 100644 --- a/lib/StaticAnalyzer/Core/CMakeLists.txt +++ b/lib/StaticAnalyzer/Core/CMakeLists.txt @@ -14,6 +14,7 @@ add_clang_library(clangStaticAnalyzerCore CheckerHelpers.cpp CheckerManager.cpp CheckerRegistry.cpp + CommonBugCategories.cpp ConstraintManager.cpp CoreEngine.cpp Environment.cpp @@ -38,7 +39,6 @@ add_clang_library(clangStaticAnalyzerCore Store.cpp SubEngine.cpp SymbolManager.cpp - TextPathDiagnostics.cpp ) add_dependencies(clangStaticAnalyzerCore diff --git a/lib/StaticAnalyzer/Core/CallEvent.cpp b/lib/StaticAnalyzer/Core/CallEvent.cpp index dfd20b8..a3b34f4 100644 --- a/lib/StaticAnalyzer/Core/CallEvent.cpp +++ b/lib/StaticAnalyzer/Core/CallEvent.cpp @@ -140,8 +140,8 @@ ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount, ProgramStateRef Orig) const { ProgramStateRef Result = (Orig ? Orig : getState()); - SmallVector<SVal, 8> ConstValues; SmallVector<SVal, 8> ValuesToInvalidate; + RegionAndSymbolInvalidationTraits ETraits; getExtraInvalidatedValues(ValuesToInvalidate); @@ -154,9 +154,12 @@ ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount, // Mark this region for invalidation. We batch invalidate regions // below for efficiency. if (PreserveArgs.count(Idx)) - ConstValues.push_back(getArgSVal(Idx)); - else - ValuesToInvalidate.push_back(getArgSVal(Idx)); + if (const MemRegion *MR = getArgSVal(Idx).getAsRegion()) + ETraits.setTrait(MR->StripCasts(), + RegionAndSymbolInvalidationTraits::TK_PreserveContents); + // TODO: Factor this out + handle the lower level const pointers. + + ValuesToInvalidate.push_back(getArgSVal(Idx)); } // Invalidate designated regions using the batch invalidation API. @@ -165,7 +168,7 @@ ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount, return Result->invalidateRegions(ValuesToInvalidate, getOriginExpr(), BlockCount, getLocationContext(), /*CausedByPointerEscape*/ true, - /*Symbols=*/0, this, ConstValues); + /*Symbols=*/0, this, &ETraits); } ProgramPoint CallEvent::getProgramPoint(bool IsPreVisit, @@ -245,15 +248,36 @@ QualType CallEvent::getDeclaredResultType(const Decl *D) { // Blocks are difficult because the return type may not be stored in the // BlockDecl itself. The AST should probably be enhanced, but for now we // just do what we can. - QualType Ty = BD->getSignatureAsWritten()->getType(); - if (const FunctionType *FT = Ty->getAs<FunctionType>()) - if (!FT->getResultType()->isDependentType()) - return FT->getResultType(); + // If the block is declared without an explicit argument list, the + // signature-as-written just includes the return type, not the entire + // function type. + // FIXME: All blocks should have signatures-as-written, even if the return + // type is inferred. (That's signified with a dependent result type.) + if (const TypeSourceInfo *TSI = BD->getSignatureAsWritten()) { + QualType Ty = TSI->getType(); + if (const FunctionType *FT = Ty->getAs<FunctionType>()) + Ty = FT->getResultType(); + if (!Ty->isDependentType()) + return Ty; + } return QualType(); } - return QualType(); + llvm_unreachable("unknown callable kind"); +} + +bool CallEvent::isVariadic(const Decl *D) { + assert(D); + + if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) + return FD->isVariadic(); + if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) + return MD->isVariadic(); + if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) + return BD->isVariadic(); + + llvm_unreachable("unknown callable kind"); } static void addParameterValuesToBindings(const StackFrameContext *CalleeCtx, @@ -264,8 +288,11 @@ static void addParameterValuesToBindings(const StackFrameContext *CalleeCtx, CallEvent::param_iterator E) { MemRegionManager &MRMgr = SVB.getRegionManager(); + // If the function has fewer parameters than the call has arguments, we simply + // do not bind any values to them. + unsigned NumArgs = Call.getNumArgs(); unsigned Idx = 0; - for (; I != E; ++I, ++Idx) { + for (; I != E && Idx < NumArgs; ++I, ++Idx) { const ParmVarDecl *ParamDecl = *I; assert(ParamDecl && "Formal parameter has no decl?"); @@ -674,8 +701,12 @@ const PseudoObjectExpr *ObjCMethodCall::getContainingPseudoObjectExpr() const { ObjCMessageKind ObjCMethodCall::getMessageKind() const { if (Data == 0) { + + // Find the parent, ignoring implicit casts. ParentMap &PM = getLocationContext()->getParentMap(); - const Stmt *S = PM.getParent(getOriginExpr()); + const Stmt *S = PM.getParentIgnoreParenCasts(getOriginExpr()); + + // Check if parent is a PseudoObjectExpr. if (const PseudoObjectExpr *POE = dyn_cast_or_null<PseudoObjectExpr>(S)) { const Expr *Syntactic = POE->getSyntacticForm(); @@ -730,7 +761,7 @@ bool ObjCMethodCall::canBeOverridenInSubclass(ObjCInterfaceDecl *IDecl, // TODO: It could actually be subclassed if the subclass is private as well. // This is probably very rare. SourceLocation InterfLoc = IDecl->getEndOfDefinitionLoc(); - if (InterfLoc.isValid() && SM.isFromMainFile(InterfLoc)) + if (InterfLoc.isValid() && SM.isInMainFile(InterfLoc)) return false; // Assume that property accessors are not overridden. @@ -752,7 +783,7 @@ bool ObjCMethodCall::canBeOverridenInSubclass(ObjCInterfaceDecl *IDecl, return false; // If outside the main file, - if (D->getLocation().isValid() && !SM.isFromMainFile(D->getLocation())) + if (D->getLocation().isValid() && !SM.isInMainFile(D->getLocation())) return true; if (D->isOverriding()) { @@ -946,6 +977,8 @@ CallEventManager::getCaller(const StackFrameContext *CalleeCtx, const Stmt *Trigger; if (Optional<CFGAutomaticObjDtor> AutoDtor = E.getAs<CFGAutomaticObjDtor>()) Trigger = AutoDtor->getTriggerStmt(); + else if (Optional<CFGDeleteDtor> DeleteDtor = E.getAs<CFGDeleteDtor>()) + Trigger = cast<Stmt>(DeleteDtor->getDeleteExpr()); else Trigger = Dtor->getBody(); diff --git a/lib/StaticAnalyzer/Core/CheckerContext.cpp b/lib/StaticAnalyzer/Core/CheckerContext.cpp index 74eeef1..6b22bf4 100644 --- a/lib/StaticAnalyzer/Core/CheckerContext.cpp +++ b/lib/StaticAnalyzer/Core/CheckerContext.cpp @@ -68,7 +68,7 @@ bool CheckerContext::isCLibraryFunction(const FunctionDecl *FD, // If this function is not externally visible, it is not a C library function. // Note that we make an exception for inline functions, which may be // declared in header files without external linkage. - if (!FD->isInlined() && FD->getLinkage() != ExternalLinkage) + if (!FD->isInlined() && !FD->isExternallyVisible()) return false; if (Name.empty()) diff --git a/lib/StaticAnalyzer/Core/CheckerManager.cpp b/lib/StaticAnalyzer/Core/CheckerManager.cpp index 8adf326..c1ae7e9 100644 --- a/lib/StaticAnalyzer/Core/CheckerManager.cpp +++ b/lib/StaticAnalyzer/Core/CheckerManager.cpp @@ -169,7 +169,7 @@ void CheckerManager::runCheckersForStmt(bool isPreVisit, const Stmt *S, ExprEngine &Eng, bool WasInlined) { - CheckStmtContext C(isPreVisit, *getCachedStmtCheckersFor(S, isPreVisit), + CheckStmtContext C(isPreVisit, getCachedStmtCheckersFor(S, isPreVisit), S, Eng, WasInlined); expandGraphWithCheckers(C, Dst, Src); } @@ -487,10 +487,10 @@ CheckerManager::runCheckersForRegionChanges(ProgramStateRef state, /// \brief Run checkers to process symbol escape event. ProgramStateRef CheckerManager::runCheckersForPointerEscape(ProgramStateRef State, - const InvalidatedSymbols &Escaped, - const CallEvent *Call, - PointerEscapeKind Kind, - bool IsConst) { + const InvalidatedSymbols &Escaped, + const CallEvent *Call, + PointerEscapeKind Kind, + RegionAndSymbolInvalidationTraits *ETraits) { assert((Call != NULL || (Kind != PSK_DirectEscapeOnCall && Kind != PSK_IndirectEscapeOnCall)) && @@ -500,7 +500,7 @@ CheckerManager::runCheckersForPointerEscape(ProgramStateRef State, // way), bail out. if (!State) return NULL; - State = PointerEscapeCheckers[i](State, Escaped, Call, Kind, IsConst); + State = PointerEscapeCheckers[i](State, Escaped, Call, Kind, ETraits); } return State; } @@ -688,27 +688,23 @@ void CheckerManager::_registerForEndOfTranslationUnit( // Implementation details. //===----------------------------------------------------------------------===// -CheckerManager::CachedStmtCheckers * +const CheckerManager::CachedStmtCheckers & CheckerManager::getCachedStmtCheckersFor(const Stmt *S, bool isPreVisit) { assert(S); - CachedStmtCheckersKey key(S->getStmtClass(), isPreVisit); - CachedStmtCheckers *checkers = 0; - CachedStmtCheckersMapTy::iterator CCI = CachedStmtCheckersMap.find(key); - if (CCI != CachedStmtCheckersMap.end()) { - checkers = &(CCI->second); - } else { - // Find the checkers that should run for this Stmt and cache them. - checkers = &CachedStmtCheckersMap[key]; - for (unsigned i = 0, e = StmtCheckers.size(); i != e; ++i) { - StmtCheckerInfo &info = StmtCheckers[i]; - if (info.IsPreVisit == isPreVisit && info.IsForStmtFn(S)) - checkers->push_back(info.CheckFn); - } + unsigned Key = (S->getStmtClass() << 1) | unsigned(isPreVisit); + CachedStmtCheckersMapTy::iterator CCI = CachedStmtCheckersMap.find(Key); + if (CCI != CachedStmtCheckersMap.end()) + return CCI->second; + + // Find the checkers that should run for this Stmt and cache them. + CachedStmtCheckers &Checkers = CachedStmtCheckersMap[Key]; + for (unsigned i = 0, e = StmtCheckers.size(); i != e; ++i) { + StmtCheckerInfo &Info = StmtCheckers[i]; + if (Info.IsPreVisit == isPreVisit && Info.IsForStmtFn(S)) + Checkers.push_back(Info.CheckFn); } - - assert(checkers); - return checkers; + return Checkers; } CheckerManager::~CheckerManager() { diff --git a/lib/StaticAnalyzer/Core/CommonBugCategories.cpp b/lib/StaticAnalyzer/Core/CommonBugCategories.cpp new file mode 100644 index 0000000..3cb9323 --- /dev/null +++ b/lib/StaticAnalyzer/Core/CommonBugCategories.cpp @@ -0,0 +1,20 @@ +//=--- CommonBugCategories.cpp - Provides common issue categories -*- C++ -*-=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h" + +// Common strings used for the "category" of many static analyzer issues. +namespace clang { namespace ento { namespace categories { + +const char * const CoreFoundationObjectiveC = "Core Foundation/Objective-C"; +const char * const LogicError = "Logic error"; +const char * const MemoryCoreFoundationObjectiveC = + "Memory (Core Foundation/Objective-C)"; +const char * const UnixAPI = "Unix API"; +}}} diff --git a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp index af9518a..e9c4a35 100644 --- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp +++ b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp @@ -357,8 +357,7 @@ ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks, // Process the first worklist until it is empty. while (!WL1.empty()) { - const ExplodedNode *N = WL1.back(); - WL1.pop_back(); + const ExplodedNode *N = WL1.pop_back_val(); // Have we already visited this node? If so, continue to the next one. if (Pass1.count(N)) @@ -388,8 +387,7 @@ ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks, // ===- Pass 2 (forward DFS to construct the new graph) -=== while (!WL2.empty()) { - const ExplodedNode *N = WL2.back(); - WL2.pop_back(); + const ExplodedNode *N = WL2.pop_back_val(); // Skip this node if we have already processed it. if (Pass2.find(N) != Pass2.end()) diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp index bfe4e15..9907d0c 100644 --- a/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -16,6 +16,7 @@ #define DEBUG_TYPE "ExprEngine" #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" +#include "PrettyStackTraceLocationContext.h" #include "clang/AST/CharUnits.h" #include "clang/AST/ParentMap.h" #include "clang/AST/StmtCXX.h" @@ -208,7 +209,18 @@ ExprEngine::createTemporaryRegionIfNeeded(ProgramStateRef State, // Create a temporary object region for the inner expression (which may have // a more derived type) and bind the value into it. - const TypedValueRegion *TR = MRMgr.getCXXTempObjectRegion(Inner, LC); + const TypedValueRegion *TR = NULL; + if (const MaterializeTemporaryExpr *MT = + dyn_cast<MaterializeTemporaryExpr>(Result)) { + StorageDuration SD = MT->getStorageDuration(); + // If this object is bound to a reference with static storage duration, we + // put it in a different region to prevent "address leakage" warnings. + if (SD == SD_Static || SD == SD_Thread) + TR = MRMgr.getCXXStaticTempObjectRegion(Inner); + } + if (!TR) + TR = MRMgr.getCXXTempObjectRegion(Inner, LC); + SVal Reg = loc::MemRegionVal(TR); if (V.isUnknown()) @@ -263,6 +275,7 @@ void ExprEngine::processEndWorklist(bool hasWorkRemaining) { void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, unsigned StmtIdx, NodeBuilderContext *Ctx) { + PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); currStmtIdx = StmtIdx; currBldrCtx = Ctx; @@ -274,13 +287,13 @@ void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, ProcessInitializer(E.castAs<CFGInitializer>().getInitializer(), Pred); return; case CFGElement::AutomaticObjectDtor: + case CFGElement::DeleteDtor: case CFGElement::BaseDtor: case CFGElement::MemberDtor: case CFGElement::TemporaryDtor: ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred); return; } - currBldrCtx = 0; } static bool shouldRemoveDeadBindings(AnalysisManager &AMgr, @@ -523,6 +536,9 @@ void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, case CFGElement::TemporaryDtor: ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst); break; + case CFGElement::DeleteDtor: + ProcessDeleteDtor(D.castAs<CFGDeleteDtor>(), Pred, Dst); + break; default: llvm_unreachable("Unexpected dtor kind."); } @@ -550,6 +566,35 @@ void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor, Pred, Dst); } +void ExprEngine::ProcessDeleteDtor(const CFGDeleteDtor Dtor, + ExplodedNode *Pred, + ExplodedNodeSet &Dst) { + ProgramStateRef State = Pred->getState(); + const LocationContext *LCtx = Pred->getLocationContext(); + const CXXDeleteExpr *DE = Dtor.getDeleteExpr(); + const Stmt *Arg = DE->getArgument(); + SVal ArgVal = State->getSVal(Arg, LCtx); + + // If the argument to delete is known to be a null value, + // don't run destructor. + if (State->isNull(ArgVal).isConstrainedTrue()) { + QualType DTy = DE->getDestroyedType(); + QualType BTy = getContext().getBaseElementType(DTy); + const CXXRecordDecl *RD = BTy->getAsCXXRecordDecl(); + const CXXDestructorDecl *Dtor = RD->getDestructor(); + + PostImplicitCall PP(Dtor, DE->getLocStart(), LCtx); + NodeBuilder Bldr(Pred, Dst, *currBldrCtx); + Bldr.generateNode(PP, Pred->getState(), Pred); + return; + } + + VisitCXXDestructor(DE->getDestroyedType(), + ArgVal.getAsRegion(), + DE, /*IsBase=*/ false, + Pred, Dst); +} + void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, ExplodedNode *Pred, ExplodedNodeSet &Dst) { const LocationContext *LCtx = Pred->getLocationContext(); @@ -589,7 +634,15 @@ void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, ExplodedNode *Pred, - ExplodedNodeSet &Dst) {} + ExplodedNodeSet &Dst) { + + QualType varType = D.getBindTemporaryExpr()->getSubExpr()->getType(); + + // FIXME: Inlining of temporary destructors is not supported yet anyway, so we + // just put a NULL region for now. This will need to be changed later. + VisitCXXDestructor(varType, NULL, D.getBindTemporaryExpr(), + /*IsBase=*/ false, Pred, Dst); +} void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, ExplodedNodeSet &DstTop) { @@ -604,9 +657,7 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, switch (S->getStmtClass()) { // C++ and ARC stuff we don't support yet. case Expr::ObjCIndirectCopyRestoreExprClass: - case Stmt::CXXDefaultInitExprClass: case Stmt::CXXDependentScopeMemberExprClass: - case Stmt::CXXPseudoDestructorExprClass: case Stmt::CXXTryStmtClass: case Stmt::CXXTypeidExprClass: case Stmt::CXXUuidofExprClass: @@ -651,13 +702,13 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, case Stmt::IfStmtClass: case Stmt::IndirectGotoStmtClass: case Stmt::LabelStmtClass: - case Stmt::AttributedStmtClass: case Stmt::NoStmtClass: case Stmt::NullStmtClass: case Stmt::SwitchStmtClass: case Stmt::WhileStmtClass: case Expr::MSDependentExistsStmtClass: case Stmt::CapturedStmtClass: + case Stmt::OMPParallelDirectiveClass: llvm_unreachable("Stmt should not be in analyzer evaluation loop"); case Stmt::ObjCSubscriptRefExprClass: @@ -698,6 +749,7 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, case Stmt::ParenListExprClass: case Stmt::PredefinedExprClass: case Stmt::ShuffleVectorExprClass: + case Stmt::ConvertVectorExprClass: case Stmt::VAArgExprClass: case Stmt::CUDAKernelCallExprClass: case Stmt::OpaqueValueExprClass: @@ -708,6 +760,7 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, // Cases we intentionally don't evaluate, since they don't need // to be explicitly evaluated. case Stmt::AddrLabelExprClass: + case Stmt::AttributedStmtClass: case Stmt::IntegerLiteralClass: case Stmt::CharacterLiteralClass: case Stmt::ImplicitValueInitExprClass: @@ -719,6 +772,7 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, case Stmt::StringLiteralClass: case Stmt::ObjCStringLiteralClass: case Stmt::CXXBindTemporaryExprClass: + case Stmt::CXXPseudoDestructorExprClass: case Stmt::SubstNonTypeTemplateParmExprClass: case Stmt::CXXNullPtrLiteralExprClass: { Bldr.takeNodes(Pred); @@ -729,7 +783,8 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, break; } - case Stmt::CXXDefaultArgExprClass: { + case Stmt::CXXDefaultArgExprClass: + case Stmt::CXXDefaultInitExprClass: { Bldr.takeNodes(Pred); ExplodedNodeSet PreVisit; getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this); @@ -737,9 +792,13 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, ExplodedNodeSet Tmp; StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx); - const LocationContext *LCtx = Pred->getLocationContext(); - const CXXDefaultArgExpr *DefaultE = cast<CXXDefaultArgExpr>(S); - const Expr *ArgE = DefaultE->getExpr(); + const Expr *ArgE; + if (const CXXDefaultArgExpr *DefE = dyn_cast<CXXDefaultArgExpr>(S)) + ArgE = DefE->getExpr(); + else if (const CXXDefaultInitExpr *DefE = dyn_cast<CXXDefaultInitExpr>(S)) + ArgE = DefE->getExpr(); + else + llvm_unreachable("unknown constant wrapper kind"); bool IsTemporary = false; if (const MaterializeTemporaryExpr *MTE = @@ -752,13 +811,15 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, if (!ConstantVal) ConstantVal = UnknownVal(); + const LocationContext *LCtx = Pred->getLocationContext(); for (ExplodedNodeSet::iterator I = PreVisit.begin(), E = PreVisit.end(); I != E; ++I) { ProgramStateRef State = (*I)->getState(); - State = State->BindExpr(DefaultE, LCtx, *ConstantVal); + State = State->BindExpr(S, LCtx, *ConstantVal); if (IsTemporary) - State = createTemporaryRegionIfNeeded(State, LCtx, DefaultE, - DefaultE); + State = createTemporaryRegionIfNeeded(State, LCtx, + cast<Expr>(S), + cast<Expr>(S)); Bldr2.generateNode(S, *I, State); } @@ -767,10 +828,10 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, break; } + // Cases we evaluate as opaque expressions, conjuring a symbol. + case Stmt::CXXStdInitializerListExprClass: case Expr::ObjCArrayLiteralClass: case Expr::ObjCDictionaryLiteralClass: - // FIXME: explicitly model with a region and the actual contents - // of the container. For now, conjure a symbol. case Expr::ObjCBoxedExprClass: { Bldr.takeNodes(Pred); @@ -1188,7 +1249,8 @@ bool ExprEngine::replayWithoutInlining(ExplodedNode *N, void ExprEngine::processCFGBlockEntrance(const BlockEdge &L, NodeBuilderWithSinks &nodeBuilder, ExplodedNode *Pred) { - + PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); + // FIXME: Refactor this into a checker. if (nodeBuilder.getContext().blockCount() >= AMgr.options.maxBlockVisitOnPath) { static SimpleProgramPointTag tag("ExprEngine : Block count exceeded"); @@ -1312,6 +1374,8 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF) { + const LocationContext *LCtx = Pred->getLocationContext(); + PrettyStackTraceLocationContext StackCrashInfo(LCtx); currBldrCtx = &BldCtx; // Check for NULL conditions; e.g. "for(;;)" @@ -1323,7 +1387,6 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, } - // Resolve the condition in the precense of nested '||' and '&&'. if (const Expr *Ex = dyn_cast<Expr>(Condition)) Condition = Ex->IgnoreParens(); @@ -1412,6 +1475,7 @@ void ExprEngine::processStaticInitializer(const DeclStmt *DS, clang::ento::ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF) { + PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); currBldrCtx = &BuilderCtx; const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl()); @@ -1477,6 +1541,7 @@ void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { /// nodes when the control reaches the end of a function. void ExprEngine::processEndOfFunction(NodeBuilderContext& BC, ExplodedNode *Pred) { + PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); StateMgr.EndPath(Pred->getState()); ExplodedNodeSet Dst; @@ -1613,7 +1678,9 @@ void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, const LocationContext *LCtx = Pred->getLocationContext(); if (const VarDecl *VD = dyn_cast<VarDecl>(D)) { - assert(Ex->isGLValue()); + // C permits "extern void v", and if you cast the address to a valid type, + // you can even do things with it. We simply pretend + assert(Ex->isGLValue() || VD->getType()->isVoidType()); SVal V = state->getLValue(VD, Pred->getLocationContext()); // For references, the 'lvalue' is the pointer address stored in the @@ -1722,7 +1789,24 @@ void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, FieldDecl *field = cast<FieldDecl>(Member); SVal L = state->getLValue(field, baseExprVal); - if (M->isGLValue()) { + + if (M->isGLValue() || M->getType()->isArrayType()) { + + // We special case rvalue of array type because the analyzer cannot reason + // about it, since we expect all regions to be wrapped in Locs. So we will + // treat these as lvalues assuming that they will decay to pointers as soon + // as they are used. + if (!M->isGLValue()) { + assert(M->getType()->isArrayType()); + const ImplicitCastExpr *PE = + dyn_cast<ImplicitCastExpr>(Pred->getParentMap().getParent(M)); + if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) { + assert(false && + "We assume that array is always wrapped in ArrayToPointerDecay"); + L = UnknownVal(); + } + } + if (field->getType()->isReferenceType()) { if (const MemRegion *R = L.getAsRegion()) L = state->getSVal(R); @@ -1793,7 +1877,8 @@ ProgramStateRef ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, State = getCheckerManager().runCheckersForPointerEscape(State, EscapedSymbols, /*CallEvent*/ 0, - PSK_EscapeOnBind); + PSK_EscapeOnBind, + 0); return State; } @@ -1804,7 +1889,7 @@ ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State, ArrayRef<const MemRegion *> ExplicitRegions, ArrayRef<const MemRegion *> Regions, const CallEvent *Call, - bool IsConst) { + RegionAndSymbolInvalidationTraits &ITraits) { if (!Invalidated || Invalidated->empty()) return State; @@ -1814,17 +1899,7 @@ ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State, *Invalidated, 0, PSK_EscapeOther, - IsConst); - - // Note: Due to current limitations of RegionStore, we only process the top - // level const pointers correctly. The lower level const pointers are - // currently treated as non-const. - if (IsConst) - return getCheckerManager().runCheckersForPointerEscape(State, - *Invalidated, - Call, - PSK_DirectEscapeOnCall, - true); + &ITraits); // If the symbols were invalidated by a call, we want to find out which ones // were invalidated directly due to being arguments to the call. @@ -1846,12 +1921,12 @@ ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State, if (!SymbolsDirectlyInvalidated.empty()) State = getCheckerManager().runCheckersForPointerEscape(State, - SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall); + SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall, &ITraits); // Notify about the symbols that get indirectly invalidated by the call. if (!SymbolsIndirectlyInvalidated.empty()) State = getCheckerManager().runCheckersForPointerEscape(State, - SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall); + SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall, &ITraits); return State; } diff --git a/lib/StaticAnalyzer/Core/ExprEngineC.cpp b/lib/StaticAnalyzer/Core/ExprEngineC.cpp index 67aeab6..983fda0 100644 --- a/lib/StaticAnalyzer/Core/ExprEngineC.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngineC.cpp @@ -184,7 +184,8 @@ void ExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred, // Get the value of the block itself. SVal V = svalBuilder.getBlockPointer(BE->getBlockDecl(), T, - Pred->getLocationContext()); + Pred->getLocationContext(), + currBldrCtx->blockCount()); ProgramStateRef State = Pred->getState(); @@ -309,7 +310,8 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, case CK_BlockPointerToObjCPointerCast: case CK_AnyPointerToBlockPointerCast: case CK_ObjCObjectLValueCast: - case CK_ZeroToOCLEvent: { + case CK_ZeroToOCLEvent: + case CK_LValueBitCast: { // Delegate to SValBuilder to process. SVal V = state->getSVal(Ex, LCtx); V = svalBuilder.evalCast(V, T, ExTy); @@ -370,7 +372,7 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, } case CK_NullToMemberPointer: { // FIXME: For now, member pointers are represented by void *. - SVal V = svalBuilder.makeIntValWithPtrWidth(0, true); + SVal V = svalBuilder.makeNull(); state = state->BindExpr(CastE, LCtx, V); Bldr.generateNode(CastE, Pred, state); continue; @@ -381,8 +383,7 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, case CK_BaseToDerivedMemberPointer: case CK_DerivedToBaseMemberPointer: case CK_ReinterpretMemberPointer: - case CK_VectorSplat: - case CK_LValueBitCast: { + case CK_VectorSplat: { // Recover some path-sensitivty by conjuring a new value. QualType resultType = CastE->getType(); if (CastE->isGLValue()) @@ -446,7 +447,8 @@ void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred, ExplodedNodeSet dstPreVisit; getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, DS, *this); - StmtNodeBuilder B(dstPreVisit, Dst, *currBldrCtx); + ExplodedNodeSet dstEvaluated; + StmtNodeBuilder B(dstPreVisit, dstEvaluated, *currBldrCtx); for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end(); I!=E; ++I) { ExplodedNode *N = *I; @@ -499,6 +501,8 @@ void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred, B.generateNode(DS, N, state); } } + + getCheckerManager().runCheckersForPostStmt(Dst, B.getResults(), DS, *this); } void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred, @@ -579,9 +583,10 @@ void ExprEngine::VisitInitListExpr(const InitListExpr *IE, const LocationContext *LCtx = Pred->getLocationContext(); QualType T = getContext().getCanonicalType(IE->getType()); unsigned NumInitElements = IE->getNumInits(); - - if (T->isArrayType() || T->isRecordType() || T->isVectorType() || - T->isAnyComplexType()) { + + if (!IE->isGLValue() && + (T->isArrayType() || T->isRecordType() || T->isVectorType() || + T->isAnyComplexType())) { llvm::ImmutableList<SVal> vals = getBasicVals().getEmptySValList(); // Handle base case where the initializer has no elements. @@ -595,8 +600,6 @@ void ExprEngine::VisitInitListExpr(const InitListExpr *IE, for (InitListExpr::const_reverse_iterator it = IE->rbegin(), ei = IE->rend(); it != ei; ++it) { SVal V = state->getSVal(cast<Expr>(*it), LCtx); - if (dyn_cast_or_null<CXXTempObjectRegion>(V.getAsRegion())) - V = UnknownVal(); vals = getBasicVals().consVals(V, vals); } @@ -606,7 +609,9 @@ void ExprEngine::VisitInitListExpr(const InitListExpr *IE, return; } - // Handle scalars: int{5} and int{}. + // Handle scalars: int{5} and int{} and GLvalues. + // Note, if the InitListExpr is a GLvalue, it means that there is an address + // representing it, so it must have a single init element. assert(NumInitElements <= 1); SVal V; @@ -735,15 +740,23 @@ VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex, void ExprEngine::VisitUnaryOperator(const UnaryOperator* U, ExplodedNode *Pred, ExplodedNodeSet &Dst) { - StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); - switch (U->getOpcode()) { + // FIXME: Prechecks eventually go in ::Visit(). + ExplodedNodeSet CheckedSet; + getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, U, *this); + + ExplodedNodeSet EvalSet; + StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx); + + for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); + I != E; ++I) { + switch (U->getOpcode()) { default: { - Bldr.takeNodes(Pred); + Bldr.takeNodes(*I); ExplodedNodeSet Tmp; - VisitIncrementDecrementOperator(U, Pred, Tmp); + VisitIncrementDecrementOperator(U, *I, Tmp); Bldr.addNodes(Tmp); - } break; + } case UO_Real: { const Expr *Ex = U->getSubExpr()->IgnoreParens(); @@ -755,10 +768,10 @@ void ExprEngine::VisitUnaryOperator(const UnaryOperator* U, // For all other types, UO_Real is an identity operation. assert (U->getType() == Ex->getType()); - ProgramStateRef state = Pred->getState(); - const LocationContext *LCtx = Pred->getLocationContext(); - Bldr.generateNode(U, Pred, state->BindExpr(U, LCtx, - state->getSVal(Ex, LCtx))); + ProgramStateRef state = (*I)->getState(); + const LocationContext *LCtx = (*I)->getLocationContext(); + Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, + state->getSVal(Ex, LCtx))); break; } @@ -770,10 +783,10 @@ void ExprEngine::VisitUnaryOperator(const UnaryOperator* U, break; } // For all other types, UO_Imag returns 0. - ProgramStateRef state = Pred->getState(); - const LocationContext *LCtx = Pred->getLocationContext(); + ProgramStateRef state = (*I)->getState(); + const LocationContext *LCtx = (*I)->getLocationContext(); SVal X = svalBuilder.makeZeroVal(Ex->getType()); - Bldr.generateNode(U, Pred, state->BindExpr(U, LCtx, X)); + Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, X)); break; } @@ -791,10 +804,10 @@ void ExprEngine::VisitUnaryOperator(const UnaryOperator* U, // generate an extra node that just propagates the value of the // subexpression. const Expr *Ex = U->getSubExpr()->IgnoreParens(); - ProgramStateRef state = Pred->getState(); - const LocationContext *LCtx = Pred->getLocationContext(); - Bldr.generateNode(U, Pred, state->BindExpr(U, LCtx, - state->getSVal(Ex, LCtx))); + ProgramStateRef state = (*I)->getState(); + const LocationContext *LCtx = (*I)->getLocationContext(); + Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, + state->getSVal(Ex, LCtx))); break; } @@ -803,14 +816,14 @@ void ExprEngine::VisitUnaryOperator(const UnaryOperator* U, case UO_Not: { assert (!U->isGLValue()); const Expr *Ex = U->getSubExpr()->IgnoreParens(); - ProgramStateRef state = Pred->getState(); - const LocationContext *LCtx = Pred->getLocationContext(); + ProgramStateRef state = (*I)->getState(); + const LocationContext *LCtx = (*I)->getLocationContext(); // Get the value of the subexpression. SVal V = state->getSVal(Ex, LCtx); if (V.isUnknownOrUndef()) { - Bldr.generateNode(U, Pred, state->BindExpr(U, LCtx, V)); + Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, V)); break; } @@ -847,11 +860,13 @@ void ExprEngine::VisitUnaryOperator(const UnaryOperator* U, state = state->BindExpr(U, LCtx, Result); break; } - Bldr.generateNode(U, Pred, state); + Bldr.generateNode(U, *I, state); break; } + } } + getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, U, *this); } void ExprEngine::VisitIncrementDecrementOperator(const UnaryOperator* U, diff --git a/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp b/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp index ed90dc5..eba4f94 100644 --- a/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp @@ -30,21 +30,7 @@ void ExprEngine::CreateCXXTemporaryObject(const MaterializeTemporaryExpr *ME, ProgramStateRef state = Pred->getState(); const LocationContext *LCtx = Pred->getLocationContext(); - SVal V = state->getSVal(tempExpr, LCtx); - - // If the value is already a CXXTempObjectRegion, it is fine as it is. - // Otherwise, create a new CXXTempObjectRegion, and copy the value into it. - // This is an optimization for when an rvalue is constructed and then - // immediately materialized. - const MemRegion *MR = V.getAsRegion(); - if (const CXXTempObjectRegion *TR = - dyn_cast_or_null<CXXTempObjectRegion>(MR)) { - if (getContext().hasSameUnqualifiedType(TR->getValueType(), ME->getType())) - state = state->BindExpr(ME, LCtx, V); - } - - if (state == Pred->getState()) - state = createTemporaryRegionIfNeeded(state, LCtx, tempExpr, ME); + state = createTemporaryRegionIfNeeded(state, LCtx, tempExpr, ME); Bldr.generateNode(ME, Pred, state); } @@ -105,6 +91,12 @@ void ExprEngine::performTrivialCopy(NodeBuilder &Bldr, ExplodedNode *Pred, /// If the type is not an array type at all, the original value is returned. static SVal makeZeroElementRegion(ProgramStateRef State, SVal LValue, QualType &Ty) { + // FIXME: This check is just a temporary workaround, because + // ProcessTemporaryDtor sends us NULL regions. It will not be necessary once + // we can properly process temporary destructors. + if (!LValue.getAsRegion()) + return LValue; + SValBuilder &SVB = State->getStateManager().getSValBuilder(); ASTContext &Ctx = SVB.getContext(); @@ -176,6 +168,7 @@ void ExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *CE, } // FIXME: This will eventually need to handle new-expressions as well. + // Don't forget to update the pre-constructor initialization code below. } // If we couldn't find an existing region to construct into, assume we're @@ -187,8 +180,26 @@ void ExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *CE, break; } - case CXXConstructExpr::CK_NonVirtualBase: case CXXConstructExpr::CK_VirtualBase: + // Make sure we are not calling virtual base class initializers twice. + // Only the most-derived object should initialize virtual base classes. + if (const Stmt *Outer = LCtx->getCurrentStackFrame()->getCallSite()) { + const CXXConstructExpr *OuterCtor = dyn_cast<CXXConstructExpr>(Outer); + if (OuterCtor) { + switch (OuterCtor->getConstructionKind()) { + case CXXConstructExpr::CK_NonVirtualBase: + case CXXConstructExpr::CK_VirtualBase: + // Bail out! + destNodes.Add(Pred); + return; + case CXXConstructExpr::CK_Complete: + case CXXConstructExpr::CK_Delegating: + break; + } + } + } + // FALLTHROUGH + case CXXConstructExpr::CK_NonVirtualBase: case CXXConstructExpr::CK_Delegating: { const CXXMethodDecl *CurCtor = cast<CXXMethodDecl>(LCtx->getDecl()); Loc ThisPtr = getSValBuilder().getCXXThis(CurCtor, @@ -215,8 +226,38 @@ void ExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *CE, ExplodedNodeSet DstPreVisit; getCheckerManager().runCheckersForPreStmt(DstPreVisit, Pred, CE, *this); + + ExplodedNodeSet PreInitialized; + { + StmtNodeBuilder Bldr(DstPreVisit, PreInitialized, *currBldrCtx); + if (CE->requiresZeroInitialization()) { + // Type of the zero doesn't matter. + SVal ZeroVal = svalBuilder.makeZeroVal(getContext().CharTy); + + for (ExplodedNodeSet::iterator I = DstPreVisit.begin(), + E = DstPreVisit.end(); + I != E; ++I) { + ProgramStateRef State = (*I)->getState(); + // FIXME: Once we properly handle constructors in new-expressions, we'll + // need to invalidate the region before setting a default value, to make + // sure there aren't any lingering bindings around. This probably needs + // to happen regardless of whether or not the object is zero-initialized + // to handle random fields of a placement-initialized object picking up + // old bindings. We might only want to do it when we need to, though. + // FIXME: This isn't actually correct for arrays -- we need to zero- + // initialize the entire array, not just the first element -- but our + // handling of arrays everywhere else is weak as well, so this shouldn't + // actually make things worse. Placement new makes this tricky as well, + // since it's then possible to be initializing one part of a multi- + // dimensional array. + State = State->bindDefault(loc::MemRegionVal(Target), ZeroVal); + Bldr.generateNode(CE, *I, State, /*tag=*/0, ProgramPoint::PreStmtKind); + } + } + } + ExplodedNodeSet DstPreCall; - getCheckerManager().runCheckersForPreCall(DstPreCall, DstPreVisit, + getCheckerManager().runCheckersForPreCall(DstPreCall, PreInitialized, *Call, *this); ExplodedNodeSet DstEvaluated; @@ -255,7 +296,9 @@ void ExprEngine::VisitCXXDestructor(QualType ObjectType, // FIXME: We need to run the same destructor on every element of the array. // This workaround will just run the first destructor (which will still // invalidate the entire array). - SVal DestVal = loc::MemRegionVal(Dest); + SVal DestVal = UnknownVal(); + if (Dest) + DestVal = loc::MemRegionVal(Dest); DestVal = makeZeroElementRegion(State, DestVal, ObjectType); Dest = DestVal.getAsRegion(); @@ -332,11 +375,14 @@ void ExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred, if (!State) return; - // If we're compiling with exceptions enabled, and this allocation function - // is not declared as non-throwing, failures /must/ be signalled by - // exceptions, and thus the return value will never be NULL. + // If this allocation function is not declared as non-throwing, failures + // /must/ be signalled by exceptions, and thus the return value will never be + // NULL. -fno-exceptions does not influence this semantics. + // FIXME: GCC has a -fcheck-new option, which forces it to consider the case + // where new can return NULL. If we end up supporting that option, we can + // consider adding a check for it here. // C++11 [basic.stc.dynamic.allocation]p3. - if (FD && getContext().getLangOpts().CXXExceptions) { + if (FD) { QualType Ty = FD->getType(); if (const FunctionProtoType *ProtoType = Ty->getAs<FunctionProtoType>()) if (!ProtoType->isNothrow(getContext())) @@ -382,8 +428,6 @@ void ExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred, if (!isa<CXXConstructExpr>(Init)) { assert(Bldr.getResults().size() == 1); Bldr.takeNodes(NewN); - - assert(!CNE->getType()->getPointeeCXXRecordDecl()); evalBind(Dst, CNE, NewN, Result, State->getSVal(Init, LCtx), /*FirstInit=*/IsStandardGlobalOpNewFunction); } diff --git a/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp b/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp index 06570a4..06328e4 100644 --- a/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp @@ -14,6 +14,7 @@ #define DEBUG_TYPE "ExprEngine" #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" +#include "PrettyStackTraceLocationContext.h" #include "clang/AST/CXXInheritance.h" #include "clang/AST/DeclCXX.h" #include "clang/AST/ParentMap.h" @@ -39,6 +40,8 @@ STATISTIC(NumReachedInlineCountMax, void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) { // Get the entry block in the CFG of the callee. const StackFrameContext *calleeCtx = CE.getCalleeContext(); + PrettyStackTraceLocationContext CrashInfo(calleeCtx); + const CFG *CalleeCFG = calleeCtx->getCFG(); const CFGBlock *Entry = &(CalleeCFG->getEntry()); @@ -214,7 +217,7 @@ static bool isTemporaryPRValue(const CXXConstructExpr *E, SVal V) { /// 5. PostStmt<CallExpr> void ExprEngine::processCallExit(ExplodedNode *CEBNode) { // Step 1 CEBNode was generated before the call. - + PrettyStackTraceLocationContext CrashInfo(CEBNode->getLocationContext()); const StackFrameContext *calleeCtx = CEBNode->getLocationContext()->getCurrentStackFrame(); @@ -717,15 +720,30 @@ static bool isContainerCtorOrDtor(const ASTContext &Ctx, return isContainerClass(Ctx, RD); } +/// Returns true if the given function is the destructor of a class named +/// "shared_ptr". +static bool isCXXSharedPtrDtor(const FunctionDecl *FD) { + const CXXDestructorDecl *Dtor = dyn_cast<CXXDestructorDecl>(FD); + if (!Dtor) + return false; + + const CXXRecordDecl *RD = Dtor->getParent(); + if (const IdentifierInfo *II = RD->getDeclName().getAsIdentifierInfo()) + if (II->isStr("shared_ptr")) + return true; + + return false; +} + /// Returns true if the function in \p CalleeADC may be inlined in general. /// /// This checks static properties of the function, such as its signature and /// CFG, to determine whether the analyzer should ever consider inlining it, /// in any context. -static bool mayInlineDecl(const CallEvent &Call, AnalysisDeclContext *CalleeADC, +static bool mayInlineDecl(AnalysisDeclContext *CalleeADC, AnalyzerOptions &Opts) { // FIXME: Do not inline variadic calls. - if (Call.isVariadic()) + if (CallEvent::isVariadic(CalleeADC->getDecl())) return false; // Check certain C++-related inlining policies. @@ -746,9 +764,18 @@ static bool mayInlineDecl(const CallEvent &Call, AnalysisDeclContext *CalleeADC, // Conditionally control the inlining of methods on objects that look // like C++ containers. if (!Opts.mayInlineCXXContainerCtorsAndDtors()) - if (!Ctx.getSourceManager().isFromMainFile(FD->getLocation())) + if (!Ctx.getSourceManager().isInMainFile(FD->getLocation())) if (isContainerCtorOrDtor(Ctx, FD)) return false; + + // Conditionally control the inlining of the destructor of C++ shared_ptr. + // We don't currently do a good job modeling shared_ptr because we can't + // see the reference count, so treating as opaque is probably the best + // idea. + if (!Opts.mayInlineCXXSharedPtrDtor()) + if (isCXXSharedPtrDtor(FD)) + return false; + } } @@ -780,6 +807,14 @@ bool ExprEngine::shouldInlineCall(const CallEvent &Call, const Decl *D, AnalysisDeclContextManager &ADCMgr = AMgr.getAnalysisDeclContextManager(); AnalysisDeclContext *CalleeADC = ADCMgr.getContext(D); + // Temporary object destructor processing is currently broken, so we never + // inline them. + // FIXME: Remove this once temp destructors are working. + if (isa<CXXDestructorCall>(Call)) { + if ((*currBldrCtx->getBlock())[currStmtIdx].getAs<CFGTemporaryDtor>()) + return false; + } + // The auto-synthesized bodies are essential to inline as they are // usually small and commonly used. Note: we should do this check early on to // ensure we always inline these calls. @@ -798,7 +833,7 @@ bool ExprEngine::shouldInlineCall(const CallEvent &Call, const Decl *D, } else { // We haven't actually checked the static properties of this function yet. // Do that now, and record our decision in the function summaries. - if (mayInlineDecl(Call, CalleeADC, Opts)) { + if (mayInlineDecl(CalleeADC, Opts)) { Engine.FunctionSummaries->markMayInline(D); } else { Engine.FunctionSummaries->markShouldNotInline(D); diff --git a/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp b/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp index 73426da..365f6ab 100644 --- a/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp +++ b/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp @@ -36,7 +36,7 @@ using namespace ento; namespace { class HTMLDiagnostics : public PathDiagnosticConsumer { - llvm::sys::Path Directory, FilePrefix; + std::string Directory; bool createdDir, noDir; const Preprocessor &PP; public: @@ -70,10 +70,7 @@ public: HTMLDiagnostics::HTMLDiagnostics(const std::string& prefix, const Preprocessor &pp) - : Directory(prefix), FilePrefix(prefix), createdDir(false), noDir(false), - PP(pp) { - // All html files begin with "report" - FilePrefix.appendComponent("report"); + : Directory(prefix), createdDir(false), noDir(false), PP(pp) { } void ento::createHTMLDiagnosticConsumer(AnalyzerOptions &AnalyzerOpts, @@ -102,15 +99,11 @@ void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D, // Create the HTML directory if it is missing. if (!createdDir) { createdDir = true; - std::string ErrorMsg; - Directory.createDirectoryOnDisk(true, &ErrorMsg); - - bool IsDirectory; - if (llvm::sys::fs::is_directory(Directory.str(), IsDirectory) || - !IsDirectory) { + bool existed; + if (llvm::error_code ec = + llvm::sys::fs::create_directories(Directory, existed)) { llvm::errs() << "warning: could not create directory '" - << Directory.str() << "'\n" - << "reason: " << ErrorMsg << '\n'; + << Directory << "': " << ec.message() << '\n'; noDir = true; @@ -165,11 +158,11 @@ void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D, // working directory if we have no directory information. This is // a work in progress. - std::string DirName = ""; + llvm::SmallString<0> DirName; if (llvm::sys::path::is_relative(Entry->getName())) { - llvm::sys::Path P = llvm::sys::Path::GetCurrentDirectory(); - DirName = P.str() + "/"; + llvm::sys::fs::current_path(DirName); + DirName += '/'; } // Add the name of the file as an <h1> tag. @@ -228,6 +221,10 @@ void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D, << path.back()->getLocation().asLocation().getExpansionLineNumber() << " -->\n"; + os << "\n<!-- BUGCOLUMN " + << path.back()->getLocation().asLocation().getExpansionColumnNumber() + << " -->\n"; + os << "\n<!-- BUGPATHLENGTH " << path.size() << " -->\n"; // Mark the end of the tags. @@ -250,26 +247,22 @@ void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D, } // Create a path for the target HTML file. - llvm::sys::Path F(FilePrefix); - F.makeUnique(false, NULL); - - // Rename the file with an HTML extension. - llvm::sys::Path H(F); - H.appendSuffix("html"); - F.renamePathOnDisk(H, NULL); - - std::string ErrorMsg; - llvm::raw_fd_ostream os(H.c_str(), ErrorMsg); - - if (!ErrorMsg.empty()) { - llvm::errs() << "warning: could not create file '" << F.str() - << "'\n"; + int FD; + SmallString<128> Model, ResultPath; + llvm::sys::path::append(Model, Directory, "report-%%%%%%.html"); + + if (llvm::error_code EC = + llvm::sys::fs::createUniqueFile(Model.str(), FD, ResultPath)) { + llvm::errs() << "warning: could not create file in '" << Directory + << "': " << EC.message() << '\n'; return; } - if (filesMade) { - filesMade->addDiagnostic(D, getName(), llvm::sys::path::filename(H.str())); - } + llvm::raw_fd_ostream os(FD, true); + + if (filesMade) + filesMade->addDiagnostic(D, getName(), + llvm::sys::path::filename(ResultPath)); // Emit the HTML to disk. for (RewriteBuffer::iterator I = Buf->begin(), E = Buf->end(); I!=E; ++I) diff --git a/lib/StaticAnalyzer/Core/MemRegion.cpp b/lib/StaticAnalyzer/Core/MemRegion.cpp index 42073d4..162cd33 100644 --- a/lib/StaticAnalyzer/Core/MemRegion.cpp +++ b/lib/StaticAnalyzer/Core/MemRegion.cpp @@ -186,7 +186,7 @@ DefinedOrUnknownSVal TypedValueRegion::getExtent(SValBuilder &svalBuilder) const if (isa<VariableArrayType>(T)) return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this)); - if (isa<IncompleteArrayType>(T)) + if (T->isIncompleteType()) return UnknownVal(); CharUnits size = Ctx.getTypeSizeInChars(T); @@ -383,15 +383,17 @@ void BlockTextRegion::Profile(llvm::FoldingSetNodeID& ID) const { void BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const BlockTextRegion *BC, const LocationContext *LC, + unsigned BlkCount, const MemRegion *sReg) { ID.AddInteger(MemRegion::BlockDataRegionKind); ID.AddPointer(BC); ID.AddPointer(LC); + ID.AddInteger(BlkCount); ID.AddPointer(sReg); } void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const { - BlockDataRegion::ProfileRegion(ID, BC, LC, getSuperRegion()); + BlockDataRegion::ProfileRegion(ID, BC, LC, BlockCount, getSuperRegion()); } void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, @@ -464,7 +466,14 @@ void BlockTextRegion::dumpToStream(raw_ostream &os) const { } void BlockDataRegion::dumpToStream(raw_ostream &os) const { - os << "block_data{" << BC << '}'; + os << "block_data{" << BC; + os << "; "; + for (BlockDataRegion::referenced_vars_iterator + I = referenced_vars_begin(), + E = referenced_vars_end(); I != E; ++I) + os << "(" << I.getCapturedRegion() << "," << + I.getOriginalRegion() << ") "; + os << '}'; } void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const { @@ -806,10 +815,19 @@ const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D, sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind, getFunctionTextRegion(cast<NamedDecl>(STCD))); else if (const BlockDecl *BD = dyn_cast<BlockDecl>(STCD)) { + // FIXME: The fallback type here is totally bogus -- though it should + // never be queried, it will prevent uniquing with the real + // BlockTextRegion. Ideally we'd fix the AST so that we always had a + // signature. + QualType T; + if (const TypeSourceInfo *TSI = BD->getSignatureAsWritten()) + T = TSI->getType(); + else + T = getContext().getFunctionNoProtoType(getContext().VoidTy); + const BlockTextRegion *BTR = - getBlockTextRegion(BD, - C.getCanonicalType(BD->getSignatureAsWritten()->getType()), - STC->getAnalysisDeclContext()); + getBlockTextRegion(BD, C.getCanonicalType(T), + STC->getAnalysisDeclContext()); sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind, BTR); } @@ -830,7 +848,8 @@ const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D, const BlockDataRegion * MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC, - const LocationContext *LC) { + const LocationContext *LC, + unsigned blockCount) { const MemRegion *sReg = 0; const BlockDecl *BD = BC->getDecl(); if (!BD->hasCaptures()) { @@ -852,7 +871,13 @@ MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC, } } - return getSubRegion<BlockDataRegion>(BC, LC, sReg); + return getSubRegion<BlockDataRegion>(BC, LC, blockCount, sReg); +} + +const CXXTempObjectRegion * +MemRegionManager::getCXXStaticTempObjectRegion(const Expr *Ex) { + return getSubRegion<CXXTempObjectRegion>( + Ex, getGlobalsRegion(MemRegion::GlobalInternalSpaceRegionKind, NULL)); } const CompoundLiteralRegion* @@ -966,7 +991,7 @@ MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *RD, bool IsVirtual) { if (isa<TypedValueRegion>(Super)) { assert(isValidBaseClass(RD, dyn_cast<TypedValueRegion>(Super), IsVirtual)); - (void)isValidBaseClass; + (void)&isValidBaseClass; if (IsVirtual) { // Virtual base regions should not be layered, since the layout rules @@ -1435,3 +1460,45 @@ const VarRegion *BlockDataRegion::getOriginalRegion(const VarRegion *R) const { } return 0; } + +//===----------------------------------------------------------------------===// +// RegionAndSymbolInvalidationTraits +//===----------------------------------------------------------------------===// + +void RegionAndSymbolInvalidationTraits::setTrait(SymbolRef Sym, + InvalidationKinds IK) { + SymTraitsMap[Sym] |= IK; +} + +void RegionAndSymbolInvalidationTraits::setTrait(const MemRegion *MR, + InvalidationKinds IK) { + assert(MR); + if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) + setTrait(SR->getSymbol(), IK); + else + MRTraitsMap[MR] |= IK; +} + +bool RegionAndSymbolInvalidationTraits::hasTrait(SymbolRef Sym, + InvalidationKinds IK) { + const_symbol_iterator I = SymTraitsMap.find(Sym); + if (I != SymTraitsMap.end()) + return I->second & IK; + + return false; +} + +bool RegionAndSymbolInvalidationTraits::hasTrait(const MemRegion *MR, + InvalidationKinds IK) { + if (!MR) + return false; + + if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) + return hasTrait(SR->getSymbol(), IK); + + const_region_iterator I = MRTraitsMap.find(MR); + if (I != MRTraitsMap.end()) + return I->second & IK; + + return false; +} diff --git a/lib/StaticAnalyzer/Core/PathDiagnostic.cpp b/lib/StaticAnalyzer/Core/PathDiagnostic.cpp index 0351310..b504db6 100644 --- a/lib/StaticAnalyzer/Core/PathDiagnostic.cpp +++ b/lib/StaticAnalyzer/Core/PathDiagnostic.cpp @@ -48,10 +48,11 @@ static StringRef StripTrailingDots(StringRef s) { PathDiagnosticPiece::PathDiagnosticPiece(StringRef s, Kind k, DisplayHint hint) - : str(StripTrailingDots(s)), kind(k), Hint(hint) {} + : str(StripTrailingDots(s)), kind(k), Hint(hint), + LastInMainSourceFile(false) {} PathDiagnosticPiece::PathDiagnosticPiece(Kind k, DisplayHint hint) - : kind(k), Hint(hint) {} + : kind(k), Hint(hint), LastInMainSourceFile(false) {} PathDiagnosticPiece::~PathDiagnosticPiece() {} PathDiagnosticEventPiece::~PathDiagnosticEventPiece() {} @@ -119,6 +120,71 @@ PathDiagnostic::PathDiagnostic(const Decl *declWithIssue, UniqueingDecl(DeclToUnique), path(pathImpl) {} +static PathDiagnosticCallPiece * +getFirstStackedCallToHeaderFile(PathDiagnosticCallPiece *CP, + const SourceManager &SMgr) { + SourceLocation CallLoc = CP->callEnter.asLocation(); + + // If the call is within a macro, don't do anything (for now). + if (CallLoc.isMacroID()) + return 0; + + assert(SMgr.isInMainFile(CallLoc) && + "The call piece should be in the main file."); + + // Check if CP represents a path through a function outside of the main file. + if (!SMgr.isInMainFile(CP->callEnterWithin.asLocation())) + return CP; + + const PathPieces &Path = CP->path; + if (Path.empty()) + return 0; + + // Check if the last piece in the callee path is a call to a function outside + // of the main file. + if (PathDiagnosticCallPiece *CPInner = + dyn_cast<PathDiagnosticCallPiece>(Path.back())) { + return getFirstStackedCallToHeaderFile(CPInner, SMgr); + } + + // Otherwise, the last piece is in the main file. + return 0; +} + +void PathDiagnostic::resetDiagnosticLocationToMainFile() { + if (path.empty()) + return; + + PathDiagnosticPiece *LastP = path.back().getPtr(); + assert(LastP); + const SourceManager &SMgr = LastP->getLocation().getManager(); + + // We only need to check if the report ends inside headers, if the last piece + // is a call piece. + if (PathDiagnosticCallPiece *CP = dyn_cast<PathDiagnosticCallPiece>(LastP)) { + CP = getFirstStackedCallToHeaderFile(CP, SMgr); + if (CP) { + // Mark the piece. + CP->setAsLastInMainSourceFile(); + + // Update the path diagnostic message. + const NamedDecl *ND = dyn_cast<NamedDecl>(CP->getCallee()); + if (ND) { + SmallString<200> buf; + llvm::raw_svector_ostream os(buf); + os << " (within a call to '" << ND->getDeclName() << "')"; + appendToDesc(os.str()); + } + + // Reset the report containing declaration and location. + DeclWithIssue = CP->getCaller(); + Loc = CP->getLocation(); + + return; + } + } +} + void PathDiagnosticConsumer::anchor() { } PathDiagnosticConsumer::~PathDiagnosticConsumer() { @@ -150,11 +216,10 @@ void PathDiagnosticConsumer::HandlePathDiagnostic(PathDiagnostic *D) { WorkList.push_back(&D->path); while (!WorkList.empty()) { - const PathPieces &path = *WorkList.back(); - WorkList.pop_back(); + const PathPieces &path = *WorkList.pop_back_val(); - for (PathPieces::const_iterator I = path.begin(), E = path.end(); - I != E; ++I) { + for (PathPieces::const_iterator I = path.begin(), E = path.end(); I != E; + ++I) { const PathDiagnosticPiece *piece = I->getPtr(); FullSourceLoc L = piece->getLocation().asLocation().getExpansionLoc(); @@ -494,6 +559,10 @@ getLocationForCaller(const StackFrameContext *SFC, return PathDiagnosticLocation::createEnd(Dtor.getTriggerStmt(), SM, CallerCtx); } + case CFGElement::DeleteDtor: { + const CFGDeleteDtor &Dtor = Source.castAs<CFGDeleteDtor>(); + return PathDiagnosticLocation(Dtor.getDeleteExpr(), SM, CallerCtx); + } case CFGElement::BaseDtor: case CFGElement::MemberDtor: { const AnalysisDeclContext *CallerInfo = CallerCtx->getAnalysisDeclContext(); @@ -916,7 +985,7 @@ IntrusiveRefCntPtr<PathDiagnosticEventPiece> PathDiagnosticCallPiece::getCallEnterWithinCallerEvent() const { if (!callEnterWithin.asLocation().isValid()) return 0; - if (Callee->isImplicit()) + if (Callee->isImplicit() || !Callee->hasBody()) return 0; if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(Callee)) if (MD->isDefaulted()) diff --git a/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp b/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp index 8509555..5dca811 100644 --- a/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp +++ b/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp @@ -50,7 +50,6 @@ namespace { PathGenerationScheme getGenerationScheme() const { return Extensive; } bool supportsLogicalOpControlFlow() const { return true; } - bool supportsAllBlockEdges() const { return true; } virtual bool supportsCrossFileDiagnostics() const { return SupportsCrossFileDiagnostics; } @@ -215,13 +214,18 @@ static void ReportEvent(raw_ostream &o, const PathDiagnosticPiece& P, const SourceManager &SM, const LangOptions &LangOpts, unsigned indent, - unsigned depth) { + unsigned depth, + bool isKeyEvent = false) { Indent(o, indent) << "<dict>\n"; ++indent; Indent(o, indent) << "<key>kind</key><string>event</string>\n"; + if (isKeyEvent) { + Indent(o, indent) << "<key>key_event</key><true/>\n"; + } + // Output the location. FullSourceLoc L = P.getLocation().asLocation(); @@ -270,7 +274,8 @@ static void ReportPiece(raw_ostream &o, const LangOptions &LangOpts, unsigned indent, unsigned depth, - bool includeControlFlow); + bool includeControlFlow, + bool isKeyEvent = false); static void ReportCall(raw_ostream &o, const PathDiagnosticCallPiece &P, @@ -283,7 +288,8 @@ static void ReportCall(raw_ostream &o, P.getCallEnterEvent(); if (callEnter) - ReportPiece(o, *callEnter, FM, SM, LangOpts, indent, depth, true); + ReportPiece(o, *callEnter, FM, SM, LangOpts, indent, depth, true, + P.isLastInMainSourceFile()); IntrusiveRefCntPtr<PathDiagnosticEventPiece> callEnterWithinCaller = P.getCallEnterWithinCallerEvent(); @@ -331,7 +337,8 @@ static void ReportPiece(raw_ostream &o, const LangOptions &LangOpts, unsigned indent, unsigned depth, - bool includeControlFlow) { + bool includeControlFlow, + bool isKeyEvent) { switch (P.getKind()) { case PathDiagnosticPiece::ControlFlow: if (includeControlFlow) @@ -344,7 +351,7 @@ static void ReportPiece(raw_ostream &o, break; case PathDiagnosticPiece::Event: ReportEvent(o, cast<PathDiagnosticSpotPiece>(P), FM, SM, LangOpts, - indent, depth); + indent, depth, isKeyEvent); break; case PathDiagnosticPiece::Macro: ReportMacro(o, cast<PathDiagnosticMacroPiece>(P), FM, SM, LangOpts, @@ -375,11 +382,10 @@ void PlistDiagnostics::FlushDiagnosticsImpl( WorkList.push_back(&D->path); while (!WorkList.empty()) { - const PathPieces &path = *WorkList.back(); - WorkList.pop_back(); - - for (PathPieces::const_iterator I = path.begin(), E = path.end(); - I!=E; ++I) { + const PathPieces &path = *WorkList.pop_back_val(); + + for (PathPieces::const_iterator I = path.begin(), E = path.end(); I != E; + ++I) { const PathDiagnosticPiece *piece = I->getPtr(); AddFID(FM, Fids, SM, piece->getLocation().asLocation()); ArrayRef<SourceRange> Ranges = piece->getRanges(); diff --git a/lib/StaticAnalyzer/Core/PrettyStackTraceLocationContext.h b/lib/StaticAnalyzer/Core/PrettyStackTraceLocationContext.h new file mode 100644 index 0000000..ed64fcb --- /dev/null +++ b/lib/StaticAnalyzer/Core/PrettyStackTraceLocationContext.h @@ -0,0 +1,45 @@ +//==- PrettyStackTraceLocationContext.h - show analysis backtrace --*- C++ -*-// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_STATICANALYZER_PRETTYSTACKTRACELOCATIONCONTEXT_H +#define LLVM_CLANG_STATICANALYZER_PRETTYSTACKTRACELOCATIONCONTEXT_H + +#include "clang/Analysis/AnalysisContext.h" + +namespace clang { +namespace ento { + +/// While alive, includes the current analysis stack in a crash trace. +/// +/// Example: +/// \code +/// 0. Program arguments: ... +/// 1. <eof> parser at end of file +/// 2. While analyzing stack: +/// #0 void inlined() +/// #1 void test() +/// 3. crash-trace.c:6:3: Error evaluating statement +/// \endcode +class PrettyStackTraceLocationContext : public llvm::PrettyStackTraceEntry { + const LocationContext *LCtx; +public: + PrettyStackTraceLocationContext(const LocationContext *LC) : LCtx(LC) { + assert(LCtx); + } + + virtual void print(raw_ostream &OS) const { + OS << "While analyzing stack: \n"; + LCtx->dumpStack(OS, "\t"); + } +}; + +} // end ento namespace +} // end clang namespace + +#endif diff --git a/lib/StaticAnalyzer/Core/ProgramState.cpp b/lib/StaticAnalyzer/Core/ProgramState.cpp index 653b69b..6e23668 100644 --- a/lib/StaticAnalyzer/Core/ProgramState.cpp +++ b/lib/StaticAnalyzer/Core/ProgramState.cpp @@ -137,48 +137,32 @@ typedef ArrayRef<SVal> ValueList; ProgramStateRef ProgramState::invalidateRegions(RegionList Regions, - const Expr *E, unsigned Count, - const LocationContext *LCtx, - bool CausedByPointerEscape, - InvalidatedSymbols *IS, - const CallEvent *Call, - RegionList ConstRegions) const { + const Expr *E, unsigned Count, + const LocationContext *LCtx, + bool CausedByPointerEscape, + InvalidatedSymbols *IS, + const CallEvent *Call, + RegionAndSymbolInvalidationTraits *ITraits) const { SmallVector<SVal, 8> Values; for (RegionList::const_iterator I = Regions.begin(), End = Regions.end(); I != End; ++I) Values.push_back(loc::MemRegionVal(*I)); - SmallVector<SVal, 8> ConstValues; - for (RegionList::const_iterator I = ConstRegions.begin(), - End = ConstRegions.end(); I != End; ++I) - ConstValues.push_back(loc::MemRegionVal(*I)); - - if (!IS) { - InvalidatedSymbols invalidated; - return invalidateRegionsImpl(Values, E, Count, LCtx, - CausedByPointerEscape, - invalidated, Call, ConstValues); - } return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, - *IS, Call, ConstValues); + IS, ITraits, Call); } ProgramStateRef ProgramState::invalidateRegions(ValueList Values, - const Expr *E, unsigned Count, - const LocationContext *LCtx, - bool CausedByPointerEscape, - InvalidatedSymbols *IS, - const CallEvent *Call, - ValueList ConstValues) const { - if (!IS) { - InvalidatedSymbols invalidated; - return invalidateRegionsImpl(Values, E, Count, LCtx, - CausedByPointerEscape, - invalidated, Call, ConstValues); - } + const Expr *E, unsigned Count, + const LocationContext *LCtx, + bool CausedByPointerEscape, + InvalidatedSymbols *IS, + const CallEvent *Call, + RegionAndSymbolInvalidationTraits *ITraits) const { + return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, - *IS, Call, ConstValues); + IS, ITraits, Call); } ProgramStateRef @@ -186,49 +170,45 @@ ProgramState::invalidateRegionsImpl(ValueList Values, const Expr *E, unsigned Count, const LocationContext *LCtx, bool CausedByPointerEscape, - InvalidatedSymbols &IS, - const CallEvent *Call, - ValueList ConstValues) const { + InvalidatedSymbols *IS, + RegionAndSymbolInvalidationTraits *ITraits, + const CallEvent *Call) const { ProgramStateManager &Mgr = getStateManager(); SubEngine* Eng = Mgr.getOwningEngine(); InvalidatedSymbols ConstIS; + InvalidatedSymbols Invalidated; + if (!IS) + IS = &Invalidated; + + RegionAndSymbolInvalidationTraits ITraitsLocal; + if (!ITraits) + ITraits = &ITraitsLocal; + if (Eng) { StoreManager::InvalidatedRegions TopLevelInvalidated; - StoreManager::InvalidatedRegions TopLevelConstInvalidated; StoreManager::InvalidatedRegions Invalidated; const StoreRef &newStore - = Mgr.StoreMgr->invalidateRegions(getStore(), Values, ConstValues, - E, Count, LCtx, Call, - IS, ConstIS, - &TopLevelInvalidated, - &TopLevelConstInvalidated, + = Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call, + *IS, *ITraits, &TopLevelInvalidated, &Invalidated); ProgramStateRef newState = makeWithStore(newStore); if (CausedByPointerEscape) { - newState = Eng->notifyCheckersOfPointerEscape(newState, &IS, + newState = Eng->notifyCheckersOfPointerEscape(newState, IS, TopLevelInvalidated, - Invalidated, Call); - if (!ConstValues.empty()) { - StoreManager::InvalidatedRegions Empty; - newState = Eng->notifyCheckersOfPointerEscape(newState, &ConstIS, - TopLevelConstInvalidated, - Empty, Call, - true); - } + Invalidated, Call, + *ITraits); } - return Eng->processRegionChanges(newState, &IS, - TopLevelInvalidated, Invalidated, - Call); + return Eng->processRegionChanges(newState, IS, TopLevelInvalidated, + Invalidated, Call); } const StoreRef &newStore = - Mgr.StoreMgr->invalidateRegions(getStore(), Values, ConstValues, - E, Count, LCtx, Call, - IS, ConstIS, NULL, NULL, NULL); + Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call, + *IS, *ITraits, NULL, NULL); return makeWithStore(newStore); } @@ -526,6 +506,19 @@ ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) return getPersistentState(NewState); } +bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) { + bool wasVisited = !visited.insert(val.getCVData()).second; + if (wasVisited) + return true; + + StoreManager &StoreMgr = state->getStateManager().getStoreManager(); + // FIXME: We don't really want to use getBaseRegion() here because pointer + // arithmetic doesn't apply, but scanReachableSymbols only accepts base + // regions right now. + const MemRegion *R = val.getRegion()->getBaseRegion(); + return StoreMgr.scanReachableSymbols(val.getStore(), R, *this); +} + bool ScanReachableSymbols::scan(nonloc::CompoundVal val) { for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) if (!scan(*I)) @@ -535,10 +528,9 @@ bool ScanReachableSymbols::scan(nonloc::CompoundVal val) { } bool ScanReachableSymbols::scan(const SymExpr *sym) { - unsigned &isVisited = visited[sym]; - if (isVisited) + bool wasVisited = !visited.insert(sym).second; + if (wasVisited) return true; - isVisited = 1; if (!visitor.VisitSymbol(sym)) return false; @@ -570,16 +562,8 @@ bool ScanReachableSymbols::scan(SVal val) { return scan(X->getRegion()); if (Optional<nonloc::LazyCompoundVal> X = - val.getAs<nonloc::LazyCompoundVal>()) { - StoreManager &StoreMgr = state->getStateManager().getStoreManager(); - // FIXME: We don't really want to use getBaseRegion() here because pointer - // arithmetic doesn't apply, but scanReachableSymbols only accepts base - // regions right now. - if (!StoreMgr.scanReachableSymbols(X->getStore(), - X->getRegion()->getBaseRegion(), - *this)) - return false; - } + val.getAs<nonloc::LazyCompoundVal>()) + return scan(*X); if (Optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>()) return scan(X->getLoc()); @@ -600,11 +584,9 @@ bool ScanReachableSymbols::scan(const MemRegion *R) { if (isa<MemSpaceRegion>(R)) return true; - unsigned &isVisited = visited[R]; - if (isVisited) + bool wasVisited = !visited.insert(R).second; + if (wasVisited) return true; - isVisited = 1; - if (!visitor.VisitMemRegion(R)) return false; diff --git a/lib/StaticAnalyzer/Core/RegionStore.cpp b/lib/StaticAnalyzer/Core/RegionStore.cpp index 88c4eee..0b51976 100644 --- a/lib/StaticAnalyzer/Core/RegionStore.cpp +++ b/lib/StaticAnalyzer/Core/RegionStore.cpp @@ -349,7 +349,6 @@ private: /// regions. void populateWorkList(invalidateRegionsWorker &W, ArrayRef<SVal> Values, - bool IsArrayOfConstRegions, InvalidatedRegions *TopLevelRegions); public: @@ -377,7 +376,7 @@ public: /// version of that lvalue (i.e., a pointer to the first element of /// the array). This is called by ExprEngine when evaluating /// casts from arrays to pointers. - SVal ArrayToPointer(Loc Array); + SVal ArrayToPointer(Loc Array, QualType ElementTy); StoreRef getInitialStore(const LocationContext *InitLoc) { return StoreRef(RBFactory.getEmptyMap().getRootWithoutRetain(), *this); @@ -395,15 +394,13 @@ public: StoreRef invalidateRegions(Store store, ArrayRef<SVal> Values, - ArrayRef<SVal> ConstValues, const Expr *E, unsigned Count, const LocationContext *LCtx, const CallEvent *Call, InvalidatedSymbols &IS, - InvalidatedSymbols &ConstIS, + RegionAndSymbolInvalidationTraits &ITraits, InvalidatedRegions *Invalidated, - InvalidatedRegions *InvalidatedTopLevel, - InvalidatedRegions *InvalidatedTopLevelConst); + InvalidatedRegions *InvalidatedTopLevel); bool scanReachableSymbols(Store S, const MemRegion *R, ScanReachableSymbols &Callbacks); @@ -422,11 +419,20 @@ public: // Part of public interface to class. // BindDefault is only used to initialize a region with a default value. StoreRef BindDefault(Store store, const MemRegion *R, SVal V) { RegionBindingsRef B = getRegionBindings(store); - assert(!B.lookup(R, BindingKey::Default)); assert(!B.lookup(R, BindingKey::Direct)); - return StoreRef(B.addBinding(R, BindingKey::Default, V) - .asImmutableMap() - .getRootWithoutRetain(), *this); + + BindingKey Key = BindingKey::Make(R, BindingKey::Default); + if (B.lookup(Key)) { + const SubRegion *SR = cast<SubRegion>(R); + assert(SR->getAsOffset().getOffset() == + SR->getSuperRegion()->getAsOffset().getOffset() && + "A default value must come from a super-region"); + B = removeSubRegionBindings(B, SR); + } else { + B = B.addBinding(Key, V); + } + + return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this); } /// Attempt to extract the fields of \p LCV and bind them to the struct region @@ -639,7 +645,7 @@ template <typename DERIVED> class ClusterAnalysis { protected: typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap; - typedef llvm::PointerIntPair<const MemRegion *, 1, bool> WorkListElement; + typedef const MemRegion * WorkListElement; typedef SmallVector<WorkListElement, 10> WorkList; llvm::SmallPtrSet<const ClusterBindings *, 16> Visited; @@ -711,18 +717,17 @@ public: return true; } - bool AddToWorkList(const MemRegion *R, bool Flag = false) { + bool AddToWorkList(const MemRegion *R) { const MemRegion *BaseR = R->getBaseRegion(); - return AddToWorkList(WorkListElement(BaseR, Flag), getCluster(BaseR)); + return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR)); } void RunWorkList() { while (!WL.empty()) { WorkListElement E = WL.pop_back_val(); - const MemRegion *BaseR = E.getPointer(); + const MemRegion *BaseR = E; - static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR), - E.getInt()); + static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR)); } } @@ -942,7 +947,7 @@ class invalidateRegionsWorker : public ClusterAnalysis<invalidateRegionsWorker> unsigned Count; const LocationContext *LCtx; InvalidatedSymbols &IS; - InvalidatedSymbols &ConstIS; + RegionAndSymbolInvalidationTraits &ITraits; StoreManager::InvalidatedRegions *Regions; public: invalidateRegionsWorker(RegionStoreManager &rm, @@ -951,16 +956,13 @@ public: const Expr *ex, unsigned count, const LocationContext *lctx, InvalidatedSymbols &is, - InvalidatedSymbols &inConstIS, + RegionAndSymbolInvalidationTraits &ITraitsIn, StoreManager::InvalidatedRegions *r, GlobalsFilterKind GFK) : ClusterAnalysis<invalidateRegionsWorker>(rm, stateMgr, b, GFK), - Ex(ex), Count(count), LCtx(lctx), IS(is), ConstIS(inConstIS), Regions(r){} + Ex(ex), Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r){} - /// \param IsConst Specifies if the region we are invalidating is constant. - /// If it is, we invalidate all subregions, but not the base region itself. - void VisitCluster(const MemRegion *baseR, const ClusterBindings *C, - bool IsConst); + void VisitCluster(const MemRegion *baseR, const ClusterBindings *C); void VisitBinding(SVal V); }; } @@ -991,14 +993,18 @@ void invalidateRegionsWorker::VisitBinding(SVal V) { } void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR, - const ClusterBindings *C, - bool IsConst) { + const ClusterBindings *C) { + + bool PreserveRegionsContents = + ITraits.hasTrait(baseR, + RegionAndSymbolInvalidationTraits::TK_PreserveContents); + if (C) { for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) VisitBinding(I.getData()); - // Invalidate the contents of a non-const base region. - if (!IsConst) + // Invalidate regions contents. + if (!PreserveRegionsContents) B = B.remove(baseR); } @@ -1030,18 +1036,11 @@ void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR, } // Symbolic region? - if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { - SymbolRef RegionSym = SR->getSymbol(); - - // Mark that symbol touched by the invalidation. - if (IsConst) - ConstIS.insert(RegionSym); - else - IS.insert(RegionSym); - } + if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) + IS.insert(SR->getSymbol()); - // Nothing else should be done for a const region. - if (IsConst) + // Nothing else should be done in the case when we preserve regions context. + if (PreserveRegionsContents) return; // Otherwise, we have a normal data region. Record that we touched the region. @@ -1050,7 +1049,7 @@ void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR, if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) { // Invalidate the region by setting its default value to - // conjured symbol. The type of the symbol is irrelavant. + // conjured symbol. The type of the symbol is irrelevant. DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); B = B.addBinding(baseR, BindingKey::Default, V); @@ -1072,7 +1071,7 @@ void invalidateRegionsWorker::VisitCluster(const MemRegion *baseR, if (T->isStructureOrClassType()) { // Invalidate the region by setting its default value to - // conjured symbol. The type of the symbol is irrelavant. + // conjured symbol. The type of the symbol is irrelevant. DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); B = B.addBinding(baseR, BindingKey::Default, V); @@ -1121,7 +1120,6 @@ RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, void RegionStoreManager::populateWorkList(invalidateRegionsWorker &W, ArrayRef<SVal> Values, - bool IsArrayOfConstRegions, InvalidatedRegions *TopLevelRegions) { for (ArrayRef<SVal>::iterator I = Values.begin(), E = Values.end(); I != E; ++I) { @@ -1136,7 +1134,7 @@ void RegionStoreManager::populateWorkList(invalidateRegionsWorker &W, // Note: the last argument is false here because these are // non-top-level regions. if (const MemRegion *R = (*I).getAsRegion()) - W.AddToWorkList(R, /*IsConst=*/ false); + W.AddToWorkList(R); } continue; } @@ -1144,7 +1142,7 @@ void RegionStoreManager::populateWorkList(invalidateRegionsWorker &W, if (const MemRegion *R = V.getAsRegion()) { if (TopLevelRegions) TopLevelRegions->push_back(R); - W.AddToWorkList(R, /*IsConst=*/ IsArrayOfConstRegions); + W.AddToWorkList(R); continue; } } @@ -1152,16 +1150,14 @@ void RegionStoreManager::populateWorkList(invalidateRegionsWorker &W, StoreRef RegionStoreManager::invalidateRegions(Store store, - ArrayRef<SVal> Values, - ArrayRef<SVal> ConstValues, - const Expr *Ex, unsigned Count, - const LocationContext *LCtx, - const CallEvent *Call, - InvalidatedSymbols &IS, - InvalidatedSymbols &ConstIS, - InvalidatedRegions *TopLevelRegions, - InvalidatedRegions *TopLevelConstRegions, - InvalidatedRegions *Invalidated) { + ArrayRef<SVal> Values, + const Expr *Ex, unsigned Count, + const LocationContext *LCtx, + const CallEvent *Call, + InvalidatedSymbols &IS, + RegionAndSymbolInvalidationTraits &ITraits, + InvalidatedRegions *TopLevelRegions, + InvalidatedRegions *Invalidated) { GlobalsFilterKind GlobalsFilter; if (Call) { if (Call->isInSystemHeader()) @@ -1173,17 +1169,14 @@ RegionStoreManager::invalidateRegions(Store store, } RegionBindingsRef B = getRegionBindings(store); - invalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ConstIS, + invalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ITraits, Invalidated, GlobalsFilter); // Scan the bindings and generate the clusters. W.GenerateClusters(); // Add the regions to the worklist. - populateWorkList(W, Values, /*IsArrayOfConstRegions*/ false, - TopLevelRegions); - populateWorkList(W, ConstValues, /*IsArrayOfConstRegions*/ true, - TopLevelConstRegions); + populateWorkList(W, Values, TopLevelRegions); W.RunWorkList(); @@ -1250,23 +1243,13 @@ RegionStoreManager::getSizeInElements(ProgramStateRef state, /// version of that lvalue (i.e., a pointer to the first element of /// the array). This is called by ExprEngine when evaluating casts /// from arrays to pointers. -SVal RegionStoreManager::ArrayToPointer(Loc Array) { +SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) { if (!Array.getAs<loc::MemRegionVal>()) return UnknownVal(); const MemRegion* R = Array.castAs<loc::MemRegionVal>().getRegion(); - const TypedValueRegion* ArrayR = dyn_cast<TypedValueRegion>(R); - - if (!ArrayR) - return UnknownVal(); - - // Strip off typedefs from the ArrayRegion's ValueType. - QualType T = ArrayR->getValueType().getDesugaredType(Ctx); - const ArrayType *AT = cast<ArrayType>(T); - T = AT->getElementType(); - NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex(); - return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR, Ctx)); + return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, R, Ctx)); } //===----------------------------------------------------------------------===// @@ -1329,7 +1312,7 @@ SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) // FIXME: Handle unions. if (RTy->isUnionType()) - return UnknownVal(); + return createLazyBinding(B, R); if (RTy->isArrayType()) { if (RTy->isConstantArrayType()) @@ -1507,7 +1490,7 @@ SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B, // FIXME: Handle loads from strings where the literal is treated as // an integer, e.g., *((unsigned int*)"hello") QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType(); - if (T != Ctx.getCanonicalType(R->getElementType())) + if (!Ctx.hasSameUnqualifiedType(T, R->getElementType())) return UnknownVal(); const StringLiteral *Str = StrR->getStringLiteral(); @@ -1842,10 +1825,18 @@ NonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B, return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *this), R); } +static bool isRecordEmpty(const RecordDecl *RD) { + if (!RD->field_empty()) + return false; + if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(RD)) + return CRD->getNumBases() == 0; + return true; +} + SVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B, const TypedValueRegion *R) { const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl(); - if (RD->field_empty()) + if (!RD->getDefinition() || isRecordEmpty(RD)) return UnknownVal(); return createLazyBinding(B, R); @@ -1915,6 +1906,8 @@ RegionStoreManager::bind(RegionBindingsConstRef B, Loc L, SVal V) { return bindStruct(B, TR, V); if (Ty->isVectorType()) return bindVector(B, TR, V); + if (Ty->isUnionType()) + return bindAggregate(B, TR, V); } if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { diff --git a/lib/StaticAnalyzer/Core/SValBuilder.cpp b/lib/StaticAnalyzer/Core/SValBuilder.cpp index 9d77a3e..adc5465 100644 --- a/lib/StaticAnalyzer/Core/SValBuilder.cpp +++ b/lib/StaticAnalyzer/Core/SValBuilder.cpp @@ -202,10 +202,12 @@ DefinedSVal SValBuilder::getFunctionPointer(const FunctionDecl *func) { DefinedSVal SValBuilder::getBlockPointer(const BlockDecl *block, CanQualType locTy, - const LocationContext *locContext) { + const LocationContext *locContext, + unsigned blockCount) { const BlockTextRegion *BC = MemMgr.getBlockTextRegion(block, locTy, locContext->getAnalysisDeclContext()); - const BlockDataRegion *BD = MemMgr.getBlockDataRegion(BC, locContext); + const BlockDataRegion *BD = MemMgr.getBlockDataRegion(BC, locContext, + blockCount); return loc::MemRegionVal(BD); } @@ -266,6 +268,17 @@ Optional<SVal> SValBuilder::getConstantVal(const Expr *E) { case Stmt::CXXNullPtrLiteralExprClass: return makeNull(); + case Stmt::ImplicitCastExprClass: { + const CastExpr *CE = cast<CastExpr>(E); + if (CE->getCastKind() == CK_ArrayToPointerDecay) { + Optional<SVal> ArrayVal = getConstantVal(CE->getSubExpr()); + if (!ArrayVal) + return None; + return evalCast(*ArrayVal, CE->getType(), CE->getSubExpr()->getType()); + } + // FALLTHROUGH + } + // If we don't have a special case, fall back to the AST's constant evaluator. default: { // Don't try to come up with a value for materialized temporaries. @@ -394,15 +407,22 @@ SVal SValBuilder::evalCast(SVal val, QualType castTy, QualType originalTy) { return val; if (val.isConstant()) return makeTruthVal(!val.isZeroConstant(), castTy); - if (SymbolRef Sym = val.getAsSymbol()) { + if (!Loc::isLocType(originalTy) && + !originalTy->isIntegralOrEnumerationType() && + !originalTy->isMemberPointerType()) + return UnknownVal(); + if (SymbolRef Sym = val.getAsSymbol(true)) { BasicValueFactory &BVF = getBasicValueFactory(); // FIXME: If we had a state here, we could see if the symbol is known to // be zero, but we don't. return makeNonLoc(Sym, BO_NE, BVF.getValue(0, Sym->getType()), castTy); } + // Loc values are not always true, they could be weakly linked functions. + if (Optional<Loc> L = val.getAs<Loc>()) + return evalCastFromLoc(*L, castTy); - assert(val.getAs<Loc>()); - return makeTruthVal(true, castTy); + Loc L = val.castAs<nonloc::LocAsInteger>().getLoc(); + return evalCastFromLoc(L, castTy); } // For const casts, casts to void, just propagate the value. @@ -435,9 +455,11 @@ SVal SValBuilder::evalCast(SVal val, QualType castTy, QualType originalTy) { } // Check for casts from array type to another type. - if (originalTy->isArrayType()) { + if (const ArrayType *arrayT = + dyn_cast<ArrayType>(originalTy.getCanonicalType())) { // We will always decay to a pointer. - val = StateMgr.ArrayToPointer(val.castAs<Loc>()); + QualType elemTy = arrayT->getElementType(); + val = StateMgr.ArrayToPointer(val.castAs<Loc>(), elemTy); // Are we casting from an array to a pointer? If so just pass on // the decayed value. diff --git a/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp b/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp index a06268d..e6653ae 100644 --- a/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp +++ b/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp @@ -68,51 +68,20 @@ bool SimpleConstraintManager::canReasonAbout(SVal X) const { ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef state, DefinedSVal Cond, bool Assumption) { - if (Optional<NonLoc> NV = Cond.getAs<NonLoc>()) - return assume(state, *NV, Assumption); - return assume(state, Cond.castAs<Loc>(), Assumption); -} - -ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef state, Loc cond, - bool assumption) { - state = assumeAux(state, cond, assumption); - if (NotifyAssumeClients && SU) - return SU->processAssume(state, cond, assumption); - return state; -} - -ProgramStateRef SimpleConstraintManager::assumeAux(ProgramStateRef state, - Loc Cond, bool Assumption) { - switch (Cond.getSubKind()) { - default: - assert (false && "'Assume' not implemented for this Loc."); - return state; - - case loc::MemRegionKind: { - // FIXME: Should this go into the storemanager? - const MemRegion *R = Cond.castAs<loc::MemRegionVal>().getRegion(); - - // FIXME: now we only find the first symbolic region. - if (const SymbolicRegion *SymR = R->getSymbolicBase()) { - const llvm::APSInt &zero = getBasicVals().getZeroWithPtrWidth(); - if (Assumption) - return assumeSymNE(state, SymR->getSymbol(), zero, zero); - else - return assumeSymEQ(state, SymR->getSymbol(), zero, zero); - } - - // FALL-THROUGH. + // If we have a Loc value, cast it to a bool NonLoc first. + if (Optional<Loc> LV = Cond.getAs<Loc>()) { + SValBuilder &SVB = state->getStateManager().getSValBuilder(); + QualType T; + const MemRegion *MR = LV->getAsRegion(); + if (const TypedRegion *TR = dyn_cast_or_null<TypedRegion>(MR)) + T = TR->getLocationType(); + else + T = SVB.getContext().VoidPtrTy; + + Cond = SVB.evalCast(*LV, SVB.getContext().BoolTy, T).castAs<DefinedSVal>(); } - case loc::GotoLabelKind: - return Assumption ? state : NULL; - - case loc::ConcreteIntKind: { - bool b = Cond.castAs<loc::ConcreteInt>().getValue() != 0; - bool isFeasible = b ? Assumption : !Assumption; - return isFeasible ? state : NULL; - } - } // end switch + return assume(state, Cond.castAs<NonLoc>(), Assumption); } ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef state, @@ -216,8 +185,8 @@ ProgramStateRef SimpleConstraintManager::assumeAux(ProgramStateRef state, } case nonloc::LocAsIntegerKind: - return assumeAux(state, Cond.castAs<nonloc::LocAsInteger>().getLoc(), - Assumption); + return assume(state, Cond.castAs<nonloc::LocAsInteger>().getLoc(), + Assumption); } // end switch } diff --git a/lib/StaticAnalyzer/Core/SimpleConstraintManager.h b/lib/StaticAnalyzer/Core/SimpleConstraintManager.h index 10ddef1..28a9a4d 100644 --- a/lib/StaticAnalyzer/Core/SimpleConstraintManager.h +++ b/lib/StaticAnalyzer/Core/SimpleConstraintManager.h @@ -36,8 +36,6 @@ public: ProgramStateRef assume(ProgramStateRef state, DefinedSVal Cond, bool Assumption); - ProgramStateRef assume(ProgramStateRef state, Loc Cond, bool Assumption); - ProgramStateRef assume(ProgramStateRef state, NonLoc Cond, bool Assumption); ProgramStateRef assumeSymRel(ProgramStateRef state, @@ -87,10 +85,6 @@ protected: bool canReasonAbout(SVal X) const; ProgramStateRef assumeAux(ProgramStateRef state, - Loc Cond, - bool Assumption); - - ProgramStateRef assumeAux(ProgramStateRef state, NonLoc Cond, bool Assumption); diff --git a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp index ee627f2..cc0ee0b 100644 --- a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp +++ b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp @@ -137,6 +137,32 @@ SVal SimpleSValBuilder::evalCastFromLoc(Loc val, QualType castTy) { if (castTy->isUnionType()) return UnknownVal(); + // Casting a Loc to a bool will almost always be true, + // unless this is a weak function or a symbolic region. + if (castTy->isBooleanType()) { + switch (val.getSubKind()) { + case loc::MemRegionKind: { + const MemRegion *R = val.castAs<loc::MemRegionVal>().getRegion(); + if (const FunctionTextRegion *FTR = dyn_cast<FunctionTextRegion>(R)) + if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl())) + if (FD->isWeak()) + // FIXME: Currently we are using an extent symbol here, + // because there are no generic region address metadata + // symbols to use, only content metadata. + return nonloc::SymbolVal(SymMgr.getExtentSymbol(FTR)); + + if (const SymbolicRegion *SymR = R->getSymbolicBase()) + return nonloc::SymbolVal(SymR->getSymbol()); + + // FALL-THROUGH + } + + case loc::GotoLabelKind: + // Labels and non symbolic memory regions are always true. + return makeTruthVal(true, castTy); + } + } + if (castTy->isIntegralOrEnumerationType()) { unsigned BitWidth = Context.getTypeSize(castTy); @@ -507,6 +533,53 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, } } +static SVal evalBinOpFieldRegionFieldRegion(const FieldRegion *LeftFR, + const FieldRegion *RightFR, + BinaryOperator::Opcode op, + QualType resultTy, + SimpleSValBuilder &SVB) { + // Only comparisons are meaningful here! + if (!BinaryOperator::isComparisonOp(op)) + return UnknownVal(); + + // Next, see if the two FRs have the same super-region. + // FIXME: This doesn't handle casts yet, and simply stripping the casts + // doesn't help. + if (LeftFR->getSuperRegion() != RightFR->getSuperRegion()) + return UnknownVal(); + + const FieldDecl *LeftFD = LeftFR->getDecl(); + const FieldDecl *RightFD = RightFR->getDecl(); + const RecordDecl *RD = LeftFD->getParent(); + + // Make sure the two FRs are from the same kind of record. Just in case! + // FIXME: This is probably where inheritance would be a problem. + if (RD != RightFD->getParent()) + return UnknownVal(); + + // We know for sure that the two fields are not the same, since that + // would have given us the same SVal. + if (op == BO_EQ) + return SVB.makeTruthVal(false, resultTy); + if (op == BO_NE) + return SVB.makeTruthVal(true, resultTy); + + // Iterate through the fields and see which one comes first. + // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field + // members and the units in which bit-fields reside have addresses that + // increase in the order in which they are declared." + bool leftFirst = (op == BO_LT || op == BO_LE); + for (RecordDecl::field_iterator I = RD->field_begin(), + E = RD->field_end(); I!=E; ++I) { + if (*I == LeftFD) + return SVB.makeTruthVal(leftFirst, resultTy); + if (*I == RightFD) + return SVB.makeTruthVal(!leftFirst, resultTy); + } + + llvm_unreachable("Fields not found in parent record's definition"); +} + // FIXME: all this logic will change if/when we have MemRegion::getLocation(). SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op, @@ -621,7 +694,7 @@ SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) { // If one of the operands is a symbol and the other is a constant, // build an expression for use by the constraint manager. - if (SymbolRef lSym = lhs.getAsLocSymbol()) + if (SymbolRef lSym = lhs.getAsLocSymbol(true)) return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy); // Special case comparisons to NULL. @@ -629,19 +702,14 @@ SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, // build constraints. The address of any non-symbolic region is guaranteed // to be non-NULL. if (rInt->isZeroConstant()) { - switch (op) { - default: - break; - case BO_Sub: + if (op == BO_Sub) return evalCastFromLoc(lhs, resultTy); - case BO_EQ: - case BO_LT: - case BO_LE: - return makeTruthVal(false, resultTy); - case BO_NE: - case BO_GT: - case BO_GE: - return makeTruthVal(true, resultTy); + + if (BinaryOperator::isComparisonOp(op)) { + QualType boolType = getContext().BoolTy; + NonLoc l = evalCastFromLoc(lhs, boolType).castAs<NonLoc>(); + NonLoc r = makeTruthVal(false, boolType).castAs<NonLoc>(); + return evalBinOpNN(state, op, l, r, resultTy); } } @@ -699,14 +767,10 @@ SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, } } - // FIXME: If/when there is a getAsRawOffset() for FieldRegions, this - // ElementRegion path and the FieldRegion path below should be unified. - if (const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR)) { - // First see if the right region is also an ElementRegion. - const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR); - if (!RightER) - return UnknownVal(); - + // Handle special cases for when both regions are element regions. + const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR); + const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR); + if (RightER && LeftER) { // Next, see if the two ERs have the same super-region and matching types. // FIXME: This should do something useful even if the types don't match, // though if both indexes are constant the RegionRawOffset path will @@ -738,17 +802,29 @@ SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, // evalBinOpNN expects the two indexes to already be the right type. return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy); } + } + + // Special handling of the FieldRegions, even with symbolic offsets. + const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR); + const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR); + if (RightFR && LeftFR) { + SVal R = evalBinOpFieldRegionFieldRegion(LeftFR, RightFR, op, resultTy, + *this); + if (!R.isUnknown()) + return R; + } - // If the element indexes aren't comparable, see if the raw offsets are. - RegionRawOffset LeftOffset = LeftER->getAsArrayOffset(); - RegionRawOffset RightOffset = RightER->getAsArrayOffset(); + // Compare the regions using the raw offsets. + RegionOffset LeftOffset = LeftMR->getAsOffset(); + RegionOffset RightOffset = RightMR->getAsOffset(); - if (LeftOffset.getRegion() != NULL && - LeftOffset.getRegion() == RightOffset.getRegion()) { - CharUnits left = LeftOffset.getOffset(); - CharUnits right = RightOffset.getOffset(); + if (LeftOffset.getRegion() != NULL && + LeftOffset.getRegion() == RightOffset.getRegion() && + !LeftOffset.hasSymbolicOffset() && !RightOffset.hasSymbolicOffset()) { + int64_t left = LeftOffset.getOffset(); + int64_t right = RightOffset.getOffset(); - switch (op) { + switch (op) { default: return UnknownVal(); case BO_LT: @@ -763,60 +839,7 @@ SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, return makeTruthVal(left == right, resultTy); case BO_NE: return makeTruthVal(left != right, resultTy); - } } - - // If we get here, we have no way of comparing the ElementRegions. - } - - // See if both regions are fields of the same structure. - // FIXME: This doesn't handle nesting, inheritance, or Objective-C ivars. - if (const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR)) { - // Only comparisons are meaningful here! - if (!BinaryOperator::isComparisonOp(op)) - return UnknownVal(); - - // First see if the right region is also a FieldRegion. - const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR); - if (!RightFR) - return UnknownVal(); - - // Next, see if the two FRs have the same super-region. - // FIXME: This doesn't handle casts yet, and simply stripping the casts - // doesn't help. - if (LeftFR->getSuperRegion() != RightFR->getSuperRegion()) - return UnknownVal(); - - const FieldDecl *LeftFD = LeftFR->getDecl(); - const FieldDecl *RightFD = RightFR->getDecl(); - const RecordDecl *RD = LeftFD->getParent(); - - // Make sure the two FRs are from the same kind of record. Just in case! - // FIXME: This is probably where inheritance would be a problem. - if (RD != RightFD->getParent()) - return UnknownVal(); - - // We know for sure that the two fields are not the same, since that - // would have given us the same SVal. - if (op == BO_EQ) - return makeTruthVal(false, resultTy); - if (op == BO_NE) - return makeTruthVal(true, resultTy); - - // Iterate through the fields and see which one comes first. - // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field - // members and the units in which bit-fields reside have addresses that - // increase in the order in which they are declared." - bool leftFirst = (op == BO_LT || op == BO_LE); - for (RecordDecl::field_iterator I = RD->field_begin(), - E = RD->field_end(); I!=E; ++I) { - if (*I == LeftFD) - return makeTruthVal(leftFirst, resultTy); - if (*I == RightFD) - return makeTruthVal(!leftFirst, resultTy); - } - - llvm_unreachable("Fields not found in parent record's definition"); } // At this point we're not going to get a good answer, but we can try @@ -835,32 +858,13 @@ SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op, Loc lhs, NonLoc rhs, QualType resultTy) { - + assert(!BinaryOperator::isComparisonOp(op) && + "arguments to comparison ops must be of the same type"); + // Special case: rhs is a zero constant. if (rhs.isZeroConstant()) return lhs; - // Special case: 'rhs' is an integer that has the same width as a pointer and - // we are using the integer location in a comparison. Normally this cannot be - // triggered, but transfer functions like those for OSCompareAndSwapBarrier32 - // can generate comparisons that trigger this code. - // FIXME: Are all locations guaranteed to have pointer width? - if (BinaryOperator::isComparisonOp(op)) { - if (Optional<nonloc::ConcreteInt> rhsInt = - rhs.getAs<nonloc::ConcreteInt>()) { - const llvm::APSInt *x = &rhsInt->getValue(); - ASTContext &ctx = Context; - if (ctx.getTypeSize(ctx.VoidPtrTy) == x->getBitWidth()) { - // Convert the signedness of the integer (if necessary). - if (x->isSigned()) - x = &getBasicValueFactory().getValue(*x, true); - - return evalBinOpLL(state, op, lhs, loc::ConcreteInt(*x), resultTy); - } - } - return UnknownVal(); - } - // We are dealing with pointer arithmetic. // Handle pointer arithmetic on constant values. diff --git a/lib/StaticAnalyzer/Core/Store.cpp b/lib/StaticAnalyzer/Core/Store.cpp index 690ed08..0beb9db 100644 --- a/lib/StaticAnalyzer/Core/Store.cpp +++ b/lib/StaticAnalyzer/Core/Store.cpp @@ -325,7 +325,10 @@ SVal StoreManager::evalDynamicCast(SVal Base, QualType TargetType, if (MRClass == TargetClass) return loc::MemRegionVal(MR); - if (!TargetType->isVoidType()) { + // We skip over incomplete types. They must be the result of an earlier + // reinterpret_cast, as one can only dynamic_cast between types in the same + // class hierarchy. + if (!TargetType->isVoidType() && MRClass->hasDefinition()) { // Static upcasts are marked as DerivedToBase casts by Sema, so this will // only happen when multiple or virtual inheritance is involved. CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/true, diff --git a/lib/StaticAnalyzer/Core/SymbolManager.cpp b/lib/StaticAnalyzer/Core/SymbolManager.cpp index 7c75b6c..1b56f82 100644 --- a/lib/StaticAnalyzer/Core/SymbolManager.cpp +++ b/lib/StaticAnalyzer/Core/SymbolManager.cpp @@ -112,8 +112,7 @@ SymbolRef SymExpr::symbol_iterator::operator*() { } void SymExpr::symbol_iterator::expand() { - const SymExpr *SE = itr.back(); - itr.pop_back(); + const SymExpr *SE = itr.pop_back_val(); switch (SE->getKind()) { case SymExpr::RegionValueKind: @@ -436,6 +435,9 @@ bool SymbolReaper::isLiveRegion(const MemRegion *MR) { if (isa<MemSpaceRegion>(MR)) return true; + if (isa<CodeTextRegion>(MR)) + return true; + return false; } diff --git a/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp b/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp deleted file mode 100644 index d5706d6..0000000 --- a/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp +++ /dev/null @@ -1,72 +0,0 @@ -//===--- TextPathDiagnostics.cpp - Text Diagnostics for Paths ---*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines the TextPathDiagnostics object. -// -//===----------------------------------------------------------------------===// - -#include "clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h" -#include "clang/Lex/Preprocessor.h" -#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" -#include "llvm/Support/raw_ostream.h" -using namespace clang; -using namespace ento; -using namespace llvm; - -namespace { - -/// \brief Simple path diagnostic client used for outputting as diagnostic notes -/// the sequence of events. -class TextPathDiagnostics : public PathDiagnosticConsumer { - const std::string OutputFile; - DiagnosticsEngine &Diag; - -public: - TextPathDiagnostics(const std::string& output, DiagnosticsEngine &diag) - : OutputFile(output), Diag(diag) {} - - void FlushDiagnosticsImpl(std::vector<const PathDiagnostic *> &Diags, - FilesMade *filesMade); - - virtual StringRef getName() const { - return "TextPathDiagnostics"; - } - - PathGenerationScheme getGenerationScheme() const { return Minimal; } - bool supportsLogicalOpControlFlow() const { return true; } - bool supportsAllBlockEdges() const { return true; } - virtual bool supportsCrossFileDiagnostics() const { return true; } -}; - -} // end anonymous namespace - -void ento::createTextPathDiagnosticConsumer(AnalyzerOptions &AnalyzerOpts, - PathDiagnosticConsumers &C, - const std::string& out, - const Preprocessor &PP) { - C.push_back(new TextPathDiagnostics(out, PP.getDiagnostics())); -} - -void TextPathDiagnostics::FlushDiagnosticsImpl( - std::vector<const PathDiagnostic *> &Diags, - FilesMade *) { - for (std::vector<const PathDiagnostic *>::iterator it = Diags.begin(), - et = Diags.end(); it != et; ++it) { - const PathDiagnostic *D = *it; - - PathPieces FlatPath = D->path.flatten(/*ShouldFlattenMacros=*/true); - for (PathPieces::const_iterator I = FlatPath.begin(), E = FlatPath.end(); - I != E; ++I) { - unsigned diagID = - Diag.getDiagnosticIDs()->getCustomDiagID(DiagnosticIDs::Note, - (*I)->getString()); - Diag.Report((*I)->getLocation().asLocation(), diagID); - } - } -} |
