diff options
Diffstat (limited to 'lib/StaticAnalyzer/Core')
26 files changed, 1058 insertions, 300 deletions
diff --git a/lib/StaticAnalyzer/Core/AnalysisManager.cpp b/lib/StaticAnalyzer/Core/AnalysisManager.cpp index 83e67662e614..1cc08f0d9fe7 100644 --- a/lib/StaticAnalyzer/Core/AnalysisManager.cpp +++ b/lib/StaticAnalyzer/Core/AnalysisManager.cpp @@ -14,30 +14,25 @@ using namespace ento; void AnalysisManager::anchor() { } -AnalysisManager::AnalysisManager(ASTContext &ctx, DiagnosticsEngine &diags, - const LangOptions &lang, - const PathDiagnosticConsumers &PDC, - StoreManagerCreator storemgr, - ConstraintManagerCreator constraintmgr, - CheckerManager *checkerMgr, - AnalyzerOptions &Options, - CodeInjector *injector) - : AnaCtxMgr(Options.UnoptimizedCFG, - Options.includeImplicitDtorsInCFG(), - /*AddInitializers=*/true, - Options.includeTemporaryDtorsInCFG(), - Options.includeLifetimeInCFG(), - Options.shouldSynthesizeBodies(), - Options.shouldConditionalizeStaticInitializers(), - /*addCXXNewAllocator=*/true, - injector), - Ctx(ctx), - Diags(diags), - LangOpts(lang), - PathConsumers(PDC), - CreateStoreMgr(storemgr), CreateConstraintMgr(constraintmgr), - CheckerMgr(checkerMgr), - options(Options) { +AnalysisManager::AnalysisManager( + ASTContext &ASTCtx, DiagnosticsEngine &diags, const LangOptions &lang, + const PathDiagnosticConsumers &PDC, StoreManagerCreator storemgr, + ConstraintManagerCreator constraintmgr, CheckerManager *checkerMgr, + AnalyzerOptions &Options, CodeInjector *injector) + : AnaCtxMgr(ASTCtx, Options.UnoptimizedCFG, + Options.includeImplicitDtorsInCFG(), + /*AddInitializers=*/true, Options.includeTemporaryDtorsInCFG(), + Options.includeLifetimeInCFG(), + // Adding LoopExit elements to the CFG is a requirement for loop + // unrolling. + Options.includeLoopExitInCFG() || Options.shouldUnrollLoops(), + Options.shouldSynthesizeBodies(), + Options.shouldConditionalizeStaticInitializers(), + /*addCXXNewAllocator=*/true, + injector), + Ctx(ASTCtx), Diags(diags), LangOpts(lang), PathConsumers(PDC), + CreateStoreMgr(storemgr), CreateConstraintMgr(constraintmgr), + CheckerMgr(checkerMgr), options(Options) { AnaCtxMgr.getCFGBuildOptions().setAllAlwaysAdd(); } diff --git a/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp b/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp index 6f48fcb9e20c..48e3e22af04a 100644 --- a/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp +++ b/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp @@ -183,6 +183,11 @@ bool AnalyzerOptions::includeLifetimeInCFG() { /* Default = */ false); } +bool AnalyzerOptions::includeLoopExitInCFG() { + return getBooleanOption(IncludeLoopExitInCFG, "cfg-loopexit", + /* Default = */ false); +} + bool AnalyzerOptions::mayInlineCXXStandardLibrary() { return getBooleanOption(InlineCXXStandardLibrary, "c++-stdlib-inlining", @@ -375,6 +380,12 @@ bool AnalyzerOptions::shouldWidenLoops() { return WidenLoops.getValue(); } +bool AnalyzerOptions::shouldUnrollLoops() { + if (!UnrollLoops.hasValue()) + UnrollLoops = getBooleanOption("unroll-loops", /*Default=*/false); + return UnrollLoops.getValue(); +} + bool AnalyzerOptions::shouldDisplayNotesAsEvents() { if (!DisplayNotesAsEvents.hasValue()) DisplayNotesAsEvents = diff --git a/lib/StaticAnalyzer/Core/BasicValueFactory.cpp b/lib/StaticAnalyzer/Core/BasicValueFactory.cpp index ebbace4e33b3..ec7a7e9e4b1c 100644 --- a/lib/StaticAnalyzer/Core/BasicValueFactory.cpp +++ b/lib/StaticAnalyzer/Core/BasicValueFactory.cpp @@ -225,6 +225,8 @@ BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op, // test these conditions symbolically. // FIXME: Expand these checks to include all undefined behavior. + if (V1.isSigned() && V1.isNegative()) + return nullptr; if (V2.isSigned() && V2.isNegative()) return nullptr; diff --git a/lib/StaticAnalyzer/Core/BugReporter.cpp b/lib/StaticAnalyzer/Core/BugReporter.cpp index d8fca00681b4..4a5d25fc5634 100644 --- a/lib/StaticAnalyzer/Core/BugReporter.cpp +++ b/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -3310,6 +3310,78 @@ static const CFGBlock *findBlockForNode(const ExplodedNode *N) { return nullptr; } +// Returns true if by simply looking at the block, we can be sure that it +// results in a sink during analysis. This is useful to know when the analysis +// was interrupted, and we try to figure out if it would sink eventually. +// There may be many more reasons why a sink would appear during analysis +// (eg. checkers may generate sinks arbitrarily), but here we only consider +// sinks that would be obvious by looking at the CFG. +static bool isImmediateSinkBlock(const CFGBlock *Blk) { + if (Blk->hasNoReturnElement()) + return true; + + // FIXME: Throw-expressions are currently generating sinks during analysis: + // they're not supported yet, and also often used for actually terminating + // the program. So we should treat them as sinks in this analysis as well, + // at least for now, but once we have better support for exceptions, + // we'd need to carefully handle the case when the throw is being + // immediately caught. + if (std::any_of(Blk->begin(), Blk->end(), [](const CFGElement &Elm) { + if (Optional<CFGStmt> StmtElm = Elm.getAs<CFGStmt>()) + if (isa<CXXThrowExpr>(StmtElm->getStmt())) + return true; + return false; + })) + return true; + + return false; +} + +// Returns true if by looking at the CFG surrounding the node's program +// point, we can be sure that any analysis starting from this point would +// eventually end with a sink. We scan the child CFG blocks in a depth-first +// manner and see if all paths eventually end up in an immediate sink block. +static bool isInevitablySinking(const ExplodedNode *N) { + const CFG &Cfg = N->getCFG(); + + const CFGBlock *StartBlk = findBlockForNode(N); + if (!StartBlk) + return false; + if (isImmediateSinkBlock(StartBlk)) + return true; + + llvm::SmallVector<const CFGBlock *, 32> DFSWorkList; + llvm::SmallPtrSet<const CFGBlock *, 32> Visited; + + DFSWorkList.push_back(StartBlk); + while (!DFSWorkList.empty()) { + const CFGBlock *Blk = DFSWorkList.back(); + DFSWorkList.pop_back(); + Visited.insert(Blk); + + for (const auto &Succ : Blk->succs()) { + if (const CFGBlock *SuccBlk = Succ.getReachableBlock()) { + if (SuccBlk == &Cfg.getExit()) { + // If at least one path reaches the CFG exit, it means that control is + // returned to the caller. For now, say that we are not sure what + // happens next. If necessary, this can be improved to analyze + // the parent StackFrameContext's call site in a similar manner. + return false; + } + + if (!isImmediateSinkBlock(SuccBlk) && !Visited.count(SuccBlk)) { + // If the block has reachable child blocks that aren't no-return, + // add them to the worklist. + DFSWorkList.push_back(SuccBlk); + } + } + } + } + + // Nothing reached the exit. It can only mean one thing: there's no return. + return true; +} + static BugReport * FindReportInEquivalenceClass(BugReportEquivClass& EQ, SmallVectorImpl<BugReport*> &bugReports) { @@ -3360,15 +3432,10 @@ FindReportInEquivalenceClass(BugReportEquivClass& EQ, // See if we are in a no-return CFG block. If so, treat this similarly // to being post-dominated by a sink. This works better when the analysis - // is incomplete and we have never reached a no-return function - // we're post-dominated by. - // This is not quite enough to handle the incomplete analysis case. - // We may be post-dominated in subsequent blocks, or even - // inter-procedurally. However, it is not clear if more complicated - // cases are generally worth suppressing. - if (const CFGBlock *B = findBlockForNode(errorNode)) - if (B->hasNoReturnElement()) - continue; + // is incomplete and we have never reached the no-return function call(s) + // that we'd inevitably bump into on this path. + if (isInevitablySinking(errorNode)) + continue; // At this point we know that 'N' is not a sink and it has at least one // successor. Use a DFS worklist to find a non-sink end-of-path node. diff --git a/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp b/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp index d00182a871c1..7304d789431e 100644 --- a/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp +++ b/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp @@ -11,7 +11,7 @@ // enhance the diagnostics reported for a bug. // //===----------------------------------------------------------------------===// -#include "clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitor.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h" #include "clang/AST/Expr.h" #include "clang/AST/ExprObjC.h" #include "clang/Analysis/CFGStmtMap.h" @@ -42,48 +42,80 @@ bool bugreporter::isDeclRefExprToReference(const Expr *E) { return false; } +/// Given that expression S represents a pointer that would be dereferenced, +/// try to find a sub-expression from which the pointer came from. +/// This is used for tracking down origins of a null or undefined value: +/// "this is null because that is null because that is null" etc. +/// We wipe away field and element offsets because they merely add offsets. +/// We also wipe away all casts except lvalue-to-rvalue casts, because the +/// latter represent an actual pointer dereference; however, we remove +/// the final lvalue-to-rvalue cast before returning from this function +/// because it demonstrates more clearly from where the pointer rvalue was +/// loaded. Examples: +/// x->y.z ==> x (lvalue) +/// foo()->y.z ==> foo() (rvalue) const Expr *bugreporter::getDerefExpr(const Stmt *S) { - // Pattern match for a few useful cases: - // a[0], p->f, *p const Expr *E = dyn_cast<Expr>(S); if (!E) return nullptr; - E = E->IgnoreParenCasts(); while (true) { - if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E)) { - assert(B->isAssignmentOp()); - E = B->getLHS()->IgnoreParenCasts(); - continue; - } - else if (const UnaryOperator *U = dyn_cast<UnaryOperator>(E)) { - if (U->getOpcode() == UO_Deref) - return U->getSubExpr()->IgnoreParenCasts(); - } - else if (const MemberExpr *ME = dyn_cast<MemberExpr>(E)) { - if (ME->isImplicitAccess()) { - return ME; - } else if (ME->isArrow() || isDeclRefExprToReference(ME->getBase())) { - return ME->getBase()->IgnoreParenCasts(); + if (const CastExpr *CE = dyn_cast<CastExpr>(E)) { + if (CE->getCastKind() == CK_LValueToRValue) { + // This cast represents the load we're looking for. + break; + } + E = CE->getSubExpr(); + } else if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E)) { + // Pointer arithmetic: '*(x + 2)' -> 'x') etc. + if (B->getType()->isPointerType()) { + if (B->getLHS()->getType()->isPointerType()) { + E = B->getLHS(); + } else if (B->getRHS()->getType()->isPointerType()) { + E = B->getRHS(); + } else { + break; + } } else { - // If we have a member expr with a dot, the base must have been - // dereferenced. - return getDerefExpr(ME->getBase()); + // Probably more arithmetic can be pattern-matched here, + // but for now give up. + break; + } + } else if (const UnaryOperator *U = dyn_cast<UnaryOperator>(E)) { + if (U->getOpcode() == UO_Deref || U->getOpcode() == UO_AddrOf || + (U->isIncrementDecrementOp() && U->getType()->isPointerType())) { + // Operators '*' and '&' don't actually mean anything. + // We look at casts instead. + E = U->getSubExpr(); + } else { + // Probably more arithmetic can be pattern-matched here, + // but for now give up. + break; } } - else if (const ObjCIvarRefExpr *IvarRef = dyn_cast<ObjCIvarRefExpr>(E)) { - return IvarRef->getBase()->IgnoreParenCasts(); - } - else if (const ArraySubscriptExpr *AE = dyn_cast<ArraySubscriptExpr>(E)) { - return getDerefExpr(AE->getBase()); - } - else if (isa<DeclRefExpr>(E)) { - return E; + // Pattern match for a few useful cases: a[0], p->f, *p etc. + else if (const MemberExpr *ME = dyn_cast<MemberExpr>(E)) { + E = ME->getBase(); + } else if (const ObjCIvarRefExpr *IvarRef = dyn_cast<ObjCIvarRefExpr>(E)) { + E = IvarRef->getBase(); + } else if (const ArraySubscriptExpr *AE = dyn_cast<ArraySubscriptExpr>(E)) { + E = AE->getBase(); + } else if (const ParenExpr *PE = dyn_cast<ParenExpr>(E)) { + E = PE->getSubExpr(); + } else { + // Other arbitrary stuff. + break; } - break; } - return nullptr; + // Special case: remove the final lvalue-to-rvalue cast, but do not recurse + // deeper into the sub-expression. This way we return the lvalue from which + // our pointer rvalue was loaded. + if (const ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(E)) + if (CE->getCastKind() == CK_LValueToRValue) + E = CE->getSubExpr(); + + return E; } const Stmt *bugreporter::GetDenomExpr(const ExplodedNode *N) { @@ -1509,7 +1541,7 @@ ConditionBRVisitor::VisitTrueTest(const Expr *Cond, const BinaryOperator *BExpr, // For non-assignment operations, we require that we can understand // both the LHS and RHS. if (LhsString.empty() || RhsString.empty() || - !BinaryOperator::isComparisonOp(Op)) + !BinaryOperator::isComparisonOp(Op) || Op == BO_Cmp) return nullptr; // Should we invert the strings if the LHS is not a variable name? diff --git a/lib/StaticAnalyzer/Core/CMakeLists.txt b/lib/StaticAnalyzer/Core/CMakeLists.txt index 85878f5e96ee..5ac4f942f373 100644 --- a/lib/StaticAnalyzer/Core/CMakeLists.txt +++ b/lib/StaticAnalyzer/Core/CMakeLists.txt @@ -35,6 +35,7 @@ add_clang_library(clangStaticAnalyzerCore ExprEngineObjC.cpp FunctionSummary.cpp HTMLDiagnostics.cpp + LoopUnrolling.cpp LoopWidening.cpp MemRegion.cpp PathDiagnostic.cpp @@ -54,6 +55,7 @@ add_clang_library(clangStaticAnalyzerCore LINK_LIBS clangAST + clangASTMatchers clangAnalysis clangBasic clangLex diff --git a/lib/StaticAnalyzer/Core/CallEvent.cpp b/lib/StaticAnalyzer/Core/CallEvent.cpp index 1858bfd89637..776369be9dba 100644 --- a/lib/StaticAnalyzer/Core/CallEvent.cpp +++ b/lib/StaticAnalyzer/Core/CallEvent.cpp @@ -21,6 +21,9 @@ #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Support/Debug.h" + +#define DEBUG_TYPE "static-analyzer-call-event" using namespace clang; using namespace ento; @@ -97,9 +100,6 @@ bool CallEvent::hasNonNullArgumentsWithType(bool (*Condition)(QualType)) const { for (CallEvent::param_type_iterator I = param_type_begin(), E = param_type_end(); I != E && Idx < NumOfArgs; ++I, ++Idx) { - if (NumOfArgs <= Idx) - break; - // If the parameter is 0, it's harmless. if (getArgSVal(Idx).isZeroConstant()) continue; @@ -211,7 +211,9 @@ ProgramPoint CallEvent::getProgramPoint(bool IsPreVisit, } bool CallEvent::isCalled(const CallDescription &CD) const { - assert(getKind() != CE_ObjCMessage && "Obj-C methods are not supported"); + // FIXME: Add ObjC Message support. + if (getKind() == CE_ObjCMessage) + return false; if (!CD.IsLookupDone) { CD.IsLookupDone = true; CD.II = &getState()->getStateManager().getContext().Idents.get(CD.FuncName); @@ -346,6 +348,30 @@ ArrayRef<ParmVarDecl*> AnyFunctionCall::parameters() const { return D->parameters(); } +RuntimeDefinition AnyFunctionCall::getRuntimeDefinition() const { + const FunctionDecl *FD = getDecl(); + // Note that the AnalysisDeclContext will have the FunctionDecl with + // the definition (if one exists). + if (FD) { + AnalysisDeclContext *AD = + getLocationContext()->getAnalysisDeclContext()-> + getManager()->getContext(FD); + bool IsAutosynthesized; + Stmt* Body = AD->getBody(IsAutosynthesized); + DEBUG({ + if (IsAutosynthesized) + llvm::dbgs() << "Using autosynthesized body for " << FD->getName() + << "\n"; + }); + if (Body) { + const Decl* Decl = AD->getDecl(); + return RuntimeDefinition(Decl); + } + } + + return RuntimeDefinition(); +} + void AnyFunctionCall::getInitialStackFrameContents( const StackFrameContext *CalleeCtx, BindingsTy &Bindings) const { diff --git a/lib/StaticAnalyzer/Core/CheckerContext.cpp b/lib/StaticAnalyzer/Core/CheckerContext.cpp index 548b06ef91fc..61cbf3854bb2 100644 --- a/lib/StaticAnalyzer/Core/CheckerContext.cpp +++ b/lib/StaticAnalyzer/Core/CheckerContext.cpp @@ -99,3 +99,35 @@ StringRef CheckerContext::getMacroNameOrSpelling(SourceLocation &Loc) { return Lexer::getSpelling(Loc, buf, getSourceManager(), getLangOpts()); } +/// Evaluate comparison and return true if it's known that condition is true +static bool evalComparison(SVal LHSVal, BinaryOperatorKind ComparisonOp, + SVal RHSVal, ProgramStateRef State) { + if (LHSVal.isUnknownOrUndef()) + return false; + ProgramStateManager &Mgr = State->getStateManager(); + if (!LHSVal.getAs<NonLoc>()) { + LHSVal = Mgr.getStoreManager().getBinding(State->getStore(), + LHSVal.castAs<Loc>()); + if (LHSVal.isUnknownOrUndef() || !LHSVal.getAs<NonLoc>()) + return false; + } + + SValBuilder &Bldr = Mgr.getSValBuilder(); + SVal Eval = Bldr.evalBinOp(State, ComparisonOp, LHSVal, RHSVal, + Bldr.getConditionType()); + if (Eval.isUnknownOrUndef()) + return false; + ProgramStateRef StTrue, StFalse; + std::tie(StTrue, StFalse) = State->assume(Eval.castAs<DefinedSVal>()); + return StTrue && !StFalse; +} + +bool CheckerContext::isGreaterOrEqual(const Expr *E, unsigned long long Val) { + DefinedSVal V = getSValBuilder().makeIntVal(Val, getASTContext().LongLongTy); + return evalComparison(getSVal(E), BO_GE, V, getState()); +} + +bool CheckerContext::isNegative(const Expr *E) { + DefinedSVal V = getSValBuilder().makeIntVal(0, false); + return evalComparison(getSVal(E), BO_LT, V, getState()); +} diff --git a/lib/StaticAnalyzer/Core/CoreEngine.cpp b/lib/StaticAnalyzer/Core/CoreEngine.cpp index 4e2866c56f0e..e2e9ddf5048e 100644 --- a/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -274,7 +274,8 @@ void CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc, assert(Loc.getAs<PostStmt>() || Loc.getAs<PostInitializer>() || Loc.getAs<PostImplicitCall>() || - Loc.getAs<CallExitEnd>()); + Loc.getAs<CallExitEnd>() || + Loc.getAs<LoopExit>()); HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred); break; } @@ -566,7 +567,8 @@ void CoreEngine::enqueueStmtNode(ExplodedNode *N, // Do not create extra nodes. Move to the next CFG element. if (N->getLocation().getAs<PostInitializer>() || - N->getLocation().getAs<PostImplicitCall>()) { + N->getLocation().getAs<PostImplicitCall>()|| + N->getLocation().getAs<LoopExit>()) { WList->enqueue(N, Block, Idx+1); return; } diff --git a/lib/StaticAnalyzer/Core/Environment.cpp b/lib/StaticAnalyzer/Core/Environment.cpp index e2cb52cb417e..c6acb9d1851c 100644 --- a/lib/StaticAnalyzer/Core/Environment.cpp +++ b/lib/StaticAnalyzer/Core/Environment.cpp @@ -13,7 +13,7 @@ #include "clang/AST/ExprCXX.h" #include "clang/AST/ExprObjC.h" -#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "llvm/Support/raw_ostream.h" diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp index eee5400fe177..3be37e7ae301 100644 --- a/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -17,6 +17,7 @@ #include "PrettyStackTraceLocationContext.h" #include "clang/AST/CharUnits.h" #include "clang/AST/ParentMap.h" +#include "clang/Analysis/CFGStmtMap.h" #include "clang/AST/StmtCXX.h" #include "clang/AST/StmtObjC.h" #include "clang/Basic/Builtins.h" @@ -27,6 +28,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/SaveAndRestore.h" #include "llvm/Support/raw_ostream.h" @@ -362,6 +364,9 @@ void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, case CFGElement::TemporaryDtor: ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred); return; + case CFGElement::LoopExit: + ProcessLoopExit(E.castAs<CFGLoopExit>().getLoopStmt(), Pred); + return; case CFGElement::LifetimeEnds: return; } @@ -507,6 +512,24 @@ void ExprEngine::ProcessStmt(const CFGStmt S, Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); } +void ExprEngine::ProcessLoopExit(const Stmt* S, ExplodedNode *Pred) { + PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), + S->getLocStart(), + "Error evaluating end of the loop"); + ExplodedNodeSet Dst; + Dst.Add(Pred); + NodeBuilder Bldr(Pred, Dst, *currBldrCtx); + ProgramStateRef NewState = Pred->getState(); + + if(AMgr.options.shouldUnrollLoops()) + NewState = processLoopEnd(S, NewState); + + LoopExit PP(S, Pred->getLocationContext()); + Bldr.generateNode(PP, NewState, Pred); + // Enqueue the new nodes onto the work list. + Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); +} + void ExprEngine::ProcessInitializer(const CFGInitializer Init, ExplodedNode *Pred) { const CXXCtorInitializer *BMI = Init.getInitializer(); @@ -804,6 +827,21 @@ void ExprEngine::VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE, } } +namespace { +class CollectReachableSymbolsCallback final : public SymbolVisitor { + InvalidatedSymbols Symbols; + +public: + explicit CollectReachableSymbolsCallback(ProgramStateRef State) {} + const InvalidatedSymbols &getSymbols() const { return Symbols; } + + bool VisitSymbol(SymbolRef Sym) override { + Symbols.insert(Sym); + return true; + } +}; +} // end anonymous namespace + void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, ExplodedNodeSet &DstTop) { PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), @@ -1080,8 +1118,29 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, SVal result = svalBuilder.conjureSymbolVal(nullptr, Ex, LCtx, resultType, currBldrCtx->blockCount()); - ProgramStateRef state = N->getState()->BindExpr(Ex, LCtx, result); - Bldr2.generateNode(S, N, state); + ProgramStateRef State = N->getState()->BindExpr(Ex, LCtx, result); + + // Escape pointers passed into the list, unless it's an ObjC boxed + // expression which is not a boxable C structure. + if (!(isa<ObjCBoxedExpr>(Ex) && + !cast<ObjCBoxedExpr>(Ex)->getSubExpr() + ->getType()->isRecordType())) + for (auto Child : Ex->children()) { + assert(Child); + + SVal Val = State->getSVal(Child, LCtx); + + CollectReachableSymbolsCallback Scanner = + State->scanReachableSymbols<CollectReachableSymbolsCallback>( + Val); + const InvalidatedSymbols &EscapedSymbols = Scanner.getSymbols(); + + State = getCheckerManager().runCheckersForPointerEscape( + State, EscapedSymbols, + /*CallEvent*/ nullptr, PSK_EscapeOther, nullptr); + } + + Bldr2.generateNode(S, N, State); } getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this); @@ -1091,7 +1150,7 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, case Stmt::ArraySubscriptExprClass: Bldr.takeNodes(Pred); - VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst); + VisitArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst); Bldr.addNodes(Dst); break; @@ -1497,6 +1556,25 @@ void ExprEngine::processCFGBlockEntrance(const BlockEdge &L, NodeBuilderWithSinks &nodeBuilder, ExplodedNode *Pred) { PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext()); + // If we reach a loop which has a known bound (and meets + // other constraints) then consider completely unrolling it. + if(AMgr.options.shouldUnrollLoops()) { + unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath; + const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator(); + if (Term) { + ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(), + Pred, maxBlockVisitOnPath); + if (NewState != Pred->getState()) { + ExplodedNode *UpdatedNode = nodeBuilder.generateNode(NewState, Pred); + if (!UpdatedNode) + return; + Pred = UpdatedNode; + } + } + // Is we are inside an unrolled loop then no need the check the counters. + if(isUnrolledState(Pred->getState())) + return; + } // If this block is terminated by a loop and it has already been visited the // maximum number of times, widen the loop. @@ -2030,10 +2108,12 @@ void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, ProgramPoint::PostLValueKind); return; } - if (isa<FieldDecl>(D)) { + if (isa<FieldDecl>(D) || isa<IndirectFieldDecl>(D)) { // FIXME: Compute lvalue of field pointers-to-member. // Right now we just use a non-null void pointer, so that it gives proper // results in boolean contexts. + // FIXME: Maybe delegate this to the surrounding operator&. + // Note how this expression is lvalue, however pointer-to-member is NonLoc. SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy, currBldrCtx->blockCount()); state = state->assume(V.castAs<DefinedOrUnknownSVal>(), true); @@ -2046,10 +2126,9 @@ void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, } /// VisitArraySubscriptExpr - Transfer function for array accesses -void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A, +void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A, ExplodedNode *Pred, ExplodedNodeSet &Dst){ - const Expr *Base = A->getBase()->IgnoreParens(); const Expr *Idx = A->getIdx()->IgnoreParens(); @@ -2058,18 +2137,32 @@ void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A, ExplodedNodeSet EvalSet; StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx); - assert(A->isGLValue() || - (!AMgr.getLangOpts().CPlusPlus && - A->getType().isCForbiddenLValueType())); + + bool IsVectorType = A->getBase()->getType()->isVectorType(); + + // The "like" case is for situations where C standard prohibits the type to + // be an lvalue, e.g. taking the address of a subscript of an expression of + // type "void *". + bool IsGLValueLike = A->isGLValue() || + (A->getType().isCForbiddenLValueType() && !AMgr.getLangOpts().CPlusPlus); for (auto *Node : CheckerPreStmt) { const LocationContext *LCtx = Node->getLocationContext(); ProgramStateRef state = Node->getState(); - SVal V = state->getLValue(A->getType(), - state->getSVal(Idx, LCtx), - state->getSVal(Base, LCtx)); - Bldr.generateNode(A, Node, state->BindExpr(A, LCtx, V), nullptr, - ProgramPoint::PostLValueKind); + + if (IsGLValueLike) { + SVal V = state->getLValue(A->getType(), + state->getSVal(Idx, LCtx), + state->getSVal(Base, LCtx)); + Bldr.generateNode(A, Node, state->BindExpr(A, LCtx, V), nullptr, + ProgramPoint::PostLValueKind); + } else if (IsVectorType) { + // FIXME: non-glvalue vector reads are not modelled. + Bldr.generateNode(A, Node, state, nullptr); + } else { + llvm_unreachable("Array subscript should be an lValue when not \ +a vector and not a forbidden lvalue type"); + } } getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, A, *this); @@ -2195,21 +2288,6 @@ void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred, getCheckerManager().runCheckersForPostStmt(Dst, AfterInvalidateSet, AE, *this); } -namespace { -class CollectReachableSymbolsCallback final : public SymbolVisitor { - InvalidatedSymbols Symbols; - -public: - CollectReachableSymbolsCallback(ProgramStateRef State) {} - const InvalidatedSymbols &getSymbols() const { return Symbols; } - - bool VisitSymbol(SymbolRef Sym) override { - Symbols.insert(Sym); - return true; - } -}; -} // end anonymous namespace - // A value escapes in three possible cases: // (1) We are binding to something that is not a memory region. // (2) We are binding to a MemrRegion that does not have stack storage. @@ -2666,6 +2744,12 @@ struct DOTGraphTraits<ExplodedNode*> : Out << "Epsilon Point"; break; + case ProgramPoint::LoopExitKind: { + LoopExit LE = Loc.castAs<LoopExit>(); + Out << "LoopExit: " << LE.getLoopStmt()->getStmtClassName(); + break; + } + case ProgramPoint::PreImplicitCallKind: { ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>(); Out << "PreCall: "; diff --git a/lib/StaticAnalyzer/Core/ExprEngineC.cpp b/lib/StaticAnalyzer/Core/ExprEngineC.cpp index 6f1e8391e67c..3e7a50365f50 100644 --- a/lib/StaticAnalyzer/Core/ExprEngineC.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngineC.cpp @@ -20,6 +20,24 @@ using namespace clang; using namespace ento; using llvm::APSInt; +/// \brief Optionally conjure and return a symbol for offset when processing +/// an expression \p Expression. +/// If \p Other is a location, conjure a symbol for \p Symbol +/// (offset) if it is unknown so that memory arithmetic always +/// results in an ElementRegion. +/// \p Count The number of times the current basic block was visited. +static SVal conjureOffsetSymbolOnLocation( + SVal Symbol, SVal Other, Expr* Expression, SValBuilder &svalBuilder, + unsigned Count, const LocationContext *LCtx) { + QualType Ty = Expression->getType(); + if (Other.getAs<Loc>() && + Ty->isIntegralOrEnumerationType() && + Symbol.isUnknown()) { + return svalBuilder.conjureSymbolVal(Expression, LCtx, Ty, Count); + } + return Symbol; +} + void ExprEngine::VisitBinaryOperator(const BinaryOperator* B, ExplodedNode *Pred, ExplodedNodeSet &Dst) { @@ -63,24 +81,13 @@ void ExprEngine::VisitBinaryOperator(const BinaryOperator* B, StmtNodeBuilder Bldr(*it, Tmp2, *currBldrCtx); if (B->isAdditiveOp()) { - // If one of the operands is a location, conjure a symbol for the other - // one (offset) if it's unknown so that memory arithmetic always - // results in an ElementRegion. // TODO: This can be removed after we enable history tracking with // SymSymExpr. unsigned Count = currBldrCtx->blockCount(); - if (LeftV.getAs<Loc>() && - RHS->getType()->isIntegralOrEnumerationType() && - RightV.isUnknown()) { - RightV = svalBuilder.conjureSymbolVal(RHS, LCtx, RHS->getType(), - Count); - } - if (RightV.getAs<Loc>() && - LHS->getType()->isIntegralOrEnumerationType() && - LeftV.isUnknown()) { - LeftV = svalBuilder.conjureSymbolVal(LHS, LCtx, LHS->getType(), - Count); - } + RightV = conjureOffsetSymbolOnLocation( + RightV, LeftV, RHS, svalBuilder, Count, LCtx); + LeftV = conjureOffsetSymbolOnLocation( + LeftV, RightV, LHS, svalBuilder, Count, LCtx); } // Although we don't yet model pointers-to-members, we do need to make @@ -92,12 +99,10 @@ void ExprEngine::VisitBinaryOperator(const BinaryOperator* B, // Process non-assignments except commas or short-circuited // logical expressions (LAnd and LOr). SVal Result = evalBinOp(state, Op, LeftV, RightV, B->getType()); - if (Result.isUnknown()) { - Bldr.generateNode(B, *it, state); - continue; + if (!Result.isUnknown()) { + state = state->BindExpr(B, LCtx, Result); } - state = state->BindExpr(B, LCtx, Result); Bldr.generateNode(B, *it, state); continue; } @@ -530,7 +535,7 @@ void ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL, const Expr *Init = CL->getInitializer(); SVal V = State->getSVal(CL->getInitializer(), LCtx); - if (isa<CXXConstructExpr>(Init)) { + if (isa<CXXConstructExpr>(Init) || isa<CXXStdInitializerListExpr>(Init)) { // No work needed. Just pass the value up to this expression. } else { assert(isa<InitListExpr>(Init)); @@ -628,6 +633,16 @@ void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred, StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); ProgramStateRef state = Pred->getState(); + if (B->getType()->isVectorType()) { + // FIXME: We do not model vector arithmetic yet. When adding support for + // that, note that the CFG-based reasoning below does not apply, because + // logical operators on vectors are not short-circuit. Currently they are + // modeled as short-circuit in Clang CFG but this is incorrect. + // Do not set the value for the expression. It'd be UnknownVal by default. + Bldr.generateNode(B, Pred, state); + return; + } + ExplodedNode *N = Pred; while (!N->getLocation().getAs<BlockEntrance>()) { ProgramPoint P = N->getLocation(); @@ -1028,7 +1043,14 @@ void ExprEngine::VisitIncrementDecrementOperator(const UnaryOperator* U, // Propagate unknown and undefined values. if (V2_untested.isUnknownOrUndef()) { - Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, V2_untested)); + state = state->BindExpr(U, LCtx, V2_untested); + + // Perform the store, so that the uninitialized value detection happens. + Bldr.takeNodes(*I); + ExplodedNodeSet Dst3; + evalStore(Dst3, U, U, *I, state, loc, V2_untested); + Bldr.addNodes(Dst3); + continue; } DefinedSVal V2 = V2_untested.castAs<DefinedSVal>(); diff --git a/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp b/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp index f0f6dd2e43e7..9b820e81e374 100644 --- a/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp +++ b/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp @@ -44,8 +44,12 @@ class HTMLDiagnostics : public PathDiagnosticConsumer { bool createdDir, noDir; const Preprocessor &PP; AnalyzerOptions &AnalyzerOpts; + const bool SupportsCrossFileDiagnostics; public: - HTMLDiagnostics(AnalyzerOptions &AnalyzerOpts, const std::string& prefix, const Preprocessor &pp); + HTMLDiagnostics(AnalyzerOptions &AnalyzerOpts, + const std::string& prefix, + const Preprocessor &pp, + bool supportsMultipleFiles); ~HTMLDiagnostics() override { FlushDiagnostics(nullptr); } @@ -56,6 +60,10 @@ public: return "HTMLDiagnostics"; } + bool supportsCrossFileDiagnostics() const override { + return SupportsCrossFileDiagnostics; + } + unsigned ProcessMacroPiece(raw_ostream &os, const PathDiagnosticMacroPiece& P, unsigned num); @@ -69,21 +77,47 @@ public: void ReportDiag(const PathDiagnostic& D, FilesMade *filesMade); + + // Generate the full HTML report + std::string GenerateHTML(const PathDiagnostic& D, Rewriter &R, + const SourceManager& SMgr, const PathPieces& path, + const char *declName); + + // Add HTML header/footers to file specified by FID + void FinalizeHTML(const PathDiagnostic& D, Rewriter &R, + const SourceManager& SMgr, const PathPieces& path, + FileID FID, const FileEntry *Entry, const char *declName); + + // Rewrite the file specified by FID with HTML formatting. + void RewriteFile(Rewriter &R, const SourceManager& SMgr, + const PathPieces& path, FileID FID); }; } // end anonymous namespace HTMLDiagnostics::HTMLDiagnostics(AnalyzerOptions &AnalyzerOpts, const std::string& prefix, - const Preprocessor &pp) - : Directory(prefix), createdDir(false), noDir(false), PP(pp), AnalyzerOpts(AnalyzerOpts) { -} + const Preprocessor &pp, + bool supportsMultipleFiles) + : Directory(prefix), + createdDir(false), + noDir(false), + PP(pp), + AnalyzerOpts(AnalyzerOpts), + SupportsCrossFileDiagnostics(supportsMultipleFiles) {} void ento::createHTMLDiagnosticConsumer(AnalyzerOptions &AnalyzerOpts, PathDiagnosticConsumers &C, const std::string& prefix, const Preprocessor &PP) { - C.push_back(new HTMLDiagnostics(AnalyzerOpts, prefix, PP)); + C.push_back(new HTMLDiagnostics(AnalyzerOpts, prefix, PP, true)); +} + +void ento::createHTMLSingleFileDiagnosticConsumer(AnalyzerOptions &AnalyzerOpts, + PathDiagnosticConsumers &C, + const std::string& prefix, + const Preprocessor &PP) { + C.push_back(new HTMLDiagnostics(AnalyzerOpts, prefix, PP, false)); } //===----------------------------------------------------------------------===// @@ -121,24 +155,24 @@ void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D, // First flatten out the entire path to make it easier to use. PathPieces path = D.path.flatten(/*ShouldFlattenMacros=*/false); - // The path as already been prechecked that all parts of the path are - // from the same file and that it is non-empty. - const SourceManager &SMgr = path.front()->getLocation().getManager(); + // The path as already been prechecked that the path is non-empty. assert(!path.empty()); - FileID FID = - path.front()->getLocation().asLocation().getExpansionLoc().getFileID(); - assert(FID.isValid()); + const SourceManager &SMgr = path.front()->getLocation().getManager(); // Create a new rewriter to generate HTML. Rewriter R(const_cast<SourceManager&>(SMgr), PP.getLangOpts()); + // The file for the first path element is considered the main report file, it + // will usually be equivalent to SMgr.getMainFileID(); however, it might be a + // header when -analyzer-opt-analyze-headers is used. + FileID ReportFile = path.front()->getLocation().asLocation().getExpansionLoc().getFileID(); + // Get the function/method name SmallString<128> declName("unknown"); int offsetDecl = 0; if (const Decl *DeclWithIssue = D.getDeclWithIssue()) { - if (const NamedDecl *ND = dyn_cast<NamedDecl>(DeclWithIssue)) { + if (const NamedDecl *ND = dyn_cast<NamedDecl>(DeclWithIssue)) declName = ND->getDeclName().getAsString(); - } if (const Stmt *Body = DeclWithIssue->getBody()) { // Retrieve the relative position of the declaration which will be used @@ -151,49 +185,144 @@ void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D, } } - // Process the path. - // Maintain the counts of extra note pieces separately. - unsigned TotalPieces = path.size(); - unsigned TotalNotePieces = - std::count_if(path.begin(), path.end(), - [](const std::shared_ptr<PathDiagnosticPiece> &p) { - return isa<PathDiagnosticNotePiece>(*p); - }); + std::string report = GenerateHTML(D, R, SMgr, path, declName.c_str()); + if (report.empty()) { + llvm::errs() << "warning: no diagnostics generated for main file.\n"; + return; + } - unsigned TotalRegularPieces = TotalPieces - TotalNotePieces; - unsigned NumRegularPieces = TotalRegularPieces; - unsigned NumNotePieces = TotalNotePieces; + // Create a path for the target HTML file. + int FD; + SmallString<128> Model, ResultPath; - for (auto I = path.rbegin(), E = path.rend(); I != E; ++I) { - if (isa<PathDiagnosticNotePiece>(I->get())) { - // This adds diagnostic bubbles, but not navigation. - // Navigation through note pieces would be added later, - // as a separate pass through the piece list. - HandlePiece(R, FID, **I, NumNotePieces, TotalNotePieces); - --NumNotePieces; - } else { - HandlePiece(R, FID, **I, NumRegularPieces, TotalRegularPieces); - --NumRegularPieces; - } + if (!AnalyzerOpts.shouldWriteStableReportFilename()) { + llvm::sys::path::append(Model, Directory, "report-%%%%%%.html"); + if (std::error_code EC = + llvm::sys::fs::make_absolute(Model)) { + llvm::errs() << "warning: could not make '" << Model + << "' absolute: " << EC.message() << '\n'; + return; + } + if (std::error_code EC = + llvm::sys::fs::createUniqueFile(Model, FD, ResultPath)) { + llvm::errs() << "warning: could not create file in '" << Directory + << "': " << EC.message() << '\n'; + return; + } + + } else { + int i = 1; + std::error_code EC; + do { + // Find a filename which is not already used + const FileEntry* Entry = SMgr.getFileEntryForID(ReportFile); + std::stringstream filename; + Model = ""; + filename << "report-" + << llvm::sys::path::filename(Entry->getName()).str() + << "-" << declName.c_str() + << "-" << offsetDecl + << "-" << i << ".html"; + llvm::sys::path::append(Model, Directory, + filename.str()); + EC = llvm::sys::fs::openFileForWrite(Model, + FD, + llvm::sys::fs::F_RW | + llvm::sys::fs::F_Excl); + if (EC && EC != llvm::errc::file_exists) { + llvm::errs() << "warning: could not create file '" << Model + << "': " << EC.message() << '\n'; + return; + } + i++; + } while (EC); } - // Add line numbers, header, footer, etc. + llvm::raw_fd_ostream os(FD, true); - // unsigned FID = R.getSourceMgr().getMainFileID(); - html::EscapeText(R, FID); - html::AddLineNumbers(R, FID); + if (filesMade) + filesMade->addDiagnostic(D, getName(), + llvm::sys::path::filename(ResultPath)); - // If we have a preprocessor, relex the file and syntax highlight. - // We might not have a preprocessor if we come from a deserialized AST file, - // for example. + // Emit the HTML to disk. + os << report; +} - html::SyntaxHighlight(R, FID, PP); - html::HighlightMacros(R, FID, PP); +std::string HTMLDiagnostics::GenerateHTML(const PathDiagnostic& D, Rewriter &R, + const SourceManager& SMgr, const PathPieces& path, const char *declName) { + + // Rewrite source files as HTML for every new file the path crosses + std::vector<FileID> FileIDs; + for (auto I : path) { + FileID FID = I->getLocation().asLocation().getExpansionLoc().getFileID(); + if (std::find(FileIDs.begin(), FileIDs.end(), FID) != FileIDs.end()) + continue; + + FileIDs.push_back(FID); + RewriteFile(R, SMgr, path, FID); + } + + if (SupportsCrossFileDiagnostics && FileIDs.size() > 1) { + // Prefix file names, anchor tags, and nav cursors to every file + for (auto I = FileIDs.begin(), E = FileIDs.end(); I != E; I++) { + std::string s; + llvm::raw_string_ostream os(s); + + if (I != FileIDs.begin()) + os << "<hr class=divider>\n"; + + os << "<div id=File" << I->getHashValue() << ">\n"; - // Get the full directory name of the analyzed file. + // Left nav arrow + if (I != FileIDs.begin()) + os << "<div class=FileNav><a href=\"#File" << (I - 1)->getHashValue() + << "\">←</a></div>"; - const FileEntry* Entry = SMgr.getFileEntryForID(FID); + os << "<h4 class=FileName>" << SMgr.getFileEntryForID(*I)->getName() + << "</h4>\n"; + // Right nav arrow + if (I + 1 != E) + os << "<div class=FileNav><a href=\"#File" << (I + 1)->getHashValue() + << "\">→</a></div>"; + + os << "</div>\n"; + + R.InsertTextBefore(SMgr.getLocForStartOfFile(*I), os.str()); + } + + // Append files to the main report file in the order they appear in the path + for (auto I : llvm::make_range(FileIDs.begin() + 1, FileIDs.end())) { + std::string s; + llvm::raw_string_ostream os(s); + + const RewriteBuffer *Buf = R.getRewriteBufferFor(I); + for (auto BI : *Buf) + os << BI; + + R.InsertTextAfter(SMgr.getLocForEndOfFile(FileIDs[0]), os.str()); + } + } + + const RewriteBuffer *Buf = R.getRewriteBufferFor(FileIDs[0]); + if (!Buf) + return ""; + + // Add CSS, header, and footer. + const FileEntry* Entry = SMgr.getFileEntryForID(FileIDs[0]); + FinalizeHTML(D, R, SMgr, path, FileIDs[0], Entry, declName); + + std::string file; + llvm::raw_string_ostream os(file); + for (auto BI : *Buf) + os << BI; + + return os.str(); +} + +void HTMLDiagnostics::FinalizeHTML(const PathDiagnostic& D, Rewriter &R, + const SourceManager& SMgr, const PathPieces& path, FileID FID, + const FileEntry *Entry, const char *declName) { // This is a cludge; basically we want to append either the full // working directory if we have no directory information. This is // a work in progress. @@ -306,73 +435,48 @@ void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D, R.InsertTextBefore(SMgr.getLocForStartOfFile(FID), os.str()); } - // Add CSS, header, and footer. - html::AddHeaderFooterInternalBuiltinCSS(R, FID, Entry->getName()); +} - // Get the rewrite buffer. - const RewriteBuffer *Buf = R.getRewriteBufferFor(FID); - - if (!Buf) { - llvm::errs() << "warning: no diagnostics generated for main file.\n"; - return; - } - - // Create a path for the target HTML file. - int FD; - SmallString<128> Model, ResultPath; +void HTMLDiagnostics::RewriteFile(Rewriter &R, const SourceManager& SMgr, + const PathPieces& path, FileID FID) { + // Process the path. + // Maintain the counts of extra note pieces separately. + unsigned TotalPieces = path.size(); + unsigned TotalNotePieces = + std::count_if(path.begin(), path.end(), + [](const std::shared_ptr<PathDiagnosticPiece> &p) { + return isa<PathDiagnosticNotePiece>(*p); + }); - if (!AnalyzerOpts.shouldWriteStableReportFilename()) { - llvm::sys::path::append(Model, Directory, "report-%%%%%%.html"); - if (std::error_code EC = - llvm::sys::fs::make_absolute(Model)) { - llvm::errs() << "warning: could not make '" << Model - << "' absolute: " << EC.message() << '\n'; - return; - } - if (std::error_code EC = - llvm::sys::fs::createUniqueFile(Model, FD, ResultPath)) { - llvm::errs() << "warning: could not create file in '" << Directory - << "': " << EC.message() << '\n'; - return; - } + unsigned TotalRegularPieces = TotalPieces - TotalNotePieces; + unsigned NumRegularPieces = TotalRegularPieces; + unsigned NumNotePieces = TotalNotePieces; - } else { - int i = 1; - std::error_code EC; - do { - // Find a filename which is not already used - std::stringstream filename; - Model = ""; - filename << "report-" - << llvm::sys::path::filename(Entry->getName()).str() - << "-" << declName.c_str() - << "-" << offsetDecl - << "-" << i << ".html"; - llvm::sys::path::append(Model, Directory, - filename.str()); - EC = llvm::sys::fs::openFileForWrite(Model, - FD, - llvm::sys::fs::F_RW | - llvm::sys::fs::F_Excl); - if (EC && EC != llvm::errc::file_exists) { - llvm::errs() << "warning: could not create file '" << Model - << "': " << EC.message() << '\n'; - return; - } - i++; - } while (EC); + for (auto I = path.rbegin(), E = path.rend(); I != E; ++I) { + if (isa<PathDiagnosticNotePiece>(I->get())) { + // This adds diagnostic bubbles, but not navigation. + // Navigation through note pieces would be added later, + // as a separate pass through the piece list. + HandlePiece(R, FID, **I, NumNotePieces, TotalNotePieces); + --NumNotePieces; + } else { + HandlePiece(R, FID, **I, NumRegularPieces, TotalRegularPieces); + --NumRegularPieces; + } } - llvm::raw_fd_ostream os(FD, true); + // Add line numbers, header, footer, etc. - if (filesMade) - filesMade->addDiagnostic(D, getName(), - llvm::sys::path::filename(ResultPath)); + html::EscapeText(R, FID); + html::AddLineNumbers(R, FID); - // Emit the HTML to disk. - for (RewriteBuffer::iterator I = Buf->begin(), E = Buf->end(); I!=E; ++I) - os << *I; + // If we have a preprocessor, relex the file and syntax highlight. + // We might not have a preprocessor if we come from a deserialized AST file, + // for example. + + html::SyntaxHighlight(R, FID, PP); + html::HighlightMacros(R, FID, PP); } void HTMLDiagnostics::HandlePiece(Rewriter& R, FileID BugFileID, diff --git a/lib/StaticAnalyzer/Core/IssueHash.cpp b/lib/StaticAnalyzer/Core/IssueHash.cpp index abdea88b1db6..274ebe7a941b 100644 --- a/lib/StaticAnalyzer/Core/IssueHash.cpp +++ b/lib/StaticAnalyzer/Core/IssueHash.cpp @@ -33,6 +33,13 @@ static std::string GetSignature(const FunctionDecl *Target) { return ""; std::string Signature; + // When a flow sensitive bug happens in templated code we should not generate + // distinct hash value for every instantiation. Use the signature from the + // primary template. + if (const FunctionDecl *InstantiatedFrom = + Target->getTemplateInstantiationPattern()) + Target = InstantiatedFrom; + if (!isa<CXXConstructorDecl>(Target) && !isa<CXXDestructorDecl>(Target) && !isa<CXXConversionDecl>(Target)) Signature.append(Target->getReturnType().getAsString()).append(" "); diff --git a/lib/StaticAnalyzer/Core/LoopUnrolling.cpp b/lib/StaticAnalyzer/Core/LoopUnrolling.cpp new file mode 100644 index 000000000000..a8c4b05cea13 --- /dev/null +++ b/lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -0,0 +1,294 @@ +//===--- LoopUnrolling.cpp - Unroll loops -----------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// This file contains functions which are used to decide if a loop worth to be +/// unrolled. Moreover, these functions manages the stack of loop which is +/// tracked by the ProgramState. +/// +//===----------------------------------------------------------------------===// + +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h" + +using namespace clang; +using namespace ento; +using namespace clang::ast_matchers; + +static const int MAXIMUM_STEP_UNROLLED = 128; + +struct LoopState { +private: + enum Kind { Normal, Unrolled } K; + const Stmt *LoopStmt; + const LocationContext *LCtx; + unsigned maxStep; + LoopState(Kind InK, const Stmt *S, const LocationContext *L, unsigned N) + : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {} + +public: + static LoopState getNormal(const Stmt *S, const LocationContext *L, + unsigned N) { + return LoopState(Normal, S, L, N); + } + static LoopState getUnrolled(const Stmt *S, const LocationContext *L, + unsigned N) { + return LoopState(Unrolled, S, L, N); + } + bool isUnrolled() const { return K == Unrolled; } + unsigned getMaxStep() const { return maxStep; } + const Stmt *getLoopStmt() const { return LoopStmt; } + const LocationContext *getLocationContext() const { return LCtx; } + bool operator==(const LoopState &X) const { + return K == X.K && LoopStmt == X.LoopStmt; + } + void Profile(llvm::FoldingSetNodeID &ID) const { + ID.AddInteger(K); + ID.AddPointer(LoopStmt); + ID.AddPointer(LCtx); + ID.AddInteger(maxStep); + } +}; + +// The tracked stack of loops. The stack indicates that which loops the +// simulated element contained by. The loops are marked depending if we decided +// to unroll them. +// TODO: The loop stack should not need to be in the program state since it is +// lexical in nature. Instead, the stack of loops should be tracked in the +// LocationContext. +REGISTER_LIST_WITH_PROGRAMSTATE(LoopStack, LoopState) + +namespace clang { +namespace ento { + +static bool isLoopStmt(const Stmt *S) { + return S && (isa<ForStmt>(S) || isa<WhileStmt>(S) || isa<DoStmt>(S)); +} + +ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) { + auto LS = State->get<LoopStack>(); + if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt) + State = State->set<LoopStack>(LS.getTail()); + return State; +} + +static internal::Matcher<Stmt> simpleCondition(StringRef BindName) { + return binaryOperator(anyOf(hasOperatorName("<"), hasOperatorName(">"), + hasOperatorName("<="), hasOperatorName(">="), + hasOperatorName("!=")), + hasEitherOperand(ignoringParenImpCasts(declRefExpr( + to(varDecl(hasType(isInteger())).bind(BindName))))), + hasEitherOperand(ignoringParenImpCasts( + integerLiteral().bind("boundNum")))) + .bind("conditionOperator"); +} + +static internal::Matcher<Stmt> +changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) { + return anyOf( + unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")), + hasUnaryOperand(ignoringParenImpCasts( + declRefExpr(to(varDecl(VarNodeMatcher)))))), + binaryOperator(anyOf(hasOperatorName("="), hasOperatorName("+="), + hasOperatorName("/="), hasOperatorName("*="), + hasOperatorName("-=")), + hasLHS(ignoringParenImpCasts( + declRefExpr(to(varDecl(VarNodeMatcher))))))); +} + +static internal::Matcher<Stmt> +callByRef(internal::Matcher<Decl> VarNodeMatcher) { + return callExpr(forEachArgumentWithParam( + declRefExpr(to(varDecl(VarNodeMatcher))), + parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); +} + +static internal::Matcher<Stmt> +assignedToRef(internal::Matcher<Decl> VarNodeMatcher) { + return declStmt(hasDescendant(varDecl( + allOf(hasType(referenceType()), + hasInitializer(anyOf( + initListExpr(has(declRefExpr(to(varDecl(VarNodeMatcher))))), + declRefExpr(to(varDecl(VarNodeMatcher))))))))); +} + +static internal::Matcher<Stmt> +getAddrTo(internal::Matcher<Decl> VarNodeMatcher) { + return unaryOperator( + hasOperatorName("&"), + hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher)))); +} + +static internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) { + return hasDescendant(stmt( + anyOf(gotoStmt(), switchStmt(), returnStmt(), + // Escaping and not known mutation of the loop counter is handled + // by exclusion of assigning and address-of operators and + // pass-by-ref function calls on the loop counter from the body. + changeIntBoundNode(equalsBoundNode(NodeName)), + callByRef(equalsBoundNode(NodeName)), + getAddrTo(equalsBoundNode(NodeName)), + assignedToRef(equalsBoundNode(NodeName))))); +} + +static internal::Matcher<Stmt> forLoopMatcher() { + return forStmt( + hasCondition(simpleCondition("initVarName")), + // Initialization should match the form: 'int i = 6' or 'i = 42'. + hasLoopInit(anyOf( + declStmt(hasSingleDecl(varDecl( + allOf(hasInitializer(integerLiteral().bind("initNum")), + equalsBoundNode("initVarName"))))), + binaryOperator(hasLHS(declRefExpr(to( + varDecl(equalsBoundNode("initVarName"))))), + hasRHS(integerLiteral().bind("initNum"))))), + // Incrementation should be a simple increment or decrement + // operator call. + hasIncrement(unaryOperator( + anyOf(hasOperatorName("++"), hasOperatorName("--")), + hasUnaryOperand(declRefExpr( + to(varDecl(allOf(equalsBoundNode("initVarName"), + hasType(isInteger())))))))), + unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop"); +} + +static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N) { + // Global variables assumed as escaped variables. + if (VD->hasGlobalStorage()) + return true; + + while (!N->pred_empty()) { + const Stmt *S = PathDiagnosticLocation::getStmt(N); + if (!S) { + N = N->getFirstPred(); + continue; + } + + if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) { + for (const Decl *D : DS->decls()) { + // Once we reach the declaration of the VD we can return. + if (D->getCanonicalDecl() == VD) + return false; + } + } + // Check the usage of the pass-by-ref function calls and adress-of operator + // on VD and reference initialized by VD. + ASTContext &ASTCtx = + N->getLocationContext()->getAnalysisDeclContext()->getASTContext(); + auto Match = + match(stmt(anyOf(callByRef(equalsNode(VD)), getAddrTo(equalsNode(VD)), + assignedToRef(equalsNode(VD)))), + *S, ASTCtx); + if (!Match.empty()) + return true; + + N = N->getFirstPred(); + } + llvm_unreachable("Reached root without finding the declaration of VD"); +} + +bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, + ExplodedNode *Pred, unsigned &maxStep) { + + if (!isLoopStmt(LoopStmt)) + return false; + + // TODO: Match the cases where the bound is not a concrete literal but an + // integer with known value + auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx); + if (Matches.empty()) + return false; + + auto CounterVar = Matches[0].getNodeAs<VarDecl>("initVarName"); + llvm::APInt BoundNum = + Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue(); + llvm::APInt InitNum = + Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue(); + auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator"); + if (InitNum.getBitWidth() != BoundNum.getBitWidth()) { + InitNum = InitNum.zextOrSelf(BoundNum.getBitWidth()); + BoundNum = BoundNum.zextOrSelf(InitNum.getBitWidth()); + } + + if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE) + maxStep = (BoundNum - InitNum + 1).abs().getZExtValue(); + else + maxStep = (BoundNum - InitNum).abs().getZExtValue(); + + // Check if the counter of the loop is not escaped before. + return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred); +} + +bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt) { + const Stmt *S = nullptr; + while (!N->pred_empty()) { + if (N->succ_size() > 1) + return true; + + ProgramPoint P = N->getLocation(); + if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) + S = BE->getBlock()->getTerminator(); + + if (S == LoopStmt) + return false; + + N = N->getFirstPred(); + } + + llvm_unreachable("Reached root without encountering the previous step"); +} + +// updateLoopStack is called on every basic block, therefore it needs to be fast +ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx, + ExplodedNode *Pred, unsigned maxVisitOnPath) { + auto State = Pred->getState(); + auto LCtx = Pred->getLocationContext(); + + if (!isLoopStmt(LoopStmt)) + return State; + + auto LS = State->get<LoopStack>(); + if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() && + LCtx == LS.getHead().getLocationContext()) { + if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) { + State = State->set<LoopStack>(LS.getTail()); + State = State->add<LoopStack>( + LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); + } + return State; + } + unsigned maxStep; + if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, maxStep)) { + State = State->add<LoopStack>( + LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); + return State; + } + + unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep()); + + unsigned innerMaxStep = maxStep * outerStep; + if (innerMaxStep > MAXIMUM_STEP_UNROLLED) + State = State->add<LoopStack>( + LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); + else + State = State->add<LoopStack>( + LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep)); + return State; +} + +bool isUnrolledState(ProgramStateRef State) { + auto LS = State->get<LoopStack>(); + if (LS.isEmpty() || !LS.getHead().isUnrolled()) + return false; + return true; +} +} +} diff --git a/lib/StaticAnalyzer/Core/MemRegion.cpp b/lib/StaticAnalyzer/Core/MemRegion.cpp index 7bc186d5b994..cb8ba6de3626 100644 --- a/lib/StaticAnalyzer/Core/MemRegion.cpp +++ b/lib/StaticAnalyzer/Core/MemRegion.cpp @@ -18,7 +18,7 @@ #include "clang/AST/CharUnits.h" #include "clang/AST/DeclObjC.h" #include "clang/AST/RecordLayout.h" -#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/Support/BumpVector.h" #include "clang/Basic/SourceManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" @@ -472,6 +472,8 @@ void ObjCStringRegion::dumpToStream(raw_ostream &os) const { } void SymbolicRegion::dumpToStream(raw_ostream &os) const { + if (isa<HeapSpaceRegion>(getSuperRegion())) + os << "Heap"; os << "SymRegion{" << sym << '}'; } diff --git a/lib/StaticAnalyzer/Core/PathDiagnostic.cpp b/lib/StaticAnalyzer/Core/PathDiagnostic.cpp index d91786f74919..669748c0127a 100644 --- a/lib/StaticAnalyzer/Core/PathDiagnostic.cpp +++ b/lib/StaticAnalyzer/Core/PathDiagnostic.cpp @@ -578,8 +578,10 @@ getLocationForCaller(const StackFrameContext *SFC, } case CFGElement::TemporaryDtor: case CFGElement::NewAllocator: - case CFGElement::LifetimeEnds: llvm_unreachable("not yet implemented!"); + case CFGElement::LifetimeEnds: + case CFGElement::LoopExit: + llvm_unreachable("CFGElement kind should not be on callsite!"); } llvm_unreachable("Unknown CFGElement kind"); @@ -688,6 +690,15 @@ PathDiagnosticLocation::create(const ProgramPoint& P, return getLocationForCaller(CEE->getCalleeContext(), CEE->getLocationContext(), SMng); + } else if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) { + CFGElement BlockFront = BE->getBlock()->front(); + if (auto StmtElt = BlockFront.getAs<CFGStmt>()) { + return PathDiagnosticLocation(StmtElt->getStmt()->getLocStart(), SMng); + } else if (auto NewAllocElt = BlockFront.getAs<CFGNewAllocator>()) { + return PathDiagnosticLocation( + NewAllocElt->getAllocatorExpr()->getLocStart(), SMng); + } + llvm_unreachable("Unexpected CFG element at front of block"); } else { llvm_unreachable("Unexpected ProgramPoint"); } diff --git a/lib/StaticAnalyzer/Core/PrettyStackTraceLocationContext.h b/lib/StaticAnalyzer/Core/PrettyStackTraceLocationContext.h index e7cc23ca8234..4bb694819c2a 100644 --- a/lib/StaticAnalyzer/Core/PrettyStackTraceLocationContext.h +++ b/lib/StaticAnalyzer/Core/PrettyStackTraceLocationContext.h @@ -10,7 +10,7 @@ #ifndef LLVM_CLANG_LIB_STATICANALYZER_CORE_PRETTYSTACKTRACELOCATIONCONTEXT_H #define LLVM_CLANG_LIB_STATICANALYZER_CORE_PRETTYSTACKTRACELOCATIONCONTEXT_H -#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/AnalysisDeclContext.h" namespace clang { namespace ento { diff --git a/lib/StaticAnalyzer/Core/ProgramState.cpp b/lib/StaticAnalyzer/Core/ProgramState.cpp index 3215c3ccd21e..5b6b7339697f 100644 --- a/lib/StaticAnalyzer/Core/ProgramState.cpp +++ b/lib/StaticAnalyzer/Core/ProgramState.cpp @@ -260,7 +260,9 @@ SVal ProgramState::getSVal(Loc location, QualType T) const { // be a constant value, use that value instead to lessen the burden // on later analysis stages (so we have less symbolic values to reason // about). - if (!T.isNull()) { + // We only go into this branch if we can convert the APSInt value we have + // to the type of T, which is not always the case (e.g. for void). + if (!T.isNull() && (T->isIntegralOrEnumerationType() || Loc::isLocType(T))) { if (SymbolRef sym = V.getAsSymbol()) { if (const llvm::APSInt *Int = getStateManager() .getConstraintManager() diff --git a/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp b/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp index e0ad2d8ad45c..5a4031c0b4a5 100644 --- a/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ b/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -354,7 +354,8 @@ private: RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment); - RangeSet getSymLERange(const RangeSet &RS, const llvm::APSInt &Int, + RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS, + const llvm::APSInt &Int, const llvm::APSInt &Adjustment); RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, @@ -395,7 +396,9 @@ bool RangeConstraintManager::canReasonAbout(SVal X) const { } if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) { - if (BinaryOperator::isComparisonOp(SSE->getOpcode())) { + // FIXME: Handle <=> here. + if (BinaryOperator::isEqualityOp(SSE->getOpcode()) || + BinaryOperator::isRelationalOp(SSE->getOpcode())) { // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc. if (Loc::isLocType(SSE->getLHS()->getType())) { assert(Loc::isLocType(SSE->getRHS()->getType())); @@ -460,6 +463,53 @@ RangeConstraintManager::removeDeadBindings(ProgramStateRef State, return Changed ? State->set<ConstraintRange>(CR) : State; } +/// Return a range set subtracting zero from \p Domain. +static RangeSet assumeNonZero( + BasicValueFactory &BV, + RangeSet::Factory &F, + SymbolRef Sym, + RangeSet Domain) { + APSIntType IntType = BV.getAPSIntType(Sym->getType()); + return Domain.Intersect(BV, F, ++IntType.getZeroValue(), + --IntType.getZeroValue()); +} + +/// \brief Apply implicit constraints for bitwise OR- and AND-. +/// For unsigned types, bitwise OR with a constant always returns +/// a value greater-or-equal than the constant, and bitwise AND +/// returns a value less-or-equal then the constant. +/// +/// Pattern matches the expression \p Sym against those rule, +/// and applies the required constraints. +/// \p Input Previously established expression range set +static RangeSet applyBitwiseConstraints( + BasicValueFactory &BV, + RangeSet::Factory &F, + RangeSet Input, + const SymIntExpr* SIE) { + QualType T = SIE->getType(); + bool IsUnsigned = T->isUnsignedIntegerType(); + const llvm::APSInt &RHS = SIE->getRHS(); + const llvm::APSInt &Zero = BV.getAPSIntType(T).getZeroValue(); + BinaryOperator::Opcode Operator = SIE->getOpcode(); + + // For unsigned types, the output of bitwise-or is bigger-or-equal than RHS. + if (Operator == BO_Or && IsUnsigned) + return Input.Intersect(BV, F, RHS, BV.getMaxValue(T)); + + // Bitwise-or with a non-zero constant is always non-zero. + if (Operator == BO_Or && RHS != Zero) + return assumeNonZero(BV, F, SIE, Input); + + // For unsigned types, or positive RHS, + // bitwise-and output is always smaller-or-equal than RHS (assuming two's + // complement representation of signed types). + if (Operator == BO_And && (IsUnsigned || RHS >= Zero)) + return Input.Intersect(BV, F, BV.getMinValue(T), RHS); + + return Input; +} + RangeSet RangeConstraintManager::getRange(ProgramStateRef State, SymbolRef Sym) { if (ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym)) @@ -472,12 +522,13 @@ RangeSet RangeConstraintManager::getRange(ProgramStateRef State, RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T)); - // Special case: references are known to be non-zero. - if (T->isReferenceType()) { - APSIntType IntType = BV.getAPSIntType(T); - Result = Result.Intersect(BV, F, ++IntType.getZeroValue(), - --IntType.getZeroValue()); - } + // References are known to be non-zero. + if (T->isReferenceType()) + return assumeNonZero(BV, F, Sym, Result); + + // Known constraints on ranges of bitwise expressions. + if (const SymIntExpr* SIE = dyn_cast<SymIntExpr>(Sym)) + return applyBitwiseConstraints(BV, F, Result, SIE); return Result; } @@ -637,9 +688,10 @@ RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); } -RangeSet RangeConstraintManager::getSymLERange(const RangeSet &RS, - const llvm::APSInt &Int, - const llvm::APSInt &Adjustment) { +RangeSet RangeConstraintManager::getSymLERange( + llvm::function_ref<RangeSet()> RS, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { @@ -648,48 +700,27 @@ RangeSet RangeConstraintManager::getSymLERange(const RangeSet &RS, case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: - return RS; + return RS(); } // Special case for Int == Max. This is always feasible. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Max = AdjustmentType.getMaxValue(); if (ComparisonVal == Max) - return RS; + return RS(); llvm::APSInt Min = AdjustmentType.getMinValue(); llvm::APSInt Lower = Min - Adjustment; llvm::APSInt Upper = ComparisonVal - Adjustment; - return RS.Intersect(getBasicVals(), F, Lower, Upper); + return RS().Intersect(getBasicVals(), F, Lower, Upper); } RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { - // Before we do any real work, see if the value can even show up. - APSIntType AdjustmentType(Adjustment); - switch (AdjustmentType.testInRange(Int, true)) { - case APSIntType::RTR_Below: - return F.getEmptySet(); - case APSIntType::RTR_Within: - break; - case APSIntType::RTR_Above: - return getRange(St, Sym); - } - - // Special case for Int == Max. This is always feasible. - llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); - llvm::APSInt Max = AdjustmentType.getMaxValue(); - if (ComparisonVal == Max) - return getRange(St, Sym); - - llvm::APSInt Min = AdjustmentType.getMinValue(); - llvm::APSInt Lower = Min - Adjustment; - llvm::APSInt Upper = ComparisonVal - Adjustment; - - return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); + return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment); } ProgramStateRef @@ -706,8 +737,8 @@ ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange( RangeSet New = getSymGERange(State, Sym, From, Adjustment); if (New.isEmpty()) return nullptr; - New = getSymLERange(New, To, Adjustment); - return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New); + RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment); + return Out.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, Out); } ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange( diff --git a/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp b/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp index 1304116f4974..55ff15806efe 100644 --- a/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp +++ b/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp @@ -33,7 +33,7 @@ ProgramStateRef RangedConstraintManager::assumeSym(ProgramStateRef State, // We can only simplify expressions whose RHS is an integer. BinaryOperator::Opcode op = SIE->getOpcode(); - if (BinaryOperator::isComparisonOp(op)) { + if (BinaryOperator::isComparisonOp(op) && op != BO_Cmp) { if (!Assumption) op = BinaryOperator::negateComparisonOp(op); diff --git a/lib/StaticAnalyzer/Core/RegionStore.cpp b/lib/StaticAnalyzer/Core/RegionStore.cpp index 11902f66df91..7f2a481c6b0d 100644 --- a/lib/StaticAnalyzer/Core/RegionStore.cpp +++ b/lib/StaticAnalyzer/Core/RegionStore.cpp @@ -18,7 +18,7 @@ #include "clang/AST/Attr.h" #include "clang/AST/CharUnits.h" #include "clang/Analysis/Analyses/LiveVariables.h" -#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Basic/TargetInfo.h" #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" @@ -134,7 +134,9 @@ namespace llvm { }; } // end llvm namespace +#ifndef NDEBUG LLVM_DUMP_METHOD void BindingKey::dump() const { llvm::errs() << *this; } +#endif //===----------------------------------------------------------------------===// // Actual Store type. @@ -1393,17 +1395,17 @@ SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) return UnknownVal(); } - if (isa<AllocaRegion>(MR) || - isa<SymbolicRegion>(MR) || - isa<CodeTextRegion>(MR)) { + if (!isa<TypedValueRegion>(MR)) { if (T.isNull()) { if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR)) - T = TR->getLocationType(); - else { - const SymbolicRegion *SR = cast<SymbolicRegion>(MR); - T = SR->getSymbol()->getType(); - } + T = TR->getLocationType()->getPointeeType(); + else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) + T = SR->getSymbol()->getType()->getPointeeType(); + else if (isa<AllocaRegion>(MR)) + T = Ctx.VoidTy; } + assert(!T.isNull() && "Unable to auto-detect binding type!"); + assert(!T->isVoidType() && "Attempting to dereference a void pointer!"); MR = GetElementZeroRegion(cast<SubRegion>(MR), T); } @@ -1859,11 +1861,18 @@ SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B, return svalBuilder.getRegionValueSymbolVal(R); // Is 'VD' declared constant? If so, retrieve the constant value. - if (VD->getType().isConstQualified()) - if (const Expr *Init = VD->getInit()) + if (VD->getType().isConstQualified()) { + if (const Expr *Init = VD->getInit()) { if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) return *V; + // If the variable is const qualified and has an initializer but + // we couldn't evaluate initializer to a value, treat the value as + // unknown. + return UnknownVal(); + } + } + // This must come after the check for constants because closure-captured // constant variables may appear in UnknownSpaceRegion. if (isa<UnknownSpaceRegion>(MS)) @@ -2085,15 +2094,12 @@ RegionStoreManager::bindArray(RegionBindingsConstRef B, if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT)) Size = CAT->getSize().getZExtValue(); - // Check if the init expr is a string literal. + // Check if the init expr is a literal. If so, bind the rvalue instead. + // FIXME: It's not responsibility of the Store to transform this lvalue + // to rvalue. ExprEngine or maybe even CFG should do this before binding. if (Optional<loc::MemRegionVal> MRV = Init.getAs<loc::MemRegionVal>()) { - const StringRegion *S = cast<StringRegion>(MRV->getRegion()); - - // Treat the string as a lazy compound value. - StoreRef store(B.asStore(), *this); - nonloc::LazyCompoundVal LCV = svalBuilder.makeLazyCompoundVal(store, S) - .castAs<nonloc::LazyCompoundVal>(); - return bindAggregate(B, R, LCV); + SVal V = getBinding(B.asStore(), *MRV, R->getValueType()); + return bindAggregate(B, R, V); } // Handle lazy compound values. diff --git a/lib/StaticAnalyzer/Core/SVals.cpp b/lib/StaticAnalyzer/Core/SVals.cpp index 9f2af3ffa709..a83421426a13 100644 --- a/lib/StaticAnalyzer/Core/SVals.cpp +++ b/lib/StaticAnalyzer/Core/SVals.cpp @@ -113,12 +113,12 @@ SymbolRef SVal::getLocSymbolInBase() const { /// Casts are ignored during lookup. /// \param IncludeBaseRegions The boolean that controls whether the search /// should continue to the base regions if the region is not symbolic. -SymbolRef SVal::getAsSymbol(bool IncludeBaseRegion) const { +SymbolRef SVal::getAsSymbol(bool IncludeBaseRegions) const { // FIXME: should we consider SymbolRef wrapped in CodeTextRegion? if (Optional<nonloc::SymbolVal> X = getAs<nonloc::SymbolVal>()) return X->getSymbol(); - return getAsLocSymbol(IncludeBaseRegion); + return getAsLocSymbol(IncludeBaseRegions); } /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then diff --git a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp index f09f9696f5ad..94d29d5a6ba3 100644 --- a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp +++ b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp @@ -360,10 +360,18 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, Loc lhsL = lhs.castAs<nonloc::LocAsInteger>().getLoc(); switch (rhs.getSubKind()) { case nonloc::LocAsIntegerKind: + // FIXME: at the moment the implementation + // of modeling "pointers as integers" is not complete. + if (!BinaryOperator::isComparisonOp(op)) + return UnknownVal(); return evalBinOpLL(state, op, lhsL, rhs.castAs<nonloc::LocAsInteger>().getLoc(), resultTy); case nonloc::ConcreteIntKind: { + // FIXME: at the moment the implementation + // of modeling "pointers as integers" is not complete. + if (!BinaryOperator::isComparisonOp(op)) + return UnknownVal(); // Transform the integer into a location and compare. // FIXME: This only makes sense for comparisons. If we want to, say, // add 1 to a LocAsInteger, we'd better unpack the Loc and add to it, @@ -671,7 +679,7 @@ SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, if (SymbolRef rSym = rhs.getAsLocSymbol()) { // We can only build expressions with symbols on the left, // so we need a reversible operator. - if (!BinaryOperator::isComparisonOp(op)) + if (!BinaryOperator::isComparisonOp(op) || op == BO_Cmp) return UnknownVal(); const llvm::APSInt &lVal = lhs.castAs<loc::ConcreteInt>().getValue(); @@ -718,9 +726,11 @@ 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(true)) - return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy); - + if (SymbolRef lSym = lhs.getAsLocSymbol(true)) { + if (BinaryOperator::isComparisonOp(op)) + return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy); + return UnknownVal(); + } // Special case comparisons to NULL. // This must come after the test if the LHS is a symbol, which is used to // build constraints. The address of any non-symbolic region is guaranteed @@ -912,6 +922,10 @@ SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state, if (rhs.isZeroConstant()) return lhs; + // Perserve the null pointer so that it can be found by the DerefChecker. + if (lhs.isZeroConstant()) + return lhs; + // We are dealing with pointer arithmetic. // Handle pointer arithmetic on constant values. @@ -927,6 +941,8 @@ SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state, // Offset the increment by the pointer size. llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true); + QualType pointeeType = resultTy->getPointeeType(); + Multiplicand = getContext().getTypeSizeInChars(pointeeType).getQuantity(); rightI *= Multiplicand; // Compute the adjusted pointer. @@ -1016,7 +1032,8 @@ SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) { SVB.getKnownValue(State, nonloc::SymbolVal(S))) return Loc::isLocType(S->getType()) ? (SVal)SVB.makeIntLocVal(*I) : (SVal)SVB.makeIntVal(*I); - return nonloc::SymbolVal(S); + return Loc::isLocType(S->getType()) ? (SVal)SVB.makeLoc(S) + : nonloc::SymbolVal(S); } // TODO: Support SymbolCast. Support IntSymExpr when/if we actually diff --git a/lib/StaticAnalyzer/Core/Store.cpp b/lib/StaticAnalyzer/Core/Store.cpp index 1af49f68cc05..173fdd8d0056 100644 --- a/lib/StaticAnalyzer/Core/Store.cpp +++ b/lib/StaticAnalyzer/Core/Store.cpp @@ -440,7 +440,10 @@ SVal StoreManager::getLValueElement(QualType elementType, NonLoc Offset, // value. See also the similar FIXME in getLValueFieldOrIvar(). if (Base.isUnknownOrUndef() || Base.getAs<loc::ConcreteInt>()) return Base; - + + if (Base.getAs<loc::GotoLabel>()) + return UnknownVal(); + const SubRegion *BaseRegion = Base.castAs<loc::MemRegionVal>().getRegionAs<SubRegion>(); diff --git a/lib/StaticAnalyzer/Core/SymbolManager.cpp b/lib/StaticAnalyzer/Core/SymbolManager.cpp index 4be85661b645..f2d5ee83f3cc 100644 --- a/lib/StaticAnalyzer/Core/SymbolManager.cpp +++ b/lib/StaticAnalyzer/Core/SymbolManager.cpp @@ -31,14 +31,20 @@ void SymIntExpr::dumpToStream(raw_ostream &os) const { os << '('; getLHS()->dumpToStream(os); os << ") " - << BinaryOperator::getOpcodeStr(getOpcode()) << ' ' - << getRHS().getZExtValue(); + << BinaryOperator::getOpcodeStr(getOpcode()) << ' '; + if (getRHS().isUnsigned()) + os << getRHS().getZExtValue(); + else + os << getRHS().getSExtValue(); if (getRHS().isUnsigned()) os << 'U'; } void IntSymExpr::dumpToStream(raw_ostream &os) const { - os << getLHS().getZExtValue(); + if (getLHS().isUnsigned()) + os << getLHS().getZExtValue(); + else + os << getLHS().getSExtValue(); if (getLHS().isUnsigned()) os << 'U'; os << ' ' |