diff options
author | dim <dim@FreeBSD.org> | 2012-12-02 13:20:44 +0000 |
---|---|---|
committer | dim <dim@FreeBSD.org> | 2012-12-02 13:20:44 +0000 |
commit | 056abd2059c65a3e908193aeae16fad98017437c (patch) | |
tree | 2732d02d7d51218d6eed98ac7fcfc5b8794896b5 /lib/StaticAnalyzer/Core | |
parent | cc73504950eb7b5dff2dded9bedd67bc36d64641 (diff) | |
download | FreeBSD-src-056abd2059c65a3e908193aeae16fad98017437c.zip FreeBSD-src-056abd2059c65a3e908193aeae16fad98017437c.tar.gz |
Vendor import of clang release_32 branch r168974 (effectively, 3.2 RC2):
http://llvm.org/svn/llvm-project/cfe/branches/release_32@168974
Diffstat (limited to 'lib/StaticAnalyzer/Core')
34 files changed, 2677 insertions, 1921 deletions
diff --git a/lib/StaticAnalyzer/Core/AnalysisManager.cpp b/lib/StaticAnalyzer/Core/AnalysisManager.cpp index efeba17..011d4c09 100644 --- a/lib/StaticAnalyzer/Core/AnalysisManager.cpp +++ b/lib/StaticAnalyzer/Core/AnalysisManager.cpp @@ -20,33 +20,19 @@ AnalysisManager::AnalysisManager(ASTContext &ctx, DiagnosticsEngine &diags, StoreManagerCreator storemgr, ConstraintManagerCreator constraintmgr, CheckerManager *checkerMgr, - unsigned maxnodes, unsigned maxvisit, - bool vizdot, bool vizubi, - AnalysisPurgeMode purge, - bool eager, bool trim, - bool useUnoptimizedCFG, - bool addImplicitDtors, - bool eagerlyTrimEGraph, - AnalysisIPAMode ipa, - unsigned inlineMaxStack, - unsigned inlineMaxFunctionSize, - AnalysisInliningMode IMode, - bool NoRetry) - : AnaCtxMgr(useUnoptimizedCFG, addImplicitDtors, /*addInitializers=*/true), - Ctx(ctx), Diags(diags), LangOpts(lang), + AnalyzerOptions &Options) + : AnaCtxMgr(Options.UnoptimizedCFG, + /*AddImplicitDtors=*/true, + /*AddInitializers=*/true, + Options.includeTemporaryDtorsInCFG(), + Options.shouldSynthesizeBodies()), + Ctx(ctx), + Diags(diags), + LangOpts(lang), PathConsumers(PDC), CreateStoreMgr(storemgr), CreateConstraintMgr(constraintmgr), - CheckerMgr(checkerMgr), - MaxNodes(maxnodes), MaxVisit(maxvisit), - VisualizeEGDot(vizdot), VisualizeEGUbi(vizubi), PurgeDead(purge), - EagerlyAssume(eager), TrimGraph(trim), - EagerlyTrimEGraph(eagerlyTrimEGraph), - IPAMode(ipa), - InlineMaxStackDepth(inlineMaxStack), - InlineMaxFunctionSize(inlineMaxFunctionSize), - InliningMode(IMode), - NoRetryExhausted(NoRetry) -{ + CheckerMgr(checkerMgr), + options(Options) { AnaCtxMgr.getCFGBuildOptions().setAllAlwaysAdd(); } diff --git a/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp b/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp new file mode 100644 index 0000000..da88589 --- /dev/null +++ b/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp @@ -0,0 +1,138 @@ +//===-- AnalyzerOptions.cpp - Analysis Engine Options -----------*- 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 special accessors for analyzer configuration options +// with string representations. +// +//===----------------------------------------------------------------------===// + +#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" +#include "llvm/ADT/StringSwitch.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/Support/raw_ostream.h" + +using namespace clang; +using namespace llvm; + +bool +AnalyzerOptions::mayInlineCXXMemberFunction(CXXInlineableMemberKind K) { + if (IPAMode < Inlining) + return false; + + if (!CXXMemberInliningMode) { + static const char *ModeKey = "c++-inlining"; + + StringRef ModeStr(Config.GetOrCreateValue(ModeKey, + "methods").getValue()); + + CXXInlineableMemberKind &MutableMode = + const_cast<CXXInlineableMemberKind &>(CXXMemberInliningMode); + + MutableMode = llvm::StringSwitch<CXXInlineableMemberKind>(ModeStr) + .Case("constructors", CIMK_Constructors) + .Case("destructors", CIMK_Destructors) + .Case("none", CIMK_None) + .Case("methods", CIMK_MemberFunctions) + .Default(CXXInlineableMemberKind()); + + if (!MutableMode) { + // FIXME: We should emit a warning here about an unknown inlining kind, + // but the AnalyzerOptions doesn't have access to a diagnostic engine. + MutableMode = CIMK_None; + } + } + + return CXXMemberInliningMode >= K; +} + +static StringRef toString(bool b) { return b ? "true" : "false"; } + +bool AnalyzerOptions::getBooleanOption(StringRef Name, bool DefaultVal) { + // FIXME: We should emit a warning here if the value is something other than + // "true", "false", or the empty string (meaning the default value), + // but the AnalyzerOptions doesn't have access to a diagnostic engine. + StringRef V(Config.GetOrCreateValue(Name, toString(DefaultVal)).getValue()); + return llvm::StringSwitch<bool>(V) + .Case("true", true) + .Case("false", false) + .Default(DefaultVal); +} + +bool AnalyzerOptions::getBooleanOption(llvm::Optional<bool> &V, + StringRef Name, + bool DefaultVal) { + if (!V.hasValue()) + V = getBooleanOption(Name, DefaultVal); + return V.getValue(); +} + +bool AnalyzerOptions::includeTemporaryDtorsInCFG() { + return getBooleanOption(IncludeTemporaryDtorsInCFG, + "cfg-temporary-dtors", + /* Default = */ false); +} + +bool AnalyzerOptions::mayInlineCXXStandardLibrary() { + return getBooleanOption(InlineCXXStandardLibrary, + "c++-stdlib-inlining", + /*Default=*/true); +} + +bool AnalyzerOptions::mayInlineTemplateFunctions() { + return getBooleanOption(InlineTemplateFunctions, + "c++-template-inlining", + /*Default=*/true); +} + +bool AnalyzerOptions::mayInlineObjCMethod() { + return getBooleanOption(ObjCInliningMode, + "objc-inlining", + /* Default = */ true); +} + +bool AnalyzerOptions::shouldPruneNullReturnPaths() { + return getBooleanOption(PruneNullReturnPaths, + "suppress-null-return-paths", + /* Default = */ true); +} + +bool AnalyzerOptions::shouldAvoidSuppressingNullArgumentPaths() { + return getBooleanOption(AvoidSuppressingNullArgumentPaths, + "avoid-suppressing-null-argument-paths", + /* Default = */ false); +} + +int AnalyzerOptions::getOptionAsInteger(StringRef Name, int DefaultVal) { + llvm::SmallString<10> StrBuf; + llvm::raw_svector_ostream OS(StrBuf); + OS << DefaultVal; + + StringRef V(Config.GetOrCreateValue(Name, OS.str()).getValue()); + int Res = DefaultVal; + bool b = V.getAsInteger(10, Res); + assert(!b && "analyzer-config option should be numeric"); + (void) b; + return Res; +} + +unsigned AnalyzerOptions::getAlwaysInlineSize() { + if (!AlwaysInlineSize.hasValue()) + AlwaysInlineSize = getOptionAsInteger("ipa-always-inline-size", 3); + return AlwaysInlineSize.getValue(); +} + +unsigned AnalyzerOptions::getGraphTrimInterval() { + if (!GraphTrimInterval.hasValue()) + GraphTrimInterval = getOptionAsInteger("graph-trim-interval", 1000); + return GraphTrimInterval.getValue(); +} + +bool AnalyzerOptions::shouldSynthesizeBodies() { + return getBooleanOption("faux-bodies", true); +} diff --git a/lib/StaticAnalyzer/Core/BasicConstraintManager.cpp b/lib/StaticAnalyzer/Core/BasicConstraintManager.cpp deleted file mode 100644 index 8897756..0000000 --- a/lib/StaticAnalyzer/Core/BasicConstraintManager.cpp +++ /dev/null @@ -1,446 +0,0 @@ -//== BasicConstraintManager.cpp - Manage basic constraints.------*- 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 BasicConstraintManager, a class that tracks simple -// equality and inequality constraints on symbolic values of ProgramState. -// -//===----------------------------------------------------------------------===// - -#include "SimpleConstraintManager.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" -#include "llvm/Support/raw_ostream.h" - -using namespace clang; -using namespace ento; - - -namespace { class ConstNotEq {}; } -namespace { class ConstEq {}; } - -typedef llvm::ImmutableMap<SymbolRef,ProgramState::IntSetTy> ConstNotEqTy; -typedef llvm::ImmutableMap<SymbolRef,const llvm::APSInt*> ConstEqTy; - -static int ConstEqIndex = 0; -static int ConstNotEqIndex = 0; - -namespace clang { -namespace ento { -template<> -struct ProgramStateTrait<ConstNotEq> : - public ProgramStatePartialTrait<ConstNotEqTy> { - static inline void *GDMIndex() { return &ConstNotEqIndex; } -}; - -template<> -struct ProgramStateTrait<ConstEq> : public ProgramStatePartialTrait<ConstEqTy> { - static inline void *GDMIndex() { return &ConstEqIndex; } -}; -} -} - -namespace { -// BasicConstraintManager only tracks equality and inequality constraints of -// constants and integer variables. -class BasicConstraintManager - : public SimpleConstraintManager { - ProgramState::IntSetTy::Factory ISetFactory; -public: - BasicConstraintManager(ProgramStateManager &statemgr, SubEngine &subengine) - : SimpleConstraintManager(subengine, statemgr.getBasicVals()), - ISetFactory(statemgr.getAllocator()) {} - - ProgramStateRef assumeSymEquality(ProgramStateRef State, SymbolRef Sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment, - bool Assumption); - - ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment) { - return assumeSymEquality(State, Sym, V, Adjustment, false); - } - - ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment) { - return assumeSymEquality(State, Sym, V, Adjustment, true); - } - - ProgramStateRef assumeSymLT(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt& V, - const llvm::APSInt& Adjustment); - - ProgramStateRef assumeSymGT(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt& V, - const llvm::APSInt& Adjustment); - - ProgramStateRef assumeSymGE(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt& V, - const llvm::APSInt& Adjustment); - - ProgramStateRef assumeSymLE(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt& V, - const llvm::APSInt& Adjustment); - - ProgramStateRef AddEQ(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt& V); - - ProgramStateRef AddNE(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt& V); - - const llvm::APSInt* getSymVal(ProgramStateRef state, - SymbolRef sym) const; - - bool isNotEqual(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt& V) const; - - bool isEqual(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt& V) const; - - ProgramStateRef removeDeadBindings(ProgramStateRef state, - SymbolReaper& SymReaper); - - bool performTest(llvm::APSInt SymVal, llvm::APSInt Adjustment, - BinaryOperator::Opcode Op, llvm::APSInt ComparisonVal); - - void print(ProgramStateRef state, - raw_ostream &Out, - const char* nl, - const char *sep); -}; - -} // end anonymous namespace - -ConstraintManager* -ento::CreateBasicConstraintManager(ProgramStateManager& statemgr, - SubEngine &subengine) { - return new BasicConstraintManager(statemgr, subengine); -} - -// FIXME: This is a more general utility and should live somewhere else. -bool BasicConstraintManager::performTest(llvm::APSInt SymVal, - llvm::APSInt Adjustment, - BinaryOperator::Opcode Op, - llvm::APSInt ComparisonVal) { - APSIntType Type(Adjustment); - Type.apply(SymVal); - Type.apply(ComparisonVal); - SymVal += Adjustment; - - assert(BinaryOperator::isComparisonOp(Op)); - BasicValueFactory &BVF = getBasicVals(); - const llvm::APSInt *Result = BVF.evalAPSInt(Op, SymVal, ComparisonVal); - assert(Result && "Comparisons should always have valid results."); - - return Result->getBoolValue(); -} - -ProgramStateRef -BasicConstraintManager::assumeSymEquality(ProgramStateRef State, SymbolRef Sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment, - bool Assumption) { - // Before we do any real work, see if the value can even show up. - APSIntType AdjustmentType(Adjustment); - if (AdjustmentType.testInRange(V) != APSIntType::RTR_Within) - return Assumption ? NULL : State; - - // Get the symbol type. - BasicValueFactory &BVF = getBasicVals(); - ASTContext &Ctx = BVF.getContext(); - APSIntType SymbolType = BVF.getAPSIntType(Sym->getType(Ctx)); - - // First, see if the adjusted value is within range for the symbol. - llvm::APSInt Adjusted = AdjustmentType.convert(V) - Adjustment; - if (SymbolType.testInRange(Adjusted) != APSIntType::RTR_Within) - return Assumption ? NULL : State; - - // Now we can do things properly in the symbol space. - SymbolType.apply(Adjusted); - - // Second, determine if sym == X, where X+Adjustment != V. - if (const llvm::APSInt *X = getSymVal(State, Sym)) { - bool IsFeasible = (*X == Adjusted); - return (IsFeasible == Assumption) ? State : NULL; - } - - // Third, determine if we already know sym+Adjustment != V. - if (isNotEqual(State, Sym, Adjusted)) - return Assumption ? NULL : State; - - // If we reach here, sym is not a constant and we don't know if it is != V. - // Make the correct assumption. - if (Assumption) - return AddEQ(State, Sym, Adjusted); - else - return AddNE(State, Sym, Adjusted); -} - -// The logic for these will be handled in another ConstraintManager. -// Approximate it here anyway by handling some edge cases. -ProgramStateRef -BasicConstraintManager::assumeSymLT(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment) { - APSIntType ComparisonType(V), AdjustmentType(Adjustment); - - // Is 'V' out of range above the type? - llvm::APSInt Max = AdjustmentType.getMaxValue(); - if (V > ComparisonType.convert(Max)) { - // This path is trivially feasible. - return state; - } - - // Is 'V' the smallest possible value, or out of range below the type? - llvm::APSInt Min = AdjustmentType.getMinValue(); - if (V <= ComparisonType.convert(Min)) { - // sym cannot be any value less than 'V'. This path is infeasible. - return NULL; - } - - // Reject a path if the value of sym is a constant X and !(X+Adj < V). - if (const llvm::APSInt *X = getSymVal(state, sym)) { - bool isFeasible = performTest(*X, Adjustment, BO_LT, V); - return isFeasible ? state : NULL; - } - - // FIXME: For now have assuming x < y be the same as assuming sym != V; - return assumeSymNE(state, sym, V, Adjustment); -} - -ProgramStateRef -BasicConstraintManager::assumeSymGT(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment) { - APSIntType ComparisonType(V), AdjustmentType(Adjustment); - - // Is 'V' the largest possible value, or out of range above the type? - llvm::APSInt Max = AdjustmentType.getMaxValue(); - if (V >= ComparisonType.convert(Max)) { - // sym cannot be any value greater than 'V'. This path is infeasible. - return NULL; - } - - // Is 'V' out of range below the type? - llvm::APSInt Min = AdjustmentType.getMinValue(); - if (V < ComparisonType.convert(Min)) { - // This path is trivially feasible. - return state; - } - - // Reject a path if the value of sym is a constant X and !(X+Adj > V). - if (const llvm::APSInt *X = getSymVal(state, sym)) { - bool isFeasible = performTest(*X, Adjustment, BO_GT, V); - return isFeasible ? state : NULL; - } - - // FIXME: For now have assuming x > y be the same as assuming sym != V; - return assumeSymNE(state, sym, V, Adjustment); -} - -ProgramStateRef -BasicConstraintManager::assumeSymGE(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment) { - APSIntType ComparisonType(V), AdjustmentType(Adjustment); - - // Is 'V' the largest possible value, or out of range above the type? - llvm::APSInt Max = AdjustmentType.getMaxValue(); - ComparisonType.apply(Max); - - if (V > Max) { - // sym cannot be any value greater than 'V'. This path is infeasible. - return NULL; - } else if (V == Max) { - // If the path is feasible then as a consequence we know that - // 'sym+Adjustment == V' because there are no larger values. - // Add this constraint. - return assumeSymEQ(state, sym, V, Adjustment); - } - - // Is 'V' out of range below the type? - llvm::APSInt Min = AdjustmentType.getMinValue(); - if (V < ComparisonType.convert(Min)) { - // This path is trivially feasible. - return state; - } - - // Reject a path if the value of sym is a constant X and !(X+Adj >= V). - if (const llvm::APSInt *X = getSymVal(state, sym)) { - bool isFeasible = performTest(*X, Adjustment, BO_GE, V); - return isFeasible ? state : NULL; - } - - return state; -} - -ProgramStateRef -BasicConstraintManager::assumeSymLE(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment) { - APSIntType ComparisonType(V), AdjustmentType(Adjustment); - - // Is 'V' out of range above the type? - llvm::APSInt Max = AdjustmentType.getMaxValue(); - if (V > ComparisonType.convert(Max)) { - // This path is trivially feasible. - return state; - } - - // Is 'V' the smallest possible value, or out of range below the type? - llvm::APSInt Min = AdjustmentType.getMinValue(); - ComparisonType.apply(Min); - - if (V < Min) { - // sym cannot be any value less than 'V'. This path is infeasible. - return NULL; - } else if (V == Min) { - // If the path is feasible then as a consequence we know that - // 'sym+Adjustment == V' because there are no smaller values. - // Add this constraint. - return assumeSymEQ(state, sym, V, Adjustment); - } - - // Reject a path if the value of sym is a constant X and !(X+Adj >= V). - if (const llvm::APSInt *X = getSymVal(state, sym)) { - bool isFeasible = performTest(*X, Adjustment, BO_LE, V); - return isFeasible ? state : NULL; - } - - return state; -} - -ProgramStateRef BasicConstraintManager::AddEQ(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt& V) { - // Now that we have an actual value, we can throw out the NE-set. - // Create a new state with the old bindings replaced. - state = state->remove<ConstNotEq>(sym); - return state->set<ConstEq>(sym, &getBasicVals().getValue(V)); -} - -ProgramStateRef BasicConstraintManager::AddNE(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt& V) { - - // First, retrieve the NE-set associated with the given symbol. - ConstNotEqTy::data_type* T = state->get<ConstNotEq>(sym); - ProgramState::IntSetTy S = T ? *T : ISetFactory.getEmptySet(); - - // Now add V to the NE set. - S = ISetFactory.add(S, &getBasicVals().getValue(V)); - - // Create a new state with the old binding replaced. - return state->set<ConstNotEq>(sym, S); -} - -const llvm::APSInt* BasicConstraintManager::getSymVal(ProgramStateRef state, - SymbolRef sym) const { - const ConstEqTy::data_type* T = state->get<ConstEq>(sym); - return T ? *T : NULL; -} - -bool BasicConstraintManager::isNotEqual(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt& V) const { - - // Retrieve the NE-set associated with the given symbol. - const ConstNotEqTy::data_type* T = state->get<ConstNotEq>(sym); - - // See if V is present in the NE-set. - return T ? T->contains(&getBasicVals().getValue(V)) : false; -} - -bool BasicConstraintManager::isEqual(ProgramStateRef state, - SymbolRef sym, - const llvm::APSInt& V) const { - // Retrieve the EQ-set associated with the given symbol. - const ConstEqTy::data_type* T = state->get<ConstEq>(sym); - // See if V is present in the EQ-set. - return T ? **T == V : false; -} - -/// Scan all symbols referenced by the constraints. If the symbol is not alive -/// as marked in LSymbols, mark it as dead in DSymbols. -ProgramStateRef -BasicConstraintManager::removeDeadBindings(ProgramStateRef state, - SymbolReaper& SymReaper) { - - ConstEqTy CE = state->get<ConstEq>(); - ConstEqTy::Factory& CEFactory = state->get_context<ConstEq>(); - - for (ConstEqTy::iterator I = CE.begin(), E = CE.end(); I!=E; ++I) { - SymbolRef sym = I.getKey(); - if (SymReaper.maybeDead(sym)) - CE = CEFactory.remove(CE, sym); - } - state = state->set<ConstEq>(CE); - - ConstNotEqTy CNE = state->get<ConstNotEq>(); - ConstNotEqTy::Factory& CNEFactory = state->get_context<ConstNotEq>(); - - for (ConstNotEqTy::iterator I = CNE.begin(), E = CNE.end(); I != E; ++I) { - SymbolRef sym = I.getKey(); - if (SymReaper.maybeDead(sym)) - CNE = CNEFactory.remove(CNE, sym); - } - - return state->set<ConstNotEq>(CNE); -} - -void BasicConstraintManager::print(ProgramStateRef state, - raw_ostream &Out, - const char* nl, const char *sep) { - // Print equality constraints. - - ConstEqTy CE = state->get<ConstEq>(); - - if (!CE.isEmpty()) { - Out << nl << sep << "'==' constraints:"; - for (ConstEqTy::iterator I = CE.begin(), E = CE.end(); I!=E; ++I) - Out << nl << " $" << I.getKey() << " : " << *I.getData(); - } - - // Print != constraints. - - ConstNotEqTy CNE = state->get<ConstNotEq>(); - - if (!CNE.isEmpty()) { - Out << nl << sep << "'!=' constraints:"; - - for (ConstNotEqTy::iterator I = CNE.begin(), EI = CNE.end(); I!=EI; ++I) { - Out << nl << " $" << I.getKey() << " : "; - bool isFirst = true; - - ProgramState::IntSetTy::iterator J = I.getData().begin(), - EJ = I.getData().end(); - - for ( ; J != EJ; ++J) { - if (isFirst) isFirst = false; - else Out << ", "; - - Out << (*J)->getSExtValue(); // Hack: should print to raw_ostream. - } - } - } -} diff --git a/lib/StaticAnalyzer/Core/BasicValueFactory.cpp b/lib/StaticAnalyzer/Core/BasicValueFactory.cpp index 20c7361..a6c400f 100644 --- a/lib/StaticAnalyzer/Core/BasicValueFactory.cpp +++ b/lib/StaticAnalyzer/Core/BasicValueFactory.cpp @@ -101,11 +101,7 @@ const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth, const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) { - unsigned bits = Ctx.getTypeSize(T); - llvm::APSInt V(bits, - T->isUnsignedIntegerOrEnumerationType() || Loc::isLocType(T)); - V = X; - return getValue(V); + return getValue(getAPSIntType(T).getValue(X)); } const CompoundValData* diff --git a/lib/StaticAnalyzer/Core/BugReporter.cpp b/lib/StaticAnalyzer/Core/BugReporter.cpp index 571baec..c898d65 100644 --- a/lib/StaticAnalyzer/Core/BugReporter.cpp +++ b/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -118,10 +118,82 @@ GetCurrentOrNextStmt(const ExplodedNode *N) { // Diagnostic cleanup. //===----------------------------------------------------------------------===// +static PathDiagnosticEventPiece * +eventsDescribeSameCondition(PathDiagnosticEventPiece *X, + PathDiagnosticEventPiece *Y) { + // Prefer diagnostics that come from ConditionBRVisitor over + // those that came from TrackConstraintBRVisitor. + const void *tagPreferred = ConditionBRVisitor::getTag(); + const void *tagLesser = TrackConstraintBRVisitor::getTag(); + + if (X->getLocation() != Y->getLocation()) + return 0; + + if (X->getTag() == tagPreferred && Y->getTag() == tagLesser) + return X; + + if (Y->getTag() == tagPreferred && X->getTag() == tagLesser) + return Y; + + return 0; +} + +/// An optimization pass over PathPieces that removes redundant diagnostics +/// generated by both ConditionBRVisitor and TrackConstraintBRVisitor. Both +/// BugReporterVisitors use different methods to generate diagnostics, with +/// one capable of emitting diagnostics in some cases but not in others. This +/// can lead to redundant diagnostic pieces at the same point in a path. +static void removeRedundantMsgs(PathPieces &path) { + unsigned N = path.size(); + if (N < 2) + return; + // NOTE: this loop intentionally is not using an iterator. Instead, we + // are streaming the path and modifying it in place. This is done by + // grabbing the front, processing it, and if we decide to keep it append + // it to the end of the path. The entire path is processed in this way. + for (unsigned i = 0; i < N; ++i) { + IntrusiveRefCntPtr<PathDiagnosticPiece> piece(path.front()); + path.pop_front(); + + switch (piece->getKind()) { + case clang::ento::PathDiagnosticPiece::Call: + removeRedundantMsgs(cast<PathDiagnosticCallPiece>(piece)->path); + break; + case clang::ento::PathDiagnosticPiece::Macro: + removeRedundantMsgs(cast<PathDiagnosticMacroPiece>(piece)->subPieces); + break; + case clang::ento::PathDiagnosticPiece::ControlFlow: + break; + case clang::ento::PathDiagnosticPiece::Event: { + if (i == N-1) + break; + + if (PathDiagnosticEventPiece *nextEvent = + dyn_cast<PathDiagnosticEventPiece>(path.front().getPtr())) { + PathDiagnosticEventPiece *event = + cast<PathDiagnosticEventPiece>(piece); + // Check to see if we should keep one of the two pieces. If we + // come up with a preference, record which piece to keep, and consume + // another piece from the path. + if (PathDiagnosticEventPiece *pieceToKeep = + eventsDescribeSameCondition(event, nextEvent)) { + piece = pieceToKeep; + path.pop_front(); + ++i; + } + } + break; + } + } + path.push_back(piece); + } +} + /// Recursively scan through a path and prune out calls and macros pieces /// that aren't needed. Return true if afterwards the path contains /// "interesting stuff" which means it should be pruned from the parent path. -static bool RemoveUneededCalls(PathPieces &pieces) { +bool BugReporter::RemoveUneededCalls(PathPieces &pieces, BugReport *R, + PathDiagnosticCallPiece *CallWithLoc) { bool containsSomethingInteresting = false; const unsigned N = pieces.size(); @@ -131,30 +203,49 @@ static bool RemoveUneededCalls(PathPieces &pieces) { IntrusiveRefCntPtr<PathDiagnosticPiece> piece(pieces.front()); pieces.pop_front(); + // Throw away pieces with invalid locations. + if (piece->getKind() != PathDiagnosticPiece::Call && + piece->getLocation().asLocation().isInvalid()) + continue; + switch (piece->getKind()) { case PathDiagnosticPiece::Call: { PathDiagnosticCallPiece *call = cast<PathDiagnosticCallPiece>(piece); + // Check if the location context is interesting. + assert(LocationContextMap.count(call)); + if (R->isInteresting(LocationContextMap[call])) { + containsSomethingInteresting = true; + break; + } // Recursively clean out the subclass. Keep this call around if // it contains any informative diagnostics. - if (!RemoveUneededCalls(call->path)) + PathDiagnosticCallPiece *NewCallWithLoc = + call->getLocation().asLocation().isValid() + ? call : CallWithLoc; + + if (!RemoveUneededCalls(call->path, R, NewCallWithLoc)) continue; + + if (NewCallWithLoc == CallWithLoc && CallWithLoc) { + call->callEnter = CallWithLoc->callEnter; + } + containsSomethingInteresting = true; break; } case PathDiagnosticPiece::Macro: { PathDiagnosticMacroPiece *macro = cast<PathDiagnosticMacroPiece>(piece); - if (!RemoveUneededCalls(macro->subPieces)) + if (!RemoveUneededCalls(macro->subPieces, R)) continue; containsSomethingInteresting = true; break; } case PathDiagnosticPiece::Event: { PathDiagnosticEventPiece *event = cast<PathDiagnosticEventPiece>(piece); + // We never throw away an event, but we do throw it away wholesale // as part of a path if we throw the entire path away. - if (event->isPrunable()) - continue; - containsSomethingInteresting = true; + containsSomethingInteresting |= !event->isPrunable(); break; } case PathDiagnosticPiece::ControlFlow: @@ -382,6 +473,35 @@ PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) { } //===----------------------------------------------------------------------===// +// "Visitors only" path diagnostic generation algorithm. +//===----------------------------------------------------------------------===// +static bool GenerateVisitorsOnlyPathDiagnostic(PathDiagnostic &PD, + PathDiagnosticBuilder &PDB, + const ExplodedNode *N, + ArrayRef<BugReporterVisitor *> visitors) { + // All path generation skips the very first node (the error node). + // This is because there is special handling for the end-of-path note. + N = N->getFirstPred(); + if (!N) + return true; + + BugReport *R = PDB.getBugReport(); + while (const ExplodedNode *Pred = N->getFirstPred()) { + for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(), + E = visitors.end(); + I != E; ++I) { + // Visit all the node pairs, but throw the path pieces away. + PathDiagnosticPiece *Piece = (*I)->VisitNode(N, Pred, PDB, *R); + delete Piece; + } + + N = Pred; + } + + return R->isValid(); +} + +//===----------------------------------------------------------------------===// // "Minimal" path diagnostic generation algorithm. //===----------------------------------------------------------------------===// typedef std::pair<PathDiagnosticCallPiece*, const ExplodedNode*> StackDiagPair; @@ -412,7 +532,7 @@ static void updateStackPiecesWithMessage(PathDiagnosticPiece *P, static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM); -static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, +static bool GenerateMinimalPathDiagnostic(PathDiagnostic& PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, ArrayRef<BugReporterVisitor *> visitors) { @@ -430,55 +550,60 @@ static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, NextNode = GetPredecessorNode(N); ProgramPoint P = N->getLocation(); - - if (const CallExitEnd *CE = dyn_cast<CallExitEnd>(&P)) { - PathDiagnosticCallPiece *C = - PathDiagnosticCallPiece::construct(N, *CE, SMgr); - PD.getActivePath().push_front(C); - PD.pushActivePath(&C->path); - CallStack.push_back(StackDiagPair(C, N)); - continue; - } - - if (const CallEnter *CE = dyn_cast<CallEnter>(&P)) { - // Flush all locations, and pop the active path. - bool VisitedEntireCall = PD.isWithinCall(); - PD.popActivePath(); - - // Either we just added a bunch of stuff to the top-level path, or - // we have a previous CallExitEnd. If the former, it means that the - // path terminated within a function call. We must then take the - // current contents of the active path and place it within - // a new PathDiagnosticCallPiece. - PathDiagnosticCallPiece *C; - if (VisitedEntireCall) { - C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front()); - } else { - const Decl *Caller = CE->getLocationContext()->getDecl(); - C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); + + do { + if (const CallExitEnd *CE = dyn_cast<CallExitEnd>(&P)) { + PathDiagnosticCallPiece *C = + PathDiagnosticCallPiece::construct(N, *CE, SMgr); + GRBugReporter& BR = PDB.getBugReporter(); + BR.addCallPieceLocationContextPair(C, CE->getCalleeContext()); + PD.getActivePath().push_front(C); + PD.pushActivePath(&C->path); + CallStack.push_back(StackDiagPair(C, N)); + break; } - C->setCallee(*CE, SMgr); - if (!CallStack.empty()) { - assert(CallStack.back().first == C); - CallStack.pop_back(); + if (const CallEnter *CE = dyn_cast<CallEnter>(&P)) { + // Flush all locations, and pop the active path. + bool VisitedEntireCall = PD.isWithinCall(); + PD.popActivePath(); + + // Either we just added a bunch of stuff to the top-level path, or + // we have a previous CallExitEnd. If the former, it means that the + // path terminated within a function call. We must then take the + // current contents of the active path and place it within + // a new PathDiagnosticCallPiece. + PathDiagnosticCallPiece *C; + if (VisitedEntireCall) { + C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front()); + } else { + const Decl *Caller = CE->getLocationContext()->getDecl(); + C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); + GRBugReporter& BR = PDB.getBugReporter(); + BR.addCallPieceLocationContextPair(C, CE->getCalleeContext()); + } + + C->setCallee(*CE, SMgr); + if (!CallStack.empty()) { + assert(CallStack.back().first == C); + CallStack.pop_back(); + } + break; } - continue; - } - if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) { - const CFGBlock *Src = BE->getSrc(); - const CFGBlock *Dst = BE->getDst(); - const Stmt *T = Src->getTerminator(); + if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) { + const CFGBlock *Src = BE->getSrc(); + const CFGBlock *Dst = BE->getDst(); + const Stmt *T = Src->getTerminator(); - if (!T) - continue; + if (!T) + break; - PathDiagnosticLocation Start = - PathDiagnosticLocation::createBegin(T, SMgr, - N->getLocationContext()); + PathDiagnosticLocation Start = + PathDiagnosticLocation::createBegin(T, SMgr, + N->getLocationContext()); - switch (T->getStmtClass()) { + switch (T->getStmtClass()) { default: break; @@ -487,16 +612,16 @@ static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, const Stmt *S = GetNextStmt(N); if (!S) - continue; + break; std::string sbuf; llvm::raw_string_ostream os(sbuf); const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S); os << "Control jumps to line " - << End.asLocation().getExpansionLineNumber(); - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - os.str())); + << End.asLocation().getExpansionLineNumber(); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, os.str())); break; } @@ -509,52 +634,52 @@ static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, PathDiagnosticLocation End(S, SMgr, LC); switch (S->getStmtClass()) { - default: - os << "No cases match in the switch statement. " - "Control jumps to line " - << End.asLocation().getExpansionLineNumber(); - break; - case Stmt::DefaultStmtClass: - os << "Control jumps to the 'default' case at line " - << End.asLocation().getExpansionLineNumber(); - break; - - case Stmt::CaseStmtClass: { - os << "Control jumps to 'case "; - const CaseStmt *Case = cast<CaseStmt>(S); - const Expr *LHS = Case->getLHS()->IgnoreParenCasts(); - - // Determine if it is an enum. - bool GetRawInt = true; - - if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) { - // FIXME: Maybe this should be an assertion. Are there cases - // were it is not an EnumConstantDecl? - const EnumConstantDecl *D = + default: + os << "No cases match in the switch statement. " + "Control jumps to line " + << End.asLocation().getExpansionLineNumber(); + break; + case Stmt::DefaultStmtClass: + os << "Control jumps to the 'default' case at line " + << End.asLocation().getExpansionLineNumber(); + break; + + case Stmt::CaseStmtClass: { + os << "Control jumps to 'case "; + const CaseStmt *Case = cast<CaseStmt>(S); + const Expr *LHS = Case->getLHS()->IgnoreParenCasts(); + + // Determine if it is an enum. + bool GetRawInt = true; + + if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) { + // FIXME: Maybe this should be an assertion. Are there cases + // were it is not an EnumConstantDecl? + const EnumConstantDecl *D = dyn_cast<EnumConstantDecl>(DR->getDecl()); - if (D) { - GetRawInt = false; - os << *D; - } + if (D) { + GetRawInt = false; + os << *D; } + } - if (GetRawInt) - os << LHS->EvaluateKnownConstInt(PDB.getASTContext()); + if (GetRawInt) + os << LHS->EvaluateKnownConstInt(PDB.getASTContext()); - os << ":' at line " - << End.asLocation().getExpansionLineNumber(); - break; - } + os << ":' at line " + << End.asLocation().getExpansionLineNumber(); + break; } - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - os.str())); + } + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, os.str())); } else { os << "'Default' branch taken. "; const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N); - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - os.str())); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, os.str())); } break; @@ -565,12 +690,12 @@ static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, std::string sbuf; llvm::raw_string_ostream os(sbuf); PathDiagnosticLocation End = PDB.ExecutionContinues(os, N); - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - os.str())); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, os.str())); break; } - // Determine control-flow for ternary '?'. + // Determine control-flow for ternary '?'. case Stmt::BinaryConditionalOperatorClass: case Stmt::ConditionalOperatorClass: { std::string sbuf; @@ -587,12 +712,12 @@ static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, if (const Stmt *S = End.asStmt()) End = PDB.getEnclosingStmtLocation(S); - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - os.str())); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, os.str())); break; } - // Determine control-flow for short-circuited '&&' and '||'. + // Determine control-flow for short-circuited '&&' and '||'. case Stmt::BinaryOperatorClass: { if (!PDB.supportsLogicalOpControlFlow()) break; @@ -609,16 +734,16 @@ static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, os << "false"; PathDiagnosticLocation End(B->getLHS(), SMgr, LC); PathDiagnosticLocation Start = - PathDiagnosticLocation::createOperatorLoc(B, SMgr); - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - os.str())); + PathDiagnosticLocation::createOperatorLoc(B, SMgr); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, os.str())); } else { os << "true"; PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); PathDiagnosticLocation End = PDB.ExecutionContinues(N); - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - os.str())); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, os.str())); } } else { @@ -629,16 +754,16 @@ static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, os << "false"; PathDiagnosticLocation Start(B->getLHS(), SMgr, LC); PathDiagnosticLocation End = PDB.ExecutionContinues(N); - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - os.str())); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, os.str())); } else { os << "true"; PathDiagnosticLocation End(B->getLHS(), SMgr, LC); PathDiagnosticLocation Start = - PathDiagnosticLocation::createOperatorLoc(B, SMgr); - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - os.str())); + PathDiagnosticLocation::createOperatorLoc(B, SMgr); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, os.str())); } } @@ -656,8 +781,8 @@ static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, if (const Stmt *S = End.asStmt()) End = PDB.getEnclosingStmtLocation(S); - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - os.str())); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, os.str())); } else { PathDiagnosticLocation End = PDB.ExecutionContinues(N); @@ -665,8 +790,8 @@ static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, if (const Stmt *S = End.asStmt()) End = PDB.getEnclosingStmtLocation(S); - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - "Loop condition is false. Exiting loop")); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, "Loop condition is false. Exiting loop")); } break; @@ -683,16 +808,16 @@ static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, if (const Stmt *S = End.asStmt()) End = PDB.getEnclosingStmtLocation(S); - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - os.str())); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, os.str())); } else { PathDiagnosticLocation End = PDB.ExecutionContinues(N); if (const Stmt *S = End.asStmt()) End = PDB.getEnclosingStmtLocation(S); - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - "Loop condition is true. Entering loop body")); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, "Loop condition is true. Entering loop body")); } break; @@ -705,16 +830,17 @@ static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, End = PDB.getEnclosingStmtLocation(S); if (*(Src->succ_begin()+1) == Dst) - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - "Taking false branch")); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, "Taking false branch")); else - PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(Start, End, - "Taking true branch")); + PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece( + Start, End, "Taking true branch")); break; } + } } - } + } while(0); if (NextNode) { // Add diagnostic pieces from custom visitors. @@ -730,9 +856,13 @@ static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, } } + if (!PDB.getBugReport()->isValid()) + return false; + // After constructing the full PathDiagnostic, do a pass over it to compact // PathDiagnosticPieces that occur within a macro. CompactPathDiagnostic(PD.getMutablePieces(), PDB.getSourceManager()); + return true; } //===----------------------------------------------------------------------===// @@ -944,6 +1074,11 @@ void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) { const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc); const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc); + if (PrevLocClean.asLocation().isInvalid()) { + PrevLoc = NewLoc; + return; + } + if (NewLocClean.asLocation() == PrevLocClean.asLocation()) return; @@ -1133,7 +1268,7 @@ static void reversePropagateInterestingSymbols(BugReport &R, } } -static void GenerateExtensivePathDiagnostic(PathDiagnostic& PD, +static bool GenerateExtensivePathDiagnostic(PathDiagnostic& PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, ArrayRef<BugReporterVisitor *> visitors) { @@ -1166,6 +1301,8 @@ static void GenerateExtensivePathDiagnostic(PathDiagnostic& PD, PathDiagnosticCallPiece *C = PathDiagnosticCallPiece::construct(N, *CE, SM); + GRBugReporter& BR = PDB.getBugReporter(); + BR.addCallPieceLocationContextPair(C, CE->getCalleeContext()); EB.addEdge(C->callReturn, true); EB.flushLocations(); @@ -1202,6 +1339,8 @@ static void GenerateExtensivePathDiagnostic(PathDiagnostic& PD, } else { const Decl *Caller = CE->getLocationContext()->getDecl(); C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller); + GRBugReporter& BR = PDB.getBugReporter(); + BR.addCallPieceLocationContextPair(C, CE->getCalleeContext()); } C->setCallee(*CE, SM); @@ -1234,20 +1373,15 @@ static void GenerateExtensivePathDiagnostic(PathDiagnostic& PD, } } - const CFGBlock &Blk = *BE->getSrc(); - const Stmt *Term = Blk.getTerminator(); - // Are we jumping to the head of a loop? Add a special diagnostic. - if (const Stmt *Loop = BE->getDst()->getLoopTarget()) { + if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { PathDiagnosticLocation L(Loop, SM, PDB.LC); const CompoundStmt *CS = NULL; - if (!Term) { - if (const ForStmt *FS = dyn_cast<ForStmt>(Loop)) - CS = dyn_cast<CompoundStmt>(FS->getBody()); - else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop)) - CS = dyn_cast<CompoundStmt>(WS->getBody()); - } + if (const ForStmt *FS = dyn_cast<ForStmt>(Loop)) + CS = dyn_cast<CompoundStmt>(FS->getBody()); + else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop)) + CS = dyn_cast<CompoundStmt>(WS->getBody()); PathDiagnosticEventPiece *p = new PathDiagnosticEventPiece(L, @@ -1263,15 +1397,16 @@ static void GenerateExtensivePathDiagnostic(PathDiagnostic& PD, EB.addEdge(BL); } } - - if (Term) + + if (const Stmt *Term = BE->getSrc()->getTerminator()) EB.addContext(Term); break; } if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) { - if (const CFGStmt *S = BE->getFirstElement().getAs<CFGStmt>()) { + CFGElement First = BE->getFirstElement(); + if (const CFGStmt *S = First.getAs<CFGStmt>()) { const Stmt *stmt = S->getStmt(); if (IsControlFlowExpr(stmt)) { // Add the proper context for '&&', '||', and '?'. @@ -1306,6 +1441,8 @@ static void GenerateExtensivePathDiagnostic(PathDiagnostic& PD, } } } + + return PDB.getBugReport()->isValid(); } //===----------------------------------------------------------------------===// @@ -1414,6 +1551,12 @@ void BugReport::markInteresting(SVal V) { markInteresting(V.getAsSymbol()); } +void BugReport::markInteresting(const LocationContext *LC) { + if (!LC) + return; + InterestingLocationContexts.insert(LC); +} + bool BugReport::isInteresting(SVal V) { return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol()); } @@ -1438,6 +1581,12 @@ bool BugReport::isInteresting(const MemRegion *R) { return false; } +bool BugReport::isInteresting(const LocationContext *LC) { + if (!LC) + return false; + return InterestingLocationContexts.count(LC); +} + void BugReport::lazyInitializeInterestingSets() { if (interestingSymbols.empty()) { interestingSymbols.push_back(new Symbols()); @@ -1823,17 +1972,27 @@ static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) { path.push_back(*I); } -void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, +bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD, PathDiagnosticConsumer &PC, ArrayRef<BugReport *> &bugReports) { - assert(!bugReports.empty()); + + bool HasValid = false; SmallVector<const ExplodedNode *, 10> errorNodes; for (ArrayRef<BugReport*>::iterator I = bugReports.begin(), E = bugReports.end(); I != E; ++I) { + if ((*I)->isValid()) { + HasValid = true; errorNodes.push_back((*I)->getErrorNode()); + } else { + errorNodes.push_back(0); + } } + // If all the reports have been marked invalid, we're done. + if (!HasValid) + return false; + // Construct a new graph that contains only a single path from the error // node to a root. const std::pair<std::pair<ExplodedGraph*, NodeBackMap*>, @@ -1844,6 +2003,7 @@ void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, assert(GPair.second.second < bugReports.size()); BugReport *R = bugReports[GPair.second.second]; assert(R && "No original report found for sliced graph."); + assert(R->isValid() && "Report selected from trimmed graph marked invalid."); OwningPtr<ExplodedGraph> ReportGraph(GPair.first.first); OwningPtr<NodeBackMap> BackMap(GPair.first.second); @@ -1870,36 +2030,53 @@ void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, visitors.push_back((*I)->clone()); // Clear out the active path from any previous work. - PD.getActivePath().clear(); + PD.resetPath(); originalReportConfigToken = R->getConfigurationChangeToken(); // Generate the very last diagnostic piece - the piece is visible before // the trace is expanded. - PathDiagnosticPiece *LastPiece = 0; - for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end(); - I != E; ++I) { - if (PathDiagnosticPiece *Piece = (*I)->getEndPath(PDB, N, *R)) { - assert (!LastPiece && - "There can only be one final piece in a diagnostic."); - LastPiece = Piece; + if (PDB.getGenerationScheme() != PathDiagnosticConsumer::None) { + PathDiagnosticPiece *LastPiece = 0; + for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end(); + I != E; ++I) { + if (PathDiagnosticPiece *Piece = (*I)->getEndPath(PDB, N, *R)) { + assert (!LastPiece && + "There can only be one final piece in a diagnostic."); + LastPiece = Piece; + } } + if (!LastPiece) + LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R); + if (LastPiece) + PD.setEndOfPath(LastPiece); + else + return false; } - if (!LastPiece) - LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R); - if (LastPiece) - PD.getActivePath().push_back(LastPiece); - else - return; switch (PDB.getGenerationScheme()) { case PathDiagnosticConsumer::Extensive: - GenerateExtensivePathDiagnostic(PD, PDB, N, visitors); + if (!GenerateExtensivePathDiagnostic(PD, PDB, N, visitors)) { + assert(!R->isValid() && "Failed on valid report"); + // Try again. We'll filter out the bad report when we trim the graph. + // FIXME: It would be more efficient to use the same intermediate + // trimmed graph, and just repeat the shortest-path search. + return generatePathDiagnostic(PD, PC, bugReports); + } break; case PathDiagnosticConsumer::Minimal: - GenerateMinimalPathDiagnostic(PD, PDB, N, visitors); + if (!GenerateMinimalPathDiagnostic(PD, PDB, N, visitors)) { + assert(!R->isValid() && "Failed on valid report"); + // Try again. We'll filter out the bad report when we trim the graph. + return generatePathDiagnostic(PD, PC, bugReports); + } break; case PathDiagnosticConsumer::None: - llvm_unreachable("PathDiagnosticConsumer::None should never appear here"); + if (!GenerateVisitorsOnlyPathDiagnostic(PD, PDB, N, visitors)) { + assert(!R->isValid() && "Failed on valid report"); + // Try again. We'll filter out the bad report when we trim the graph. + return generatePathDiagnostic(PD, PC, bugReports); + } + break; } // Clean up the visitors we used. @@ -1910,18 +2087,26 @@ void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, } while(finalReportConfigToken != originalReportConfigToken); // Finally, prune the diagnostic path of uninteresting stuff. - if (R->shouldPrunePath()) { - bool hasSomethingInteresting = RemoveUneededCalls(PD.getMutablePieces()); - assert(hasSomethingInteresting); - (void) hasSomethingInteresting; + if (!PD.path.empty()) { + // Remove messages that are basically the same. + removeRedundantMsgs(PD.getMutablePieces()); + + if (R->shouldPrunePath()) { + bool hasSomethingInteresting = RemoveUneededCalls(PD.getMutablePieces(), + R); + assert(hasSomethingInteresting); + (void) hasSomethingInteresting; + } } + + return true; } void BugReporter::Register(BugType *BT) { BugTypes = F.add(BugTypes, BT); } -void BugReporter::EmitReport(BugReport* R) { +void BugReporter::emitReport(BugReport* R) { // Compute the bug report's hash to determine its equivalence class. llvm::FoldingSetNodeID ID; R->Profile(ID); @@ -2078,17 +2263,17 @@ void BugReporter::FlushReport(BugReport *exampleReport, OwningPtr<PathDiagnostic> D(new PathDiagnostic(exampleReport->getDeclWithIssue(), exampleReport->getBugType().getName(), - PD.useVerboseDescription() - ? exampleReport->getDescription() - : exampleReport->getShortDescription(), + exampleReport->getDescription(), + exampleReport->getShortDescription(/*Fallback=*/false), BT.getCategory())); // Generate the full path diagnostic, using the generation scheme - // specified by the PathDiagnosticConsumer. - if (PD.getGenerationScheme() != PathDiagnosticConsumer::None) { - if (!bugReports.empty()) - GeneratePathDiagnostic(*D.get(), PD, bugReports); - } + // specified by the PathDiagnosticConsumer. Note that we have to generate + // path diagnostics even for consumers which do not support paths, because + // the BugReporterVisitors may mark this bug as a false positive. + if (!bugReports.empty()) + if (!generatePathDiagnostic(*D.get(), PD, bugReports)) + return; // If the path is empty, generate a single step path with the location // of the issue. @@ -2100,7 +2285,7 @@ void BugReporter::FlushReport(BugReport *exampleReport, llvm::tie(Beg, End) = exampleReport->getRanges(); for ( ; Beg != End; ++Beg) piece->addRange(*Beg); - D->getActivePath().push_back(piece); + D->setEndOfPath(piece); } // Get the meta data. @@ -2124,7 +2309,7 @@ void BugReporter::EmitBasicReport(const Decl *DeclWithIssue, BugReport *R = new BugReport(*BT, str, Loc); R->setDeclWithIssue(DeclWithIssue); for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg); - EmitReport(R); + emitReport(R); } BugType *BugReporter::getBugTypeForName(StringRef name, diff --git a/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp b/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp index e729587..328e8a6 100644 --- a/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp +++ b/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp @@ -17,10 +17,13 @@ #include "clang/AST/ExprObjC.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" #include "llvm/ADT/SmallString.h" +#include "llvm/ADT/StringExtras.h" using namespace clang; using namespace ento; @@ -29,10 +32,24 @@ using namespace ento; // Utility functions. //===----------------------------------------------------------------------===// +bool bugreporter::isDeclRefExprToReference(const Expr *E) { + if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E)) { + return DRE->getDecl()->getType()->isReferenceType(); + } + return false; +} + const Stmt *bugreporter::GetDerefExpr(const ExplodedNode *N) { // Pattern match for a few useful cases (do something smarter later): // a[0], p->f, *p - const Stmt *S = N->getLocationAs<PostStmt>()->getStmt(); + const PostStmt *Loc = N->getLocationAs<PostStmt>(); + if (!Loc) + return 0; + + const Expr *S = dyn_cast<Expr>(Loc->getStmt()); + if (!S) + return 0; + S = S->IgnoreParenCasts(); while (true) { if (const BinaryOperator *B = dyn_cast<BinaryOperator>(S)) { @@ -45,7 +62,12 @@ const Stmt *bugreporter::GetDerefExpr(const ExplodedNode *N) { return U->getSubExpr()->IgnoreParenCasts(); } else if (const MemberExpr *ME = dyn_cast<MemberExpr>(S)) { - return ME->getBase()->IgnoreParenCasts(); + if (ME->isArrow() || isDeclRefExprToReference(ME->getBase())) { + return ME->getBase()->IgnoreParenCasts(); + } + } + else if (const ObjCIvarRefExpr *IvarRef = dyn_cast<ObjCIvarRefExpr>(S)) { + return IvarRef->getBase()->IgnoreParenCasts(); } else if (const ArraySubscriptExpr *AE = dyn_cast<ArraySubscriptExpr>(S)) { return AE->getBase(); @@ -103,6 +125,228 @@ BugReporterVisitor::getDefaultEndPath(BugReporterContext &BRC, } +namespace { +/// Emits an extra note at the return statement of an interesting stack frame. +/// +/// The returned value is marked as an interesting value, and if it's null, +/// adds a visitor to track where it became null. +/// +/// This visitor is intended to be used when another visitor discovers that an +/// interesting value comes from an inlined function call. +class ReturnVisitor : public BugReporterVisitorImpl<ReturnVisitor> { + const StackFrameContext *StackFrame; + enum { + Initial, + MaybeSuppress, + Satisfied + } Mode; + +public: + ReturnVisitor(const StackFrameContext *Frame) + : StackFrame(Frame), Mode(Initial) {} + + static void *getTag() { + static int Tag = 0; + return static_cast<void *>(&Tag); + } + + virtual void Profile(llvm::FoldingSetNodeID &ID) const { + ID.AddPointer(ReturnVisitor::getTag()); + ID.AddPointer(StackFrame); + } + + /// Adds a ReturnVisitor if the given statement represents a call that was + /// inlined. + /// + /// This will search back through the ExplodedGraph, starting from the given + /// node, looking for when the given statement was processed. If it turns out + /// the statement is a call that was inlined, we add the visitor to the + /// bug report, so it can print a note later. + static void addVisitorIfNecessary(const ExplodedNode *Node, const Stmt *S, + BugReport &BR) { + if (!CallEvent::isCallStmt(S)) + return; + + // First, find when we processed the statement. + do { + if (const CallExitEnd *CEE = Node->getLocationAs<CallExitEnd>()) + if (CEE->getCalleeContext()->getCallSite() == S) + break; + if (const StmtPoint *SP = Node->getLocationAs<StmtPoint>()) + if (SP->getStmt() == S) + break; + + Node = Node->getFirstPred(); + } while (Node); + + // Next, step over any post-statement checks. + while (Node && isa<PostStmt>(Node->getLocation())) + Node = Node->getFirstPred(); + + // Finally, see if we inlined the call. + if (Node) { + if (const CallExitEnd *CEE = Node->getLocationAs<CallExitEnd>()) { + const StackFrameContext *CalleeContext = CEE->getCalleeContext(); + if (CalleeContext->getCallSite() == S) { + BR.markInteresting(CalleeContext); + BR.addVisitor(new ReturnVisitor(CalleeContext)); + } + } + } + } + + /// Returns true if any counter-suppression heuristics are enabled for + /// ReturnVisitor. + static bool hasCounterSuppression(AnalyzerOptions &Options) { + return Options.shouldAvoidSuppressingNullArgumentPaths(); + } + + PathDiagnosticPiece *visitNodeInitial(const ExplodedNode *N, + const ExplodedNode *PrevN, + BugReporterContext &BRC, + BugReport &BR) { + // Only print a message at the interesting return statement. + if (N->getLocationContext() != StackFrame) + return 0; + + const StmtPoint *SP = N->getLocationAs<StmtPoint>(); + if (!SP) + return 0; + + const ReturnStmt *Ret = dyn_cast<ReturnStmt>(SP->getStmt()); + if (!Ret) + return 0; + + // Okay, we're at the right return statement, but do we have the return + // value available? + ProgramStateRef State = N->getState(); + SVal V = State->getSVal(Ret, StackFrame); + if (V.isUnknownOrUndef()) + return 0; + + // Don't print any more notes after this one. + Mode = Satisfied; + + const Expr *RetE = Ret->getRetValue(); + assert(RetE && "Tracking a return value for a void function"); + RetE = RetE->IgnoreParenCasts(); + + // If we can't prove the return value is 0, just mark it interesting, and + // make sure to track it into any further inner functions. + if (State->assume(cast<DefinedSVal>(V), true)) { + BR.markInteresting(V); + ReturnVisitor::addVisitorIfNecessary(N, RetE, BR); + return 0; + } + + // If we're returning 0, we should track where that 0 came from. + bugreporter::trackNullOrUndefValue(N, RetE, BR); + + // Build an appropriate message based on the return value. + SmallString<64> Msg; + llvm::raw_svector_ostream Out(Msg); + + if (isa<Loc>(V)) { + // If we are pruning null-return paths as unlikely error paths, mark the + // report invalid. We still want to emit a path note, however, in case + // the report is resurrected as valid later on. + ExprEngine &Eng = BRC.getBugReporter().getEngine(); + AnalyzerOptions &Options = Eng.getAnalysisManager().options; + if (Options.shouldPruneNullReturnPaths()) { + if (hasCounterSuppression(Options)) + Mode = MaybeSuppress; + else + BR.markInvalid(ReturnVisitor::getTag(), StackFrame); + } + + if (RetE->getType()->isObjCObjectPointerType()) + Out << "Returning nil"; + else + Out << "Returning null pointer"; + } else { + Out << "Returning zero"; + } + + // FIXME: We should have a more generalized location printing mechanism. + if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(RetE)) + if (const DeclaratorDecl *DD = dyn_cast<DeclaratorDecl>(DR->getDecl())) + Out << " (loaded from '" << *DD << "')"; + + PathDiagnosticLocation L(Ret, BRC.getSourceManager(), StackFrame); + return new PathDiagnosticEventPiece(L, Out.str()); + } + + PathDiagnosticPiece *visitNodeMaybeSuppress(const ExplodedNode *N, + const ExplodedNode *PrevN, + BugReporterContext &BRC, + BugReport &BR) { + // Are we at the entry node for this call? + const CallEnter *CE = N->getLocationAs<CallEnter>(); + if (!CE) + return 0; + + if (CE->getCalleeContext() != StackFrame) + return 0; + + Mode = Satisfied; + + ExprEngine &Eng = BRC.getBugReporter().getEngine(); + AnalyzerOptions &Options = Eng.getAnalysisManager().options; + if (Options.shouldAvoidSuppressingNullArgumentPaths()) { + // Don't automatically suppress a report if one of the arguments is + // known to be a null pointer. Instead, start tracking /that/ null + // value back to its origin. + ProgramStateManager &StateMgr = BRC.getStateManager(); + CallEventManager &CallMgr = StateMgr.getCallEventManager(); + + ProgramStateRef State = N->getState(); + CallEventRef<> Call = CallMgr.getCaller(StackFrame, State); + for (unsigned I = 0, E = Call->getNumArgs(); I != E; ++I) { + SVal ArgV = Call->getArgSVal(I); + if (!isa<Loc>(ArgV)) + continue; + + const Expr *ArgE = Call->getArgExpr(I); + if (!ArgE) + continue; + + // Is it possible for this argument to be non-null? + if (State->assume(cast<Loc>(ArgV), true)) + continue; + + if (bugreporter::trackNullOrUndefValue(N, ArgE, BR, /*IsArg=*/true)) + return 0; + + // If we /can't/ track the null pointer, we should err on the side of + // false negatives, and continue towards marking this report invalid. + // (We will still look at the other arguments, though.) + } + } + + // There is no reason not to suppress this report; go ahead and do it. + BR.markInvalid(ReturnVisitor::getTag(), StackFrame); + return 0; + } + + PathDiagnosticPiece *VisitNode(const ExplodedNode *N, + const ExplodedNode *PrevN, + BugReporterContext &BRC, + BugReport &BR) { + switch (Mode) { + case Initial: + return visitNodeInitial(N, PrevN, BRC, BR); + case MaybeSuppress: + return visitNodeMaybeSuppress(N, PrevN, BRC, BR); + case Satisfied: + return 0; + } + + llvm_unreachable("Invalid visit mode!"); + } +}; +} // end anonymous namespace + + void FindLastStoreBRVisitor ::Profile(llvm::FoldingSetNodeID &ID) const { static int tag = 0; ID.AddPointer(&tag); @@ -110,59 +354,90 @@ void FindLastStoreBRVisitor ::Profile(llvm::FoldingSetNodeID &ID) const { ID.Add(V); } -PathDiagnosticPiece *FindLastStoreBRVisitor::VisitNode(const ExplodedNode *N, - const ExplodedNode *PrevN, - BugReporterContext &BRC, - BugReport &BR) { +PathDiagnosticPiece *FindLastStoreBRVisitor::VisitNode(const ExplodedNode *Succ, + const ExplodedNode *Pred, + BugReporterContext &BRC, + BugReport &BR) { if (satisfied) return NULL; - if (!StoreSite) { - // Make sure the region is actually bound to value V here. - // This is necessary because the region may not actually be live at the - // report's error node. - if (N->getState()->getSVal(R) != V) - return NULL; - - const ExplodedNode *Node = N, *Last = N; - - // Now look for the store of V. - for ( ; Node ; Node = Node->getFirstPred()) { - if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { - if (const PostStmt *P = Node->getLocationAs<PostStmt>()) - if (const DeclStmt *DS = P->getStmtAs<DeclStmt>()) - if (DS->getSingleDecl() == VR->getDecl()) { - // Record the last seen initialization point. - Last = Node; - break; - } + const ExplodedNode *StoreSite = 0; + const Expr *InitE = 0; + bool IsParam = false; + + // First see if we reached the declaration of the region. + if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { + if (const PostStmt *P = Pred->getLocationAs<PostStmt>()) { + if (const DeclStmt *DS = P->getStmtAs<DeclStmt>()) { + if (DS->getSingleDecl() == VR->getDecl()) { + StoreSite = Pred; + InitE = VR->getDecl()->getInit(); + } } - - // Does the region still bind to value V? If not, we are done - // looking for store sites. - if (Node->getState()->getSVal(R) != V) - break; - - Last = Node; } + } - if (!Node) { - satisfied = true; + // Otherwise, check that Succ has this binding and Pred does not, i.e. this is + // where the binding first occurred. + if (!StoreSite) { + if (Succ->getState()->getSVal(R) != V) + return NULL; + if (Pred->getState()->getSVal(R) == V) return NULL; - } - StoreSite = Last; + StoreSite = Succ; + + // If this is an assignment expression, we can track the value + // being assigned. + if (const PostStmt *P = Succ->getLocationAs<PostStmt>()) + if (const BinaryOperator *BO = P->getStmtAs<BinaryOperator>()) + if (BO->isAssignmentOp()) + InitE = BO->getRHS(); + + // If this is a call entry, the variable should be a parameter. + // FIXME: Handle CXXThisRegion as well. (This is not a priority because + // 'this' should never be NULL, but this visitor isn't just for NULL and + // UndefinedVal.) + if (const CallEnter *CE = Succ->getLocationAs<CallEnter>()) { + const VarRegion *VR = cast<VarRegion>(R); + const ParmVarDecl *Param = cast<ParmVarDecl>(VR->getDecl()); + + ProgramStateManager &StateMgr = BRC.getStateManager(); + CallEventManager &CallMgr = StateMgr.getCallEventManager(); + + CallEventRef<> Call = CallMgr.getCaller(CE->getCalleeContext(), + Succ->getState()); + InitE = Call->getArgExpr(Param->getFunctionScopeIndex()); + IsParam = true; + } } - if (StoreSite != N) + if (!StoreSite) return NULL; - satisfied = true; + + // If we have an expression that provided the value, try to track where it + // came from. + if (InitE) { + if (V.isUndef() || isa<loc::ConcreteInt>(V)) { + if (!IsParam) + InitE = InitE->IgnoreParenCasts(); + bugreporter::trackNullOrUndefValue(StoreSite, InitE, BR, IsParam); + } else { + ReturnVisitor::addVisitorIfNecessary(StoreSite, InitE->IgnoreParenCasts(), + BR); + } + } + + if (!R->canPrintPretty()) + return 0; + + // Okay, we've found the binding. Emit an appropriate message. SmallString<256> sbuf; llvm::raw_svector_ostream os(sbuf); - if (const PostStmt *PS = N->getLocationAs<PostStmt>()) { + if (const PostStmt *PS = StoreSite->getLocationAs<PostStmt>()) { if (const DeclStmt *DS = PS->getStmtAs<DeclStmt>()) { if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { @@ -201,6 +476,30 @@ PathDiagnosticPiece *FindLastStoreBRVisitor::VisitNode(const ExplodedNode *N, os << "initialized here"; } } + } else if (isa<CallEnter>(StoreSite->getLocation())) { + const ParmVarDecl *Param = cast<ParmVarDecl>(cast<VarRegion>(R)->getDecl()); + + os << "Passing "; + + if (isa<loc::ConcreteInt>(V)) { + if (Param->getType()->isObjCObjectPointerType()) + os << "nil object reference"; + else + os << "null pointer value"; + } else if (V.isUndef()) { + os << "uninitialized value"; + } else if (isa<nonloc::ConcreteInt>(V)) { + os << "the value " << cast<nonloc::ConcreteInt>(V).getValue(); + } else { + os << "value"; + } + + // Printed parameter indexes are 1-based, not 0-based. + unsigned Idx = Param->getFunctionScopeIndex() + 1; + os << " via " << Idx << llvm::getOrdinalSuffix(Idx) << " parameter '"; + + R->printPretty(os); + os << '\''; } if (os.str().empty()) { @@ -228,17 +527,19 @@ PathDiagnosticPiece *FindLastStoreBRVisitor::VisitNode(const ExplodedNode *N, else os << "Value assigned to "; - if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { - os << '\'' << *VR->getDecl() << '\''; - } - else - return NULL; + os << '\''; + R->printPretty(os); + os << '\''; } // Construct a new PathDiagnosticPiece. - ProgramPoint P = N->getLocation(); - PathDiagnosticLocation L = - PathDiagnosticLocation::create(P, BRC.getSourceManager()); + ProgramPoint P = StoreSite->getLocation(); + PathDiagnosticLocation L; + if (isa<CallEnter>(P)) + L = PathDiagnosticLocation(InitE, BRC.getSourceManager(), + P.getLocationContext()); + else + L = PathDiagnosticLocation::create(P, BRC.getSourceManager()); if (!L.isValid()) return NULL; return new PathDiagnosticEventPiece(L, os.str()); @@ -251,6 +552,12 @@ void TrackConstraintBRVisitor::Profile(llvm::FoldingSetNodeID &ID) const { ID.Add(Constraint); } +/// Return the tag associated with this visitor. This tag will be used +/// to make all PathDiagnosticPieces created by this visitor. +const char *TrackConstraintBRVisitor::getTag() { + return "TrackConstraintBRVisitor"; +} + PathDiagnosticPiece * TrackConstraintBRVisitor::VisitNode(const ExplodedNode *N, const ExplodedNode *PrevN, @@ -290,62 +597,97 @@ TrackConstraintBRVisitor::VisitNode(const ExplodedNode *N, PathDiagnosticLocation::create(P, BRC.getSourceManager()); if (!L.isValid()) return NULL; - return new PathDiagnosticEventPiece(L, os.str()); + + PathDiagnosticEventPiece *X = new PathDiagnosticEventPiece(L, os.str()); + X->setTag(getTag()); + return X; } return NULL; } -void bugreporter::addTrackNullOrUndefValueVisitor(const ExplodedNode *N, - const Stmt *S, - BugReport *report) { +bool bugreporter::trackNullOrUndefValue(const ExplodedNode *N, const Stmt *S, + BugReport &report, bool IsArg) { if (!S || !N) - return; + return false; - ProgramStateManager &StateMgr = N->getState()->getStateManager(); + if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S)) + S = OVE->getSourceExpr(); + + if (IsArg) { + assert(isa<CallEnter>(N->getLocation()) && "Tracking arg but not at call"); + } else { + // Walk through nodes until we get one that matches the statement exactly. + do { + const ProgramPoint &pp = N->getLocation(); + if (const PostStmt *ps = dyn_cast<PostStmt>(&pp)) { + if (ps->getStmt() == S) + break; + } else if (const CallExitEnd *CEE = dyn_cast<CallExitEnd>(&pp)) { + if (CEE->getCalleeContext()->getCallSite() == S) + break; + } + N = N->getFirstPred(); + } while (N); - // Walk through nodes until we get one that matches the statement - // exactly. - while (N) { - const ProgramPoint &pp = N->getLocation(); - if (const PostStmt *ps = dyn_cast<PostStmt>(&pp)) { - if (ps->getStmt() == S) - break; - } - N = N->getFirstPred(); + if (!N) + return false; } - - if (!N) - return; ProgramStateRef state = N->getState(); - // Walk through lvalue-to-rvalue conversions. - const Expr *Ex = dyn_cast<Expr>(S); - if (Ex) { + // See if the expression we're interested refers to a variable. + // If so, we can track both its contents and constraints on its value. + if (const Expr *Ex = dyn_cast<Expr>(S)) { + // Strip off parens and casts. Note that this will never have issues with + // C++ user-defined implicit conversions, because those have a constructor + // or function call inside. Ex = Ex->IgnoreParenCasts(); if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) { + // FIXME: Right now we only track VarDecls because it's non-trivial to + // get a MemRegion for any other DeclRefExprs. <rdar://problem/12114812> if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { - const VarRegion *R = - StateMgr.getRegionManager().getVarRegion(VD, N->getLocationContext()); + ProgramStateManager &StateMgr = state->getStateManager(); + MemRegionManager &MRMgr = StateMgr.getRegionManager(); + const VarRegion *R = MRMgr.getVarRegion(VD, N->getLocationContext()); - // What did we load? + // Mark both the variable region and its contents as interesting. SVal V = state->getRawSVal(loc::MemRegionVal(R)); - report->markInteresting(R); - report->markInteresting(V); + // If the value matches the default for the variable region, that + // might mean that it's been cleared out of the state. Fall back to + // the full argument expression (with casts and such intact). + if (IsArg) { + bool UseArgValue = V.isUnknownOrUndef() || V.isZeroConstant(); + if (!UseArgValue) { + const SymbolRegionValue *SRV = + dyn_cast_or_null<SymbolRegionValue>(V.getAsLocSymbol()); + if (SRV) + UseArgValue = (SRV->getRegion() == R); + } + if (UseArgValue) + V = state->getSValAsScalarOrLoc(S, N->getLocationContext()); + } + + report.markInteresting(R); + report.markInteresting(V); + report.addVisitor(new UndefOrNullArgVisitor(R)); + + // If the contents are symbolic, find out when they became null. if (V.getAsLocSymbol()) { BugReporterVisitor *ConstraintTracker - = new TrackConstraintBRVisitor(cast<loc::MemRegionVal>(V), false); - report->addVisitor(ConstraintTracker); + = new TrackConstraintBRVisitor(cast<DefinedSVal>(V), false); + report.addVisitor(ConstraintTracker); } - report->addVisitor(new FindLastStoreBRVisitor(V, R)); - return; + report.addVisitor(new FindLastStoreBRVisitor(V, R)); + return true; } } } + // If the expression does NOT refer to a variable, we can still track + // constraints on its contents. SVal V = state->getSValAsScalarOrLoc(S, N->getLocationContext()); // Uncomment this to find cases where we aren't properly getting the @@ -354,17 +696,27 @@ void bugreporter::addTrackNullOrUndefValueVisitor(const ExplodedNode *N, // Is it a symbolic value? if (loc::MemRegionVal *L = dyn_cast<loc::MemRegionVal>(&V)) { - const SubRegion *R = cast<SubRegion>(L->getRegion()); - while (R && !isa<SymbolicRegion>(R)) { - R = dyn_cast<SubRegion>(R->getSuperRegion()); - } + // At this point we are dealing with the region's LValue. + // However, if the rvalue is a symbolic region, we should track it as well. + SVal RVal = state->getSVal(L->getRegion()); + const MemRegion *RegionRVal = RVal.getAsRegion(); + report.addVisitor(new UndefOrNullArgVisitor(L->getRegion())); + - if (R) { - report->markInteresting(R); - report->addVisitor(new TrackConstraintBRVisitor(loc::MemRegionVal(R), - false)); + if (RegionRVal && isa<SymbolicRegion>(RegionRVal)) { + report.markInteresting(RegionRVal); + report.addVisitor(new TrackConstraintBRVisitor( + loc::MemRegionVal(RegionRVal), false)); } + } else { + // Otherwise, if the value came from an inlined function call, + // we should at least make sure that function isn't pruned in our output. + if (const Expr *E = dyn_cast<Expr>(S)) + S = E->IgnoreParenCasts(); + ReturnVisitor::addVisitorIfNecessary(N, S, report); } + + return true; } BugReporterVisitor * @@ -406,7 +758,7 @@ PathDiagnosticPiece *NilReceiverBRVisitor::VisitNode(const ExplodedNode *N, // The receiver was nil, and hence the method was skipped. // Register a BugReporterVisitor to issue a message telling us how // the receiver was null. - bugreporter::addTrackNullOrUndefValueVisitor(N, Receiver, &BR); + bugreporter::trackNullOrUndefValue(N, Receiver, BR); // Issue a message saying that the method was skipped. PathDiagnosticLocation L(Receiver, BRC.getSourceManager(), N->getLocationContext()); @@ -452,14 +804,23 @@ void FindLastStoreBRVisitor::registerStatementVarDecls(BugReport &BR, //===----------------------------------------------------------------------===// // Visitor that tries to report interesting diagnostics from conditions. //===----------------------------------------------------------------------===// + +/// Return the tag associated with this visitor. This tag will be used +/// to make all PathDiagnosticPieces created by this visitor. +const char *ConditionBRVisitor::getTag() { + return "ConditionBRVisitor"; +} + PathDiagnosticPiece *ConditionBRVisitor::VisitNode(const ExplodedNode *N, const ExplodedNode *Prev, BugReporterContext &BRC, BugReport &BR) { PathDiagnosticPiece *piece = VisitNodeImpl(N, Prev, BRC, BR); - if (PathDiagnosticEventPiece *ev = - dyn_cast_or_null<PathDiagnosticEventPiece>(piece)) - ev->setPrunable(true, /* override */ false); + if (piece) { + piece->setTag(getTag()); + if (PathDiagnosticEventPiece *ev=dyn_cast<PathDiagnosticEventPiece>(piece)) + ev->setPrunable(true, /* override */ false); + } return piece; } @@ -468,8 +829,7 @@ PathDiagnosticPiece *ConditionBRVisitor::VisitNodeImpl(const ExplodedNode *N, BugReporterContext &BRC, BugReport &BR) { - const ProgramPoint &progPoint = N->getLocation(); - + ProgramPoint progPoint = N->getLocation(); ProgramStateRef CurrentState = N->getState(); ProgramStateRef PrevState = Prev->getState(); @@ -494,7 +854,7 @@ PathDiagnosticPiece *ConditionBRVisitor::VisitNodeImpl(const ExplodedNode *N, // violation. const std::pair<const ProgramPointTag *, const ProgramPointTag *> &tags = cast<GRBugReporter>(BRC.getBugReporter()). - getEngine().getEagerlyAssumeTags(); + getEngine().geteagerlyAssumeBinOpBifurcationTags(); const ProgramPointTag *tag = PS->getTag(); if (tag == tags.first) @@ -533,8 +893,7 @@ ConditionBRVisitor::VisitTerminator(const Stmt *Term, assert(Cond); assert(srcBlk->succ_size() == 2); const bool tookTrue = *(srcBlk->succ_begin()) == dstBlk; - return VisitTrueTest(Cond->IgnoreParenNoopCasts(BRC.getASTContext()), - tookTrue, BRC, R, N); + return VisitTrueTest(Cond, tookTrue, BRC, R, N); } PathDiagnosticPiece * @@ -547,7 +906,7 @@ ConditionBRVisitor::VisitTrueTest(const Expr *Cond, const Expr *Ex = Cond; while (true) { - Ex = Ex->IgnoreParens(); + Ex = Ex->IgnoreParenCasts(); switch (Ex->getStmtClass()) { default: return 0; @@ -561,7 +920,7 @@ ConditionBRVisitor::VisitTrueTest(const Expr *Cond, const UnaryOperator *UO = cast<UnaryOperator>(Ex); if (UO->getOpcode() == UO_LNot) { tookTrue = !tookTrue; - Ex = UO->getSubExpr()->IgnoreParenNoopCasts(BRC.getASTContext()); + Ex = UO->getSubExpr(); continue; } return 0; @@ -802,3 +1161,54 @@ ConditionBRVisitor::VisitTrueTest(const Expr *Cond, return event; } +PathDiagnosticPiece * +UndefOrNullArgVisitor::VisitNode(const ExplodedNode *N, + const ExplodedNode *PrevN, + BugReporterContext &BRC, + BugReport &BR) { + + ProgramStateRef State = N->getState(); + ProgramPoint ProgLoc = N->getLocation(); + + // We are only interested in visiting CallEnter nodes. + CallEnter *CEnter = dyn_cast<CallEnter>(&ProgLoc); + if (!CEnter) + return 0; + + // Check if one of the arguments is the region the visitor is tracking. + CallEventManager &CEMgr = BRC.getStateManager().getCallEventManager(); + CallEventRef<> Call = CEMgr.getCaller(CEnter->getCalleeContext(), State); + unsigned Idx = 0; + for (CallEvent::param_iterator I = Call->param_begin(), + E = Call->param_end(); I != E; ++I, ++Idx) { + const MemRegion *ArgReg = Call->getArgSVal(Idx).getAsRegion(); + + // Are we tracking the argument or its subregion? + if ( !ArgReg || (ArgReg != R && !R->isSubRegionOf(ArgReg->StripCasts()))) + continue; + + // Check the function parameter type. + const ParmVarDecl *ParamDecl = *I; + assert(ParamDecl && "Formal parameter has no decl?"); + QualType T = ParamDecl->getType(); + + if (!(T->isAnyPointerType() || T->isReferenceType())) { + // Function can only change the value passed in by address. + continue; + } + + // If it is a const pointer value, the function does not intend to + // change the value. + if (T->getPointeeType().isConstQualified()) + continue; + + // Mark the call site (LocationContext) as interesting if the value of the + // argument is undefined or '0'/'NULL'. + SVal BoundVal = State->getSVal(R); + if (BoundVal.isUndef() || BoundVal.isZeroConstant()) { + BR.markInteresting(CEnter->getCalleeContext()); + return 0; + } + } + return 0; +} diff --git a/lib/StaticAnalyzer/Core/CMakeLists.txt b/lib/StaticAnalyzer/Core/CMakeLists.txt index b16b233d..91f15b3 100644 --- a/lib/StaticAnalyzer/Core/CMakeLists.txt +++ b/lib/StaticAnalyzer/Core/CMakeLists.txt @@ -1,9 +1,9 @@ set(LLVM_LINK_COMPONENTS support) add_clang_library(clangStaticAnalyzerCore - AnalysisManager.cpp APSIntType.cpp - BasicConstraintManager.cpp + AnalysisManager.cpp + AnalyzerOptions.cpp BasicValueFactory.cpp BlockCounter.cpp BugReporter.cpp @@ -14,6 +14,7 @@ add_clang_library(clangStaticAnalyzerCore CheckerHelpers.cpp CheckerManager.cpp CheckerRegistry.cpp + ConstraintManager.cpp CoreEngine.cpp Environment.cpp ExplodedGraph.cpp @@ -54,5 +55,5 @@ target_link_libraries(clangStaticAnalyzerCore clangLex clangAST clangFrontend - clangRewrite + clangRewriteCore ) diff --git a/lib/StaticAnalyzer/Core/CallEvent.cpp b/lib/StaticAnalyzer/Core/CallEvent.cpp index 5345bd5..c5cb317 100644 --- a/lib/StaticAnalyzer/Core/CallEvent.cpp +++ b/lib/StaticAnalyzer/Core/CallEvent.cpp @@ -14,6 +14,7 @@ //===----------------------------------------------------------------------===// #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" #include "clang/Analysis/ProgramPoint.h" #include "clang/AST/ParentMap.h" #include "llvm/ADT/SmallSet.h" @@ -23,10 +24,26 @@ using namespace clang; using namespace ento; QualType CallEvent::getResultType() const { - QualType ResultTy = getDeclaredResultType(); + const Expr *E = getOriginExpr(); + assert(E && "Calls without origin expressions do not have results"); + QualType ResultTy = E->getType(); - if (ResultTy.isNull()) - ResultTy = getOriginExpr()->getType(); + ASTContext &Ctx = getState()->getStateManager().getContext(); + + // A function that returns a reference to 'int' will have a result type + // of simply 'int'. Check the origin expr's value kind to recover the + // proper type. + switch (E->getValueKind()) { + case VK_LValue: + ResultTy = Ctx.getLValueReferenceType(ResultTy); + break; + case VK_XValue: + ResultTy = Ctx.getRValueReferenceType(ResultTy); + break; + case VK_RValue: + // No adjustment is necessary. + break; + } return ResultTy; } @@ -45,7 +62,7 @@ static bool isCallbackArg(SVal V, QualType T) { // Check if a callback is passed inside a struct (for both, struct passed by // reference and by value). Dig just one level into the struct for now. - if (isa<PointerType>(T) || isa<ReferenceType>(T)) + if (T->isAnyPointerType() || T->isReferenceType()) T = T->getPointeeType(); if (const RecordType *RT = T->getAsStructureType()) { @@ -83,6 +100,14 @@ bool CallEvent::hasNonZeroCallbackArg() const { return false; } +bool CallEvent::isGlobalCFunction(StringRef FunctionName) const { + const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(getDecl()); + if (!FD) + return false; + + return CheckerContext::isCLibraryFunction(FD, FunctionName); +} + /// \brief Returns true if a type is a pointer-to-const or reference-to-const /// with no further indirection. static bool isPointerToConst(QualType Ty) { @@ -207,6 +232,13 @@ SourceRange CallEvent::getArgSourceRange(unsigned Index) const { return ArgE->getSourceRange(); } +SVal CallEvent::getReturnValue() const { + const Expr *E = getOriginExpr(); + if (!E) + return UndefinedVal(); + return getSVal(E); +} + void CallEvent::dump() const { dump(llvm::errs()); } @@ -230,10 +262,20 @@ void CallEvent::dump(raw_ostream &Out) const { } -bool CallEvent::mayBeInlined(const Stmt *S) { - // FIXME: Kill this. +bool CallEvent::isCallStmt(const Stmt *S) { return isa<CallExpr>(S) || isa<ObjCMessageExpr>(S) - || isa<CXXConstructExpr>(S); + || isa<CXXConstructExpr>(S) + || isa<CXXNewExpr>(S); +} + +/// \brief Returns the result type, adjusted for references. +QualType CallEvent::getDeclaredResultType(const Decl *D) { + assert(D); + if (const FunctionDecl* FD = dyn_cast<FunctionDecl>(D)) + return FD->getResultType(); + else if (const ObjCMethodDecl* MD = dyn_cast<ObjCMethodDecl>(D)) + return MD->getResultType(); + return QualType(); } static void addParameterValuesToBindings(const StackFrameContext *CalleeCtx, @@ -285,14 +327,6 @@ void AnyFunctionCall::getInitialStackFrameContents( D->param_begin(), D->param_end()); } -QualType AnyFunctionCall::getDeclaredResultType() const { - const FunctionDecl *D = getDecl(); - if (!D) - return QualType(); - - return D->getResultType(); -} - bool AnyFunctionCall::argumentsMayEscape() const { if (hasNonZeroCallbackArg()) return true; @@ -303,7 +337,7 @@ bool AnyFunctionCall::argumentsMayEscape() const { const IdentifierInfo *II = D->getIdentifier(); if (!II) - return true; + return false; // This set of "escaping" APIs is @@ -376,6 +410,17 @@ void CXXInstanceCall::getExtraInvalidatedRegions(RegionList &Regions) const { Regions.push_back(R); } +SVal CXXInstanceCall::getCXXThisVal() const { + const Expr *Base = getCXXThisExpr(); + // FIXME: This doesn't handle an overloaded ->* operator. + if (!Base) + return UnknownVal(); + + SVal ThisVal = getSVal(Base); + assert(ThisVal.isUnknownOrUndef() || isa<Loc>(ThisVal)); + return ThisVal; +} + RuntimeDefinition CXXInstanceCall::getRuntimeDefinition() const { // Do we have a decl at all? @@ -400,13 +445,30 @@ RuntimeDefinition CXXInstanceCall::getRuntimeDefinition() const { // Is the type a C++ class? (This is mostly a defensive check.) QualType RegionType = DynType.getType()->getPointeeType(); + assert(!RegionType.isNull() && "DynamicTypeInfo should always be a pointer."); + const CXXRecordDecl *RD = RegionType->getAsCXXRecordDecl(); if (!RD || !RD->hasDefinition()) return RuntimeDefinition(); // Find the decl for this method in that class. const CXXMethodDecl *Result = MD->getCorrespondingMethodInClass(RD, true); - assert(Result && "At the very least the static decl should show up."); + if (!Result) { + // We might not even get the original statically-resolved method due to + // some particularly nasty casting (e.g. casts to sister classes). + // However, we should at least be able to search up and down our own class + // hierarchy, and some real bugs have been caught by checking this. + assert(!RD->isDerivedFrom(MD->getParent()) && "Couldn't find known method"); + + // FIXME: This is checking that our DynamicTypeInfo is at least as good as + // the static type. However, because we currently don't update + // DynamicTypeInfo when an object is cast, we can't actually be sure the + // DynamicTypeInfo is up to date. This assert should be re-enabled once + // this is fixed. <rdar://problem/12287087> + //assert(!MD->getParent()->isDerivedFrom(RD) && "Bad DynamicTypeInfo"); + + return RuntimeDefinition(); + } // Does the decl that we found have an implementation? const FunctionDecl *Definition; @@ -459,6 +521,18 @@ const Expr *CXXMemberCall::getCXXThisExpr() const { return getOriginExpr()->getImplicitObjectArgument(); } +RuntimeDefinition CXXMemberCall::getRuntimeDefinition() const { + // C++11 [expr.call]p1: ...If the selected function is non-virtual, or if the + // id-expression in the class member access expression is a qualified-id, + // that function is called. Otherwise, its final overrider in the dynamic type + // of the object expression is called. + if (const MemberExpr *ME = dyn_cast<MemberExpr>(getOriginExpr()->getCallee())) + if (ME->hasQualifier()) + return AnyFunctionCall::getRuntimeDefinition(); + + return CXXInstanceCall::getRuntimeDefinition(); +} + const Expr *CXXMemberOperatorCall::getCXXThisExpr() const { return getOriginExpr()->getArg(0); @@ -501,15 +575,6 @@ void BlockCall::getInitialStackFrameContents(const StackFrameContext *CalleeCtx, } -QualType BlockCall::getDeclaredResultType() const { - const BlockDataRegion *BR = getBlockRegion(); - if (!BR) - return QualType(); - QualType BlockTy = BR->getCodeRegion()->getLocationType(); - return cast<FunctionType>(BlockTy->getPointeeType())->getResultType(); -} - - SVal CXXConstructorCall::getCXXThisVal() const { if (Data) return loc::MemRegionVal(static_cast<const MemRegion *>(Data)); @@ -539,10 +604,19 @@ void CXXConstructorCall::getInitialStackFrameContents( SVal CXXDestructorCall::getCXXThisVal() const { if (Data) - return loc::MemRegionVal(static_cast<const MemRegion *>(Data)); + return loc::MemRegionVal(DtorDataTy::getFromOpaqueValue(Data).getPointer()); return UnknownVal(); } +RuntimeDefinition CXXDestructorCall::getRuntimeDefinition() const { + // Base destructors are always called non-virtually. + // Skip CXXInstanceCall's devirtualization logic in this case. + if (isBaseDestructor()) + return AnyFunctionCall::getRuntimeDefinition(); + + return CXXInstanceCall::getRuntimeDefinition(); +} + CallEvent::param_iterator ObjCMethodCall::param_begin() const { const ObjCMethodDecl *D = getDecl(); @@ -566,12 +640,12 @@ ObjCMethodCall::getExtraInvalidatedRegions(RegionList &Regions) const { Regions.push_back(R); } -QualType ObjCMethodCall::getDeclaredResultType() const { - const ObjCMethodDecl *D = getDecl(); - if (!D) - return QualType(); - - return D->getResultType(); +SVal ObjCMethodCall::getSelfSVal() const { + const LocationContext *LCtx = getLocationContext(); + const ImplicitParamDecl *SelfDecl = LCtx->getSelfDecl(); + if (!SelfDecl) + return SVal(); + return getState()->getSVal(getState()->getRegion(SelfDecl, LCtx)); } SVal ObjCMethodCall::getReceiverSVal() const { @@ -584,10 +658,23 @@ SVal ObjCMethodCall::getReceiverSVal() const { // An instance message with no expression means we are sending to super. // In this case the object reference is the same as 'self'. - const LocationContext *LCtx = getLocationContext(); - const ImplicitParamDecl *SelfDecl = LCtx->getSelfDecl(); - assert(SelfDecl && "No message receiver Expr, but not in an ObjC method"); - return getState()->getSVal(getState()->getRegion(SelfDecl, LCtx)); + assert(getOriginExpr()->getReceiverKind() == ObjCMessageExpr::SuperInstance); + SVal SelfVal = getSelfSVal(); + assert(SelfVal.isValid() && "Calling super but not in ObjC method"); + return SelfVal; +} + +bool ObjCMethodCall::isReceiverSelfOrSuper() const { + if (getOriginExpr()->getReceiverKind() == ObjCMessageExpr::SuperInstance || + getOriginExpr()->getReceiverKind() == ObjCMessageExpr::SuperClass) + return true; + + if (!isInstanceMessage()) + return false; + + SVal RecVal = getSVal(getOriginExpr()->getInstanceReceiver()); + + return (RecVal == getSelfSVal()); } SourceRange ObjCMethodCall::getSourceRange() const { @@ -820,7 +907,8 @@ CallEventManager::getCaller(const StackFrameContext *CalleeCtx, return getSimpleCall(CE, State, CallerCtx); switch (CallSite->getStmtClass()) { - case Stmt::CXXConstructExprClass: { + case Stmt::CXXConstructExprClass: + case Stmt::CXXTemporaryObjectExprClass: { SValBuilder &SVB = State->getStateManager().getSValBuilder(); const CXXMethodDecl *Ctor = cast<CXXMethodDecl>(CalleeCtx->getDecl()); Loc ThisPtr = SVB.getCXXThis(Ctor, CalleeCtx); @@ -858,5 +946,5 @@ CallEventManager::getCaller(const StackFrameContext *CalleeCtx, Trigger = Dtor->getBody(); return getCXXDestructorCall(Dtor, Trigger, ThisVal.getAsRegion(), - State, CallerCtx); + isa<CFGBaseDtor>(E), State, CallerCtx); } diff --git a/lib/StaticAnalyzer/Core/CheckerContext.cpp b/lib/StaticAnalyzer/Core/CheckerContext.cpp index 0a047d9..74eeef1 100644 --- a/lib/StaticAnalyzer/Core/CheckerContext.cpp +++ b/lib/StaticAnalyzer/Core/CheckerContext.cpp @@ -38,17 +38,14 @@ StringRef CheckerContext::getCalleeName(const FunctionDecl *FunDecl) const { bool CheckerContext::isCLibraryFunction(const FunctionDecl *FD, StringRef Name) { - return isCLibraryFunction(FD, Name, getASTContext()); -} - -bool CheckerContext::isCLibraryFunction(const FunctionDecl *FD, - StringRef Name, ASTContext &Context) { // To avoid false positives (Ex: finding user defined functions with // similar names), only perform fuzzy name matching when it's a builtin. // Using a string compare is slow, we might want to switch on BuiltinID here. unsigned BId = FD->getBuiltinID(); if (BId != 0) { - StringRef BName = Context.BuiltinInfo.GetName(BId); + if (Name.empty()) + return true; + StringRef BName = FD->getASTContext().BuiltinInfo.GetName(BId); if (BName.find(Name) != StringRef::npos) return true; } @@ -59,6 +56,24 @@ bool CheckerContext::isCLibraryFunction(const FunctionDecl *FD, if (!II) return false; + // Look through 'extern "C"' and anything similar invented in the future. + const DeclContext *DC = FD->getDeclContext(); + while (DC->isTransparentContext()) + DC = DC->getParent(); + + // If this function is in a namespace, it is not a C library function. + if (!DC->isTranslationUnit()) + return false; + + // 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) + return false; + + if (Name.empty()) + return true; + StringRef FName = II->getName(); if (FName.equals(Name)) return true; diff --git a/lib/StaticAnalyzer/Core/CheckerManager.cpp b/lib/StaticAnalyzer/Core/CheckerManager.cpp index c786655..3672952 100644 --- a/lib/StaticAnalyzer/Core/CheckerManager.cpp +++ b/lib/StaticAnalyzer/Core/CheckerManager.cpp @@ -36,8 +36,7 @@ bool CheckerManager::hasPathSensitiveCheckers() const { !DeadSymbolsCheckers.empty() || !RegionChangesCheckers.empty() || !EvalAssumeCheckers.empty() || - !EvalCallCheckers.empty() || - !InlineCallCheckers.empty(); + !EvalCallCheckers.empty(); } void CheckerManager::finishedCheckerRegistration() { @@ -314,20 +313,19 @@ namespace { SVal Val; const Stmt *S; ExprEngine &Eng; - ProgramPoint::Kind PointKind; + const ProgramPoint &PP; CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); } CheckersTy::const_iterator checkers_end() { return Checkers.end(); } CheckBindContext(const CheckersTy &checkers, SVal loc, SVal val, const Stmt *s, ExprEngine &eng, - ProgramPoint::Kind PK) - : Checkers(checkers), Loc(loc), Val(val), S(s), Eng(eng), PointKind(PK) {} + const ProgramPoint &pp) + : Checkers(checkers), Loc(loc), Val(val), S(s), Eng(eng), PP(pp) {} void runChecker(CheckerManager::CheckBindFunc checkFn, NodeBuilder &Bldr, ExplodedNode *Pred) { - const ProgramPoint &L = ProgramPoint::getProgramPoint(S, PointKind, - Pred->getLocationContext(), checkFn.Checker); + const ProgramPoint &L = PP.withTag(checkFn.Checker); CheckerContext C(Bldr, Eng, Pred, L); checkFn(Loc, Val, S, C); @@ -340,8 +338,8 @@ void CheckerManager::runCheckersForBind(ExplodedNodeSet &Dst, const ExplodedNodeSet &Src, SVal location, SVal val, const Stmt *S, ExprEngine &Eng, - ProgramPoint::Kind PointKind) { - CheckBindContext C(BindCheckers, location, val, S, Eng, PointKind); + const ProgramPoint &PP) { + CheckBindContext C(BindCheckers, location, val, S, Eng, PP); expandGraphWithCheckers(C, Dst, Src); } @@ -357,8 +355,8 @@ void CheckerManager::runCheckersForEndAnalysis(ExplodedGraph &G, // for this callback since end of path nodes are expected to be final. void CheckerManager::runCheckersForEndPath(NodeBuilderContext &BC, ExplodedNodeSet &Dst, + ExplodedNode *Pred, ExprEngine &Eng) { - ExplodedNode *Pred = BC.Pred; // We define the builder outside of the loop bacause if at least one checkers // creates a sucsessor for Pred, we do not need to generate an @@ -509,41 +507,13 @@ void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst, const CallExpr *CE = cast<CallExpr>(Call.getOriginExpr()); for (ExplodedNodeSet::iterator NI = Src.begin(), NE = Src.end(); NI != NE; ++NI) { - ExplodedNode *Pred = *NI; bool anyEvaluated = false; - // First, check if any of the InlineCall callbacks can evaluate the call. - assert(InlineCallCheckers.size() <= 1 && - "InlineCall is a special hacky callback to allow intrusive" - "evaluation of the call (which simulates inlining). It is " - "currently only used by OSAtomicChecker and should go away " - "at some point."); - for (std::vector<InlineCallFunc>::iterator - EI = InlineCallCheckers.begin(), EE = InlineCallCheckers.end(); - EI != EE; ++EI) { - ExplodedNodeSet checkDst; - bool evaluated = (*EI)(CE, Eng, Pred, checkDst); - assert(!(evaluated && anyEvaluated) - && "There are more than one checkers evaluating the call"); - if (evaluated) { - anyEvaluated = true; - Dst.insert(checkDst); -#ifdef NDEBUG - break; // on release don't check that no other checker also evals. -#endif - } - } - -#ifdef NDEBUG // on release don't check that no other checker also evals. - if (anyEvaluated) { - break; - } -#endif - ExplodedNodeSet checkDst; NodeBuilder B(Pred, checkDst, Eng.getBuilderContext()); - // Next, check if any of the EvalCall callbacks can evaluate the call. + + // Check if any of the EvalCall callbacks can evaluate the call. for (std::vector<EvalCallFunc>::iterator EI = EvalCallCheckers.begin(), EE = EvalCallCheckers.end(); EI != EE; ++EI) { @@ -679,10 +649,6 @@ void CheckerManager::_registerForEvalCall(EvalCallFunc checkfn) { EvalCallCheckers.push_back(checkfn); } -void CheckerManager::_registerForInlineCall(InlineCallFunc checkfn) { - InlineCallCheckers.push_back(checkfn); -} - void CheckerManager::_registerForEndOfTranslationUnit( CheckEndOfTranslationUnit checkfn) { EndOfTranslationUnitCheckers.push_back(checkfn); diff --git a/lib/StaticAnalyzer/Core/ConstraintManager.cpp b/lib/StaticAnalyzer/Core/ConstraintManager.cpp new file mode 100644 index 0000000..4dec526 --- /dev/null +++ b/lib/StaticAnalyzer/Core/ConstraintManager.cpp @@ -0,0 +1,39 @@ +//== ConstraintManager.cpp - Constraints on symbolic values -----*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defined the interface to manage constraints on symbolic values. +// +//===----------------------------------------------------------------------===// + +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" + +using namespace clang; +using namespace ento; + +ConstraintManager::~ConstraintManager() {} + +static DefinedSVal getLocFromSymbol(const ProgramStateRef &State, + SymbolRef Sym) { + const MemRegion *R = State->getStateManager().getRegionManager() + .getSymbolicRegion(Sym); + return loc::MemRegionVal(R); +} + +ConditionTruthVal ConstraintManager::checkNull(ProgramStateRef State, + SymbolRef Sym) { + QualType Ty = Sym->getType(); + DefinedSVal V = Loc::isLocType(Ty) ? getLocFromSymbol(State, Sym) + : nonloc::SymbolVal(Sym); + const ProgramStatePair &P = assumeDual(State, V); + if (P.first && !P.second) + return ConditionTruthVal(false); + if (!P.first && P.second) + return ConditionTruthVal(true); + return ConditionTruthVal(); +} diff --git a/lib/StaticAnalyzer/Core/CoreEngine.cpp b/lib/StaticAnalyzer/Core/CoreEngine.cpp index 1f13742..ec23792 100644 --- a/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -243,11 +243,6 @@ void CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc, case ProgramPoint::CallEnterKind: { CallEnter CEnter = cast<CallEnter>(Loc); - if (AnalyzedCallees) - if (const CallExpr* CE = - dyn_cast_or_null<CallExpr>(CEnter.getCallExpr())) - if (const Decl *CD = CE->getCalleeDecl()) - AnalyzedCallees->insert(CD); SubEng.processCallEnter(CEnter, Pred); break; } @@ -303,7 +298,7 @@ void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { && "EXIT block cannot contain Stmts."); // Process the final state transition. - SubEng.processEndOfFunction(BuilderCtx); + SubEng.processEndOfFunction(BuilderCtx, Pred); // This path is done. Don't enqueue any more nodes. return; @@ -313,7 +308,7 @@ void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { ExplodedNodeSet dstNodes; BlockEntrance BE(Blk, Pred->getLocationContext()); NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE); - SubEng.processCFGBlockEntrance(L, nodeBuilder); + SubEng.processCFGBlockEntrance(L, nodeBuilder, Pred); // Auto-generate a node. if (!nodeBuilder.hasGeneratedNodes()) { @@ -519,9 +514,9 @@ void CoreEngine::enqueueStmtNode(ExplodedNode *N, return; } - const CFGStmt *CS = (*Block)[Idx].getAs<CFGStmt>(); - const Stmt *St = CS ? CS->getStmt() : 0; - PostStmt Loc(St, N->getLocationContext()); + // At this point, we know we're processing a normal statement. + CFGStmt CS = cast<CFGStmt>((*Block)[Idx]); + PostStmt Loc(CS.getStmt(), N->getLocationContext()); if (Loc == N->getLocation()) { // Note: 'N' should be a fresh node because otherwise it shouldn't be diff --git a/lib/StaticAnalyzer/Core/Environment.cpp b/lib/StaticAnalyzer/Core/Environment.cpp index 52644f7..bab89c5 100644 --- a/lib/StaticAnalyzer/Core/Environment.cpp +++ b/lib/StaticAnalyzer/Core/Environment.cpp @@ -20,6 +20,44 @@ using namespace clang; using namespace ento; +static const Expr *ignoreTransparentExprs(const Expr *E) { + E = E->IgnoreParens(); + + switch (E->getStmtClass()) { + case Stmt::OpaqueValueExprClass: + E = cast<OpaqueValueExpr>(E)->getSourceExpr(); + break; + case Stmt::ExprWithCleanupsClass: + E = cast<ExprWithCleanups>(E)->getSubExpr(); + break; + case Stmt::CXXBindTemporaryExprClass: + E = cast<CXXBindTemporaryExpr>(E)->getSubExpr(); + break; + case Stmt::SubstNonTypeTemplateParmExprClass: + E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement(); + break; + case Stmt::CXXDefaultArgExprClass: + E = cast<CXXDefaultArgExpr>(E)->getExpr(); + break; + default: + // This is the base case: we can't look through more than we already have. + return E; + } + + return ignoreTransparentExprs(E); +} + +static const Stmt *ignoreTransparentExprs(const Stmt *S) { + if (const Expr *E = dyn_cast<Expr>(S)) + return ignoreTransparentExprs(E); + return S; +} + +EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L) + : std::pair<const Stmt *, + const StackFrameContext *>(ignoreTransparentExprs(S), + L ? L->getCurrentStackFrame() : 0) {} + SVal Environment::lookupExpr(const EnvironmentEntry &E) const { const SVal* X = ExprBindings.lookup(E); if (X) { @@ -30,101 +68,72 @@ SVal Environment::lookupExpr(const EnvironmentEntry &E) const { } SVal Environment::getSVal(const EnvironmentEntry &Entry, - SValBuilder& svalBuilder, - bool useOnlyDirectBindings) const { - - if (useOnlyDirectBindings) { - // This branch is rarely taken, but can be exercised by - // checkers that explicitly bind values to arbitrary - // expressions. It is crucial that we do not ignore any - // expression here, and do a direct lookup. - return lookupExpr(Entry); + SValBuilder& svalBuilder) const { + const Stmt *S = Entry.getStmt(); + const LocationContext *LCtx = Entry.getLocationContext(); + + switch (S->getStmtClass()) { + case Stmt::CXXBindTemporaryExprClass: + case Stmt::CXXDefaultArgExprClass: + case Stmt::ExprWithCleanupsClass: + case Stmt::GenericSelectionExprClass: + case Stmt::OpaqueValueExprClass: + case Stmt::ParenExprClass: + case Stmt::SubstNonTypeTemplateParmExprClass: + llvm_unreachable("Should have been handled by ignoreTransparentExprs"); + + case Stmt::AddrLabelExprClass: + return svalBuilder.makeLoc(cast<AddrLabelExpr>(S)); + + case Stmt::CharacterLiteralClass: { + const CharacterLiteral *C = cast<CharacterLiteral>(S); + return svalBuilder.makeIntVal(C->getValue(), C->getType()); } - const Stmt *E = Entry.getStmt(); - const LocationContext *LCtx = Entry.getLocationContext(); - - for (;;) { - if (const Expr *Ex = dyn_cast<Expr>(E)) - E = Ex->IgnoreParens(); - - switch (E->getStmtClass()) { - case Stmt::AddrLabelExprClass: - return svalBuilder.makeLoc(cast<AddrLabelExpr>(E)); - case Stmt::OpaqueValueExprClass: { - const OpaqueValueExpr *ope = cast<OpaqueValueExpr>(E); - E = ope->getSourceExpr(); - continue; - } - case Stmt::ParenExprClass: - case Stmt::GenericSelectionExprClass: - llvm_unreachable("ParenExprs and GenericSelectionExprs should " - "have been handled by IgnoreParens()"); - case Stmt::CharacterLiteralClass: { - const CharacterLiteral* C = cast<CharacterLiteral>(E); - return svalBuilder.makeIntVal(C->getValue(), C->getType()); - } - case Stmt::CXXBoolLiteralExprClass: { - const SVal *X = ExprBindings.lookup(EnvironmentEntry(E, LCtx)); - if (X) - return *X; - else - return svalBuilder.makeBoolVal(cast<CXXBoolLiteralExpr>(E)); - } - case Stmt::CXXScalarValueInitExprClass: - case Stmt::ImplicitValueInitExprClass: { - QualType Ty = cast<Expr>(E)->getType(); - return svalBuilder.makeZeroVal(Ty); - } - case Stmt::IntegerLiteralClass: { - // In C++, this expression may have been bound to a temporary object. - SVal const *X = ExprBindings.lookup(EnvironmentEntry(E, LCtx)); - if (X) - return *X; - else - return svalBuilder.makeIntVal(cast<IntegerLiteral>(E)); - } - case Stmt::ObjCBoolLiteralExprClass: - return svalBuilder.makeBoolVal(cast<ObjCBoolLiteralExpr>(E)); - - // For special C0xx nullptr case, make a null pointer SVal. - case Stmt::CXXNullPtrLiteralExprClass: - return svalBuilder.makeNull(); - case Stmt::ExprWithCleanupsClass: - E = cast<ExprWithCleanups>(E)->getSubExpr(); - continue; - case Stmt::CXXBindTemporaryExprClass: - E = cast<CXXBindTemporaryExpr>(E)->getSubExpr(); - continue; - case Stmt::SubstNonTypeTemplateParmExprClass: - E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement(); - continue; - case Stmt::ObjCStringLiteralClass: { - MemRegionManager &MRMgr = svalBuilder.getRegionManager(); - const ObjCStringLiteral *SL = cast<ObjCStringLiteral>(E); - return svalBuilder.makeLoc(MRMgr.getObjCStringRegion(SL)); - } - case Stmt::StringLiteralClass: { - MemRegionManager &MRMgr = svalBuilder.getRegionManager(); - const StringLiteral *SL = cast<StringLiteral>(E); - return svalBuilder.makeLoc(MRMgr.getStringRegion(SL)); - } - case Stmt::ReturnStmtClass: { - const ReturnStmt *RS = cast<ReturnStmt>(E); - if (const Expr *RE = RS->getRetValue()) { - E = RE; - continue; - } - return UndefinedVal(); - } - - // Handle all other Stmt* using a lookup. - default: - break; - }; + case Stmt::CXXBoolLiteralExprClass: + return svalBuilder.makeBoolVal(cast<CXXBoolLiteralExpr>(S)); + + case Stmt::CXXScalarValueInitExprClass: + case Stmt::ImplicitValueInitExprClass: { + QualType Ty = cast<Expr>(S)->getType(); + return svalBuilder.makeZeroVal(Ty); + } + + case Stmt::IntegerLiteralClass: + return svalBuilder.makeIntVal(cast<IntegerLiteral>(S)); + + case Stmt::ObjCBoolLiteralExprClass: + return svalBuilder.makeBoolVal(cast<ObjCBoolLiteralExpr>(S)); + + // For special C0xx nullptr case, make a null pointer SVal. + case Stmt::CXXNullPtrLiteralExprClass: + return svalBuilder.makeNull(); + + case Stmt::ObjCStringLiteralClass: { + MemRegionManager &MRMgr = svalBuilder.getRegionManager(); + const ObjCStringLiteral *SL = cast<ObjCStringLiteral>(S); + return svalBuilder.makeLoc(MRMgr.getObjCStringRegion(SL)); + } + + case Stmt::StringLiteralClass: { + MemRegionManager &MRMgr = svalBuilder.getRegionManager(); + const StringLiteral *SL = cast<StringLiteral>(S); + return svalBuilder.makeLoc(MRMgr.getStringRegion(SL)); + } + + case Stmt::ReturnStmtClass: { + const ReturnStmt *RS = cast<ReturnStmt>(S); + if (const Expr *RE = RS->getRetValue()) + return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder); + return UndefinedVal(); + } + + // Handle all other Stmt* using a lookup. + default: break; } - return lookupExpr(EnvironmentEntry(E, LCtx)); + + return lookupExpr(EnvironmentEntry(S, LCtx)); } Environment EnvironmentManager::bindExpr(Environment Env, @@ -140,16 +149,16 @@ Environment EnvironmentManager::bindExpr(Environment Env, return Environment(F.add(Env.ExprBindings, E, V)); } -static inline EnvironmentEntry MakeLocation(const EnvironmentEntry &E) { - const Stmt *S = E.getStmt(); - S = (const Stmt*) (((uintptr_t) S) | 0x1); - return EnvironmentEntry(S, E.getLocationContext()); +EnvironmentEntry EnvironmentEntry::makeLocation() const { + EnvironmentEntry Result = *this; + reinterpret_cast<uintptr_t &>(Result.first) |= 0x1; + return Result; } Environment EnvironmentManager::bindExprAndLocation(Environment Env, const EnvironmentEntry &E, SVal location, SVal V) { - return Environment(F.add(F.add(Env.ExprBindings, MakeLocation(E), location), + return Environment(F.add(F.add(Env.ExprBindings, E.makeLocation(), location), E, V)); } @@ -286,7 +295,8 @@ void Environment::printAux(raw_ostream &Out, bool printLocations, S = (Stmt*) (((uintptr_t) S) & ((uintptr_t) ~0x1)); } - Out << " (" << (void*) En.getLocationContext() << ',' << (void*) S << ") "; + Out << " (" << (const void*) En.getLocationContext() << ',' + << (const void*) S << ") "; LangOptions LO; // FIXME. S->printPretty(Out, 0, PrintingPolicy(LO)); Out << " : " << I.getData(); diff --git a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp index b79f3f5..c284bd7 100644 --- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp +++ b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp @@ -47,10 +47,8 @@ void ExplodedNode::SetAuditor(ExplodedNode::Auditor* A) { // Cleanup. //===----------------------------------------------------------------------===// -static const unsigned CounterTop = 1000; - ExplodedGraph::ExplodedGraph() - : NumNodes(0), reclaimNodes(false), reclaimCounter(CounterTop) {} + : NumNodes(0), ReclaimNodeInterval(0) {} ExplodedGraph::~ExplodedGraph() {} @@ -63,12 +61,12 @@ bool ExplodedGraph::shouldCollect(const ExplodedNode *node) { // // (1) 1 predecessor (that has one successor) // (2) 1 successor (that has one predecessor) - // (3) The ProgramPoint is for a PostStmt. + // (3) The ProgramPoint is for a PostStmt, but not a PostStore. // (4) There is no 'tag' for the ProgramPoint. // (5) The 'store' is the same as the predecessor. // (6) The 'GDM' is the same as the predecessor. // (7) The LocationContext is the same as the predecessor. - // (8) The PostStmt is for a non-consumed Stmt or Expr. + // (8) The PostStmt isn't for a non-consumed Stmt or Expr. // (9) The successor is not a CallExpr StmtPoint (so that we would be able to // find it when retrying a call with no inlining). // FIXME: It may be safe to reclaim PreCall and PostCall nodes as well. @@ -87,16 +85,13 @@ bool ExplodedGraph::shouldCollect(const ExplodedNode *node) { // Condition 3. ProgramPoint progPoint = node->getLocation(); - if (!isa<PostStmt>(progPoint)) + if (!isa<PostStmt>(progPoint) || isa<PostStore>(progPoint)) return false; // Condition 4. PostStmt ps = cast<PostStmt>(progPoint); if (ps.getTag()) return false; - - if (isa<BinaryOperator>(ps.getStmt())) - return false; // Conditions 5, 6, and 7. ProgramStateRef state = node->getState(); @@ -106,6 +101,12 @@ bool ExplodedGraph::shouldCollect(const ExplodedNode *node) { return false; // Condition 8. + // Do not collect nodes for non-consumed Stmt or Expr to ensure precise + // diagnostic generation; specifically, so that we could anchor arrows + // pointing to the beginning of statements (as written in code). + if (!isa<Expr>(ps.getStmt())) + return false; + if (const Expr *Ex = dyn_cast<Expr>(ps.getStmt())) { ParentMap &PM = progPoint.getLocationContext()->getParentMap(); if (!PM.isConsumedExpr(Ex)) @@ -115,7 +116,7 @@ bool ExplodedGraph::shouldCollect(const ExplodedNode *node) { // Condition 9. const ProgramPoint SuccLoc = succ->getLocation(); if (const StmtPoint *SP = dyn_cast<StmtPoint>(&SuccLoc)) - if (CallEvent::mayBeInlined(SP->getStmt())) + if (CallEvent::isCallStmt(SP->getStmt())) return false; return true; @@ -141,13 +142,13 @@ void ExplodedGraph::reclaimRecentlyAllocatedNodes() { if (ChangedNodes.empty()) return; - // Only periodically relcaim nodes so that we can build up a set of + // Only periodically reclaim nodes so that we can build up a set of // nodes that meet the reclamation criteria. Freshly created nodes // by definition have no successor, and thus cannot be reclaimed (see below). - assert(reclaimCounter > 0); - if (--reclaimCounter != 0) + assert(ReclaimCounter > 0); + if (--ReclaimCounter != 0) return; - reclaimCounter = CounterTop; + ReclaimCounter = ReclaimNodeInterval; for (NodeVector::iterator it = ChangedNodes.begin(), et = ChangedNodes.end(); it != et; ++it) { @@ -162,9 +163,18 @@ void ExplodedGraph::reclaimRecentlyAllocatedNodes() { // ExplodedNode. //===----------------------------------------------------------------------===// -static inline BumpVector<ExplodedNode*>& getVector(void *P) { - return *reinterpret_cast<BumpVector<ExplodedNode*>*>(P); -} +// An NodeGroup's storage type is actually very much like a TinyPtrVector: +// it can be either a pointer to a single ExplodedNode, or a pointer to a +// BumpVector allocated with the ExplodedGraph's allocator. This allows the +// common case of single-node NodeGroups to be implemented with no extra memory. +// +// Consequently, each of the NodeGroup methods have up to four cases to handle: +// 1. The flag is set and this group does not actually contain any nodes. +// 2. The group is empty, in which case the storage value is null. +// 3. The group contains a single node. +// 4. The group contains more than one node. +typedef BumpVector<ExplodedNode *> ExplodedNodeVector; +typedef llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *> GroupStorage; void ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) { assert (!V->isSink()); @@ -176,71 +186,77 @@ void ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) { } void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) { - assert(getKind() == Size1); - P = reinterpret_cast<uintptr_t>(node); - assert(getKind() == Size1); + assert(!getFlag()); + + GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P); + assert(Storage.is<ExplodedNode *>()); + Storage = node; + assert(Storage.is<ExplodedNode *>()); } void ExplodedNode::NodeGroup::addNode(ExplodedNode *N, ExplodedGraph &G) { - assert((reinterpret_cast<uintptr_t>(N) & Mask) == 0x0); assert(!getFlag()); - if (getKind() == Size1) { - if (ExplodedNode *NOld = getNode()) { - BumpVectorContext &Ctx = G.getNodeAllocator(); - BumpVector<ExplodedNode*> *V = - G.getAllocator().Allocate<BumpVector<ExplodedNode*> >(); - new (V) BumpVector<ExplodedNode*>(Ctx, 4); - - assert((reinterpret_cast<uintptr_t>(V) & Mask) == 0x0); - V->push_back(NOld, Ctx); - V->push_back(N, Ctx); - P = reinterpret_cast<uintptr_t>(V) | SizeOther; - assert(getPtr() == (void*) V); - assert(getKind() == SizeOther); - } - else { - P = reinterpret_cast<uintptr_t>(N); - assert(getKind() == Size1); - } + GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P); + if (Storage.isNull()) { + Storage = N; + assert(Storage.is<ExplodedNode *>()); + return; } - else { - assert(getKind() == SizeOther); - getVector(getPtr()).push_back(N, G.getNodeAllocator()); + + ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>(); + + if (!V) { + // Switch from single-node to multi-node representation. + ExplodedNode *Old = Storage.get<ExplodedNode *>(); + + BumpVectorContext &Ctx = G.getNodeAllocator(); + V = G.getAllocator().Allocate<ExplodedNodeVector>(); + new (V) ExplodedNodeVector(Ctx, 4); + V->push_back(Old, Ctx); + + Storage = V; + assert(!getFlag()); + assert(Storage.is<ExplodedNodeVector *>()); } + + V->push_back(N, G.getNodeAllocator()); } unsigned ExplodedNode::NodeGroup::size() const { if (getFlag()) return 0; - if (getKind() == Size1) - return getNode() ? 1 : 0; - else - return getVector(getPtr()).size(); + const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P); + if (Storage.isNull()) + return 0; + if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>()) + return V->size(); + return 1; } -ExplodedNode **ExplodedNode::NodeGroup::begin() const { +ExplodedNode * const *ExplodedNode::NodeGroup::begin() const { if (getFlag()) - return NULL; + return 0; - if (getKind() == Size1) - return (ExplodedNode**) (getPtr() ? &P : NULL); - else - return const_cast<ExplodedNode**>(&*(getVector(getPtr()).begin())); + const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P); + if (Storage.isNull()) + return 0; + if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>()) + return V->begin(); + return Storage.getAddrOfPtr1(); } -ExplodedNode** ExplodedNode::NodeGroup::end() const { +ExplodedNode * const *ExplodedNode::NodeGroup::end() const { if (getFlag()) - return NULL; - - if (getKind() == Size1) - return (ExplodedNode**) (getPtr() ? &P+1 : NULL); - else { - // Dereferencing end() is undefined behaviour. The vector is not empty, so - // we can dereference the last elem and then add 1 to the result. - return const_cast<ExplodedNode**>(getVector(getPtr()).end()); - } + return 0; + + const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P); + if (Storage.isNull()) + return 0; + if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>()) + return V->end(); + return Storage.getAddrOfPtr1() + 1; } ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L, @@ -266,7 +282,7 @@ ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L, new (V) NodeTy(L, State, IsSink); - if (reclaimNodes) + if (ReclaimNodeInterval) ChangedNodes.push_back(V); // Insert the node into the node set and return it. @@ -314,8 +330,8 @@ ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources, // ===- Pass 1 (reverse DFS) -=== for (const ExplodedNode* const* I = BeginSources; I != EndSources; ++I) { - assert(*I); - WL1.push_back(*I); + if (*I) + WL1.push_back(*I); } // Process the first worklist until it is empty. Because it is a std::list @@ -338,7 +354,8 @@ ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources, } // Visit our predecessors and enqueue them. - for (ExplodedNode** I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I) + for (ExplodedNode::pred_iterator I = N->Preds.begin(), E = N->Preds.end(); + I != E; ++I) WL1.push_back(*I); } @@ -375,7 +392,8 @@ ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources, // Walk through the predecessors of 'N' and hook up their corresponding // nodes in the new graph (if any) to the freshly created node. - for (ExplodedNode **I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I) { + for (ExplodedNode::pred_iterator I = N->Preds.begin(), E = N->Preds.end(); + I != E; ++I) { Pass2Ty::iterator PI = Pass2.find(*I); if (PI == Pass2.end()) continue; @@ -387,7 +405,8 @@ ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources, // been created, we should hook them up as successors. Otherwise, enqueue // the new nodes from the original graph that should have nodes created // in the new graph. - for (ExplodedNode **I=N->Succs.begin(), **E=N->Succs.end(); I!=E; ++I) { + for (ExplodedNode::succ_iterator I = N->Succs.begin(), E = N->Succs.end(); + I != E; ++I) { Pass2Ty::iterator PI = Pass2.find(*I); if (PI != Pass2.end()) { PI->second->addPredecessor(NewN, *G); diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp index b0435fb..045591c 100644 --- a/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -55,32 +55,32 @@ STATISTIC(NumTimesRetriedWithoutInlining, //===----------------------------------------------------------------------===// ExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled, - SetOfConstDecls *VisitedCallees, + SetOfConstDecls *VisitedCalleesIn, FunctionSummariesTy *FS) : AMgr(mgr), AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()), - Engine(*this, VisitedCallees, FS), + Engine(*this, FS), G(Engine.getGraph()), StateMgr(getContext(), mgr.getStoreManagerCreator(), mgr.getConstraintManagerCreator(), G.getAllocator(), - *this), + this), SymMgr(StateMgr.getSymbolManager()), svalBuilder(StateMgr.getSValBuilder()), EntryNode(NULL), - currentStmt(NULL), currentStmtIdx(0), currentBuilderContext(0), - NSExceptionII(NULL), NSExceptionInstanceRaiseSelectors(NULL), - RaiseSel(GetNullarySelector("raise", getContext())), - ObjCGCEnabled(gcEnabled), BR(mgr, *this) { - - if (mgr.shouldEagerlyTrimExplodedGraph()) { - // Enable eager node reclaimation when constructing the ExplodedGraph. - G.enableNodeReclamation(); + currStmt(NULL), currStmtIdx(0), currBldrCtx(0), + ObjCNoRet(mgr.getASTContext()), + ObjCGCEnabled(gcEnabled), BR(mgr, *this), + VisitedCallees(VisitedCalleesIn) +{ + unsigned TrimInterval = mgr.options.getGraphTrimInterval(); + if (TrimInterval != 0) { + // Enable eager node reclaimation when constructing the ExplodedGraph. + G.enableNodeReclamation(TrimInterval); } } ExprEngine::~ExprEngine() { BR.FlushReports(); - delete [] NSExceptionInstanceRaiseSelectors; } //===----------------------------------------------------------------------===// @@ -164,6 +164,23 @@ ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) { return state; } +/// If the value of the given expression is a NonLoc, copy it into a new +/// temporary region, and replace the value of the expression with that. +static ProgramStateRef createTemporaryRegionIfNeeded(ProgramStateRef State, + const LocationContext *LC, + const Expr *E) { + SVal V = State->getSVal(E, LC); + + if (isa<NonLoc>(V)) { + MemRegionManager &MRMgr = State->getStateManager().getRegionManager(); + const MemRegion *R = MRMgr.getCXXTempObjectRegion(E, LC); + State = State->bindLoc(loc::MemRegionVal(R), V); + State = State->BindExpr(E, LC, loc::MemRegionVal(R)); + } + + return State; +} + //===----------------------------------------------------------------------===// // Top-level transfer function logic (Dispatcher). //===----------------------------------------------------------------------===// @@ -200,8 +217,8 @@ void ExprEngine::processEndWorklist(bool hasWorkRemaining) { void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, unsigned StmtIdx, NodeBuilderContext *Ctx) { - currentStmtIdx = StmtIdx; - currentBuilderContext = Ctx; + currStmtIdx = StmtIdx; + currBldrCtx = Ctx; switch (E.getKind()) { case CFGElement::Invalid: @@ -219,7 +236,7 @@ void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, ProcessImplicitDtor(*E.getAs<CFGImplicitDtor>(), Pred); return; } - currentBuilderContext = 0; + currBldrCtx = 0; } static bool shouldRemoveDeadBindings(AnalysisManager &AMgr, @@ -228,7 +245,7 @@ static bool shouldRemoveDeadBindings(AnalysisManager &AMgr, const LocationContext *LC) { // Are we never purging state values? - if (AMgr.getPurgeMode() == PurgeNone) + if (AMgr.options.AnalysisPurgeOpt == PurgeNone) return false; // Is this the beginning of a basic block? @@ -240,7 +257,7 @@ static bool shouldRemoveDeadBindings(AnalysisManager &AMgr, return true; // Run before processing a call. - if (CallEvent::mayBeInlined(S.getStmt())) + if (CallEvent::isCallStmt(S.getStmt())) return true; // Is this an expression that is consumed by another expression? If so, @@ -251,12 +268,12 @@ static bool shouldRemoveDeadBindings(AnalysisManager &AMgr, void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out, const Stmt *ReferenceStmt, - const LocationContext *LC, + const StackFrameContext *LC, const Stmt *DiagnosticStmt, ProgramPoint::Kind K) { assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind || - ReferenceStmt == 0) && "PreStmt is not generally supported by " - "the SymbolReaper yet"); + ReferenceStmt == 0) + && "PostStmt is not generally supported by the SymbolReaper yet"); NumRemoveDeadBindings++; CleanedState = Pred->getState(); SymbolReaper SymReaper(LC, ReferenceStmt, SymMgr, getStoreManager()); @@ -276,8 +293,8 @@ void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out, // Generate a CleanedNode that has the environment and store cleaned // up. Since no symbols are dead, we can optimize and not clean out // the constraint manager. - StmtNodeBuilder Bldr(Pred, Out, *currentBuilderContext); - Bldr.generateNode(DiagnosticStmt, Pred, CleanedState, false, &cleanupTag,K); + StmtNodeBuilder Bldr(Pred, Out, *currBldrCtx); + Bldr.generateNode(DiagnosticStmt, Pred, CleanedState, &cleanupTag, K); } else { // Call checkers with the non-cleaned state so that they could query the @@ -289,7 +306,7 @@ void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out, // For each node in CheckedSet, generate CleanedNodes that have the // environment, the store, and the constraints cleaned up but have the // user-supplied states as the predecessors. - StmtNodeBuilder Bldr(CheckedSet, Out, *currentBuilderContext); + StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx); for (ExplodedNodeSet::const_iterator I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) { ProgramStateRef CheckerState = (*I)->getState(); @@ -309,8 +326,7 @@ void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out, // generate a transition to that state. ProgramStateRef CleanedCheckerSt = StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState); - Bldr.generateNode(DiagnosticStmt, *I, CleanedCheckerSt, false, - &cleanupTag, K); + Bldr.generateNode(DiagnosticStmt, *I, CleanedCheckerSt, &cleanupTag, K); } } } @@ -320,17 +336,17 @@ void ExprEngine::ProcessStmt(const CFGStmt S, // Reclaim any unnecessary nodes in the ExplodedGraph. G.reclaimRecentlyAllocatedNodes(); - currentStmt = S.getStmt(); + currStmt = S.getStmt(); PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), - currentStmt->getLocStart(), + currStmt->getLocStart(), "Error evaluating statement"); // Remove dead bindings and symbols. EntryNode = Pred; ExplodedNodeSet CleanedStates; if (shouldRemoveDeadBindings(AMgr, S, Pred, EntryNode->getLocationContext())){ - removeDead(EntryNode, CleanedStates, currentStmt, - Pred->getLocationContext(), currentStmt); + removeDead(EntryNode, CleanedStates, currStmt, + Pred->getStackFrame(), currStmt); } else CleanedStates.Add(EntryNode); @@ -340,44 +356,45 @@ void ExprEngine::ProcessStmt(const CFGStmt S, E = CleanedStates.end(); I != E; ++I) { ExplodedNodeSet DstI; // Visit the statement. - Visit(currentStmt, *I, DstI); + Visit(currStmt, *I, DstI); Dst.insert(DstI); } // Enqueue the new nodes onto the work list. - Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx); + Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); // NULL out these variables to cleanup. CleanedState = NULL; EntryNode = NULL; - currentStmt = 0; + currStmt = 0; } void ExprEngine::ProcessInitializer(const CFGInitializer Init, ExplodedNode *Pred) { - ExplodedNodeSet Dst; - NodeBuilder Bldr(Pred, Dst, *currentBuilderContext); - - ProgramStateRef State = Pred->getState(); - const CXXCtorInitializer *BMI = Init.getInitializer(); PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), BMI->getSourceLocation(), "Error evaluating initializer"); - // We don't set EntryNode and currentStmt. And we don't clean up state. + // We don't set EntryNode and currStmt. And we don't clean up state. const StackFrameContext *stackFrame = cast<StackFrameContext>(Pred->getLocationContext()); const CXXConstructorDecl *decl = cast<CXXConstructorDecl>(stackFrame->getDecl()); + + ProgramStateRef State = Pred->getState(); SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame)); + PostInitializer PP(BMI, stackFrame); + ExplodedNodeSet Tmp(Pred); + // Evaluate the initializer, if necessary if (BMI->isAnyMemberInitializer()) { // Constructors build the object directly in the field, // but non-objects must be copied in from the initializer. - if (!isa<CXXConstructExpr>(BMI->getInit())) { + const Expr *Init = BMI->getInit(); + if (!isa<CXXConstructExpr>(Init)) { SVal FieldLoc; if (BMI->isIndirectMemberInitializer()) FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal); @@ -385,22 +402,26 @@ void ExprEngine::ProcessInitializer(const CFGInitializer Init, FieldLoc = State->getLValue(BMI->getMember(), thisVal); SVal InitVal = State->getSVal(BMI->getInit(), stackFrame); - State = State->bindLoc(FieldLoc, InitVal); + + Tmp.clear(); + evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP); } } else { assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer()); // We already did all the work when visiting the CXXConstructExpr. } - // Construct a PostInitializer node whether the state changed or not, + // Construct PostInitializer nodes whether the state changed or not, // so that the diagnostics don't get confused. - PostInitializer PP(BMI, stackFrame); - // Builder automatically add the generated node to the deferred set, - // which are processed in the builder's dtor. - Bldr.generateNode(PP, State, Pred); + ExplodedNodeSet Dst; + NodeBuilder Bldr(Tmp, Dst, *currBldrCtx); + for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; ++I) { + ExplodedNode *N = *I; + Bldr.generateNode(PP, N->getState(), N); + } // Enqueue the new nodes onto the work list. - Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx); + Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); } void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, @@ -424,7 +445,7 @@ void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, } // Enqueue the new nodes onto the work list. - Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx); + Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx); } void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor, @@ -441,7 +462,7 @@ void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor, Loc dest = state->getLValue(varDecl, Pred->getLocationContext()); VisitCXXDestructor(varType, cast<loc::MemRegionVal>(dest).getRegion(), - Dtor.getTriggerStmt(), Pred, Dst); + Dtor.getTriggerStmt(), /*IsBase=*/false, Pred, Dst); } void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, @@ -459,7 +480,7 @@ void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy); VisitCXXDestructor(BaseTy, cast<loc::MemRegionVal>(BaseVal).getRegion(), - CurDtor->getBody(), Pred, Dst); + CurDtor->getBody(), /*IsBase=*/true, Pred, Dst); } void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, @@ -475,7 +496,7 @@ void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, VisitCXXDestructor(Member->getType(), cast<loc::MemRegionVal>(FieldVal).getRegion(), - CurDtor->getBody(), Pred, Dst); + CurDtor->getBody(), /*IsBase=*/false, Pred, Dst); } void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, @@ -488,7 +509,7 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, S->getLocStart(), "Error evaluating statement"); ExplodedNodeSet Dst; - StmtNodeBuilder Bldr(Pred, DstTop, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx); // Expressions to ignore. if (const Expr *Ex = dyn_cast<Expr>(S)) @@ -498,7 +519,7 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, // this check when we KNOW that there is no block-level subexpression. // The motivation is that this check requires a hashtable lookup. - if (S != currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(S)) + if (S != currStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(S)) return; switch (S->getStmtClass()) { @@ -521,21 +542,16 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, case Stmt::CXXNoexceptExprClass: case Stmt::PackExpansionExprClass: case Stmt::SubstNonTypeTemplateParmPackExprClass: + case Stmt::FunctionParmPackExprClass: case Stmt::SEHTryStmtClass: case Stmt::SEHExceptStmtClass: case Stmt::LambdaExprClass: case Stmt::SEHFinallyStmtClass: { - const ExplodedNode *node = Bldr.generateNode(S, Pred, Pred->getState(), - /* sink */ true); - Engine.addAbortedBlock(node, currentBuilderContext->getBlock()); + const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState()); + Engine.addAbortedBlock(node, currBldrCtx->getBlock()); break; } - // We don't handle default arguments either yet, but we can fake it - // for now by just skipping them. - case Stmt::CXXDefaultArgExprClass: - break; - case Stmt::ParenExprClass: llvm_unreachable("ParenExprs already handled."); case Stmt::GenericSelectionExprClass: @@ -607,11 +623,6 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, case Stmt::AtomicExprClass: // Fall through. - // Currently all handling of 'throw' just falls to the CFG. We - // can consider doing more if necessary. - case Stmt::CXXThrowExprClass: - // Fall through. - // Cases we intentionally don't evaluate, since they don't need // to be explicitly evaluated. case Stmt::AddrLabelExprClass: @@ -626,6 +637,7 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, case Stmt::StringLiteralClass: case Stmt::ObjCStringLiteralClass: case Stmt::CXXBindTemporaryExprClass: + case Stmt::CXXDefaultArgExprClass: case Stmt::SubstNonTypeTemplateParmExprClass: case Stmt::CXXNullPtrLiteralExprClass: { Bldr.takeNodes(Pred); @@ -647,7 +659,7 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this); ExplodedNodeSet Tmp; - StmtNodeBuilder Bldr2(preVisit, Tmp, *currentBuilderContext); + StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx); const Expr *Ex = cast<Expr>(S); QualType resultType = Ex->getType(); @@ -656,9 +668,8 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, it != et; ++it) { ExplodedNode *N = *it; const LocationContext *LCtx = N->getLocationContext(); - SVal result = - svalBuilder.getConjuredSymbolVal(0, Ex, LCtx, resultType, - currentBuilderContext->getCurrentBlockCount()); + SVal result = svalBuilder.conjureSymbolVal(0, Ex, LCtx, resultType, + currBldrCtx->blockCount()); ProgramStateRef state = N->getState()->BindExpr(Ex, LCtx, result); Bldr2.generateNode(S, N, state); } @@ -674,9 +685,9 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, Bldr.addNodes(Dst); break; - case Stmt::AsmStmtClass: + case Stmt::GCCAsmStmtClass: Bldr.takeNodes(Pred); - VisitAsmStmt(cast<AsmStmt>(S), Pred, Dst); + VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst); Bldr.addNodes(Dst); break; @@ -711,11 +722,11 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, Bldr.takeNodes(Pred); - if (AMgr.shouldEagerlyAssume() && + if (AMgr.options.eagerlyAssumeBinOpBifurcation && (B->isRelationalOp() || B->isEqualityOp())) { ExplodedNodeSet Tmp; VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp); - evalEagerlyAssume(Dst, Tmp, cast<Expr>(S)); + evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S)); } else VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst); @@ -724,8 +735,26 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, break; } + case Stmt::CXXOperatorCallExprClass: { + const CXXOperatorCallExpr *OCE = cast<CXXOperatorCallExpr>(S); + + // For instance method operators, make sure the 'this' argument has a + // valid region. + const Decl *Callee = OCE->getCalleeDecl(); + if (const CXXMethodDecl *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) { + if (MD->isInstance()) { + ProgramStateRef State = Pred->getState(); + const LocationContext *LCtx = Pred->getLocationContext(); + ProgramStateRef NewState = + createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0)); + if (NewState != State) + Pred = Bldr.generateNode(OCE, Pred, NewState, /*Tag=*/0, + ProgramPoint::PreStmtKind); + } + } + // FALLTHROUGH + } case Stmt::CallExprClass: - case Stmt::CXXOperatorCallExprClass: case Stmt::CXXMemberCallExprClass: case Stmt::UserDefinedLiteralClass: { Bldr.takeNodes(Pred); @@ -846,12 +875,8 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, case Expr::MaterializeTemporaryExprClass: { Bldr.takeNodes(Pred); - const MaterializeTemporaryExpr *Materialize - = cast<MaterializeTemporaryExpr>(S); - if (Materialize->getType()->isRecordType()) - Dst.Add(Pred); - else - CreateCXXTemporaryObject(Materialize, Pred, Dst); + const MaterializeTemporaryExpr *MTE = cast<MaterializeTemporaryExpr>(S); + CreateCXXTemporaryObject(MTE, Pred, Dst); Bldr.addNodes(Dst); break; } @@ -886,12 +911,12 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, Bldr.addNodes(Dst); break; - case Stmt::ObjCAtThrowStmtClass: { + case Stmt::ObjCAtThrowStmtClass: + case Stmt::CXXThrowExprClass: // FIXME: This is not complete. We basically treat @throw as // an abort. - Bldr.generateNode(S, Pred, Pred->getState()); + Bldr.generateSink(S, Pred, Pred->getState()); break; - } case Stmt::ReturnStmtClass: Bldr.takeNodes(Pred); @@ -935,10 +960,10 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, case Stmt::UnaryOperatorClass: { Bldr.takeNodes(Pred); const UnaryOperator *U = cast<UnaryOperator>(S); - if (AMgr.shouldEagerlyAssume() && (U->getOpcode() == UO_LNot)) { + if (AMgr.options.eagerlyAssumeBinOpBifurcation && (U->getOpcode() == UO_LNot)) { ExplodedNodeSet Tmp; VisitUnaryOperator(U, Pred, Tmp); - evalEagerlyAssume(Dst, Tmp, U); + evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U); } else VisitUnaryOperator(U, Pred, Dst); @@ -1030,19 +1055,18 @@ bool ExprEngine::replayWithoutInlining(ExplodedNode *N, /// Block entrance. (Update counters). void ExprEngine::processCFGBlockEntrance(const BlockEdge &L, - NodeBuilderWithSinks &nodeBuilder) { + NodeBuilderWithSinks &nodeBuilder, + ExplodedNode *Pred) { // FIXME: Refactor this into a checker. - ExplodedNode *pred = nodeBuilder.getContext().getPred(); - - if (nodeBuilder.getContext().getCurrentBlockCount() >= AMgr.getMaxVisit()) { + if (nodeBuilder.getContext().blockCount() >= AMgr.options.maxBlockVisitOnPath) { static SimpleProgramPointTag tag("ExprEngine : Block count exceeded"); const ExplodedNode *Sink = - nodeBuilder.generateNode(pred->getState(), pred, &tag, true); + nodeBuilder.generateSink(Pred->getState(), Pred, &tag); // Check if we stopped at the top level function or not. // Root node should have the location context of the top most function. - const LocationContext *CalleeLC = pred->getLocation().getLocationContext(); + const LocationContext *CalleeLC = Pred->getLocation().getLocationContext(); const LocationContext *CalleeSF = CalleeLC->getCurrentStackFrame(); const LocationContext *RootLC = (*G.roots_begin())->getLocation().getLocationContext(); @@ -1053,7 +1077,8 @@ void ExprEngine::processCFGBlockEntrance(const BlockEdge &L, // no-inlining policy in the state and enqueuing the new work item on // the list. Replay should almost never fail. Use the stats to catch it // if it does. - if ((!AMgr.NoRetryExhausted && replayWithoutInlining(pred, CalleeLC))) + if ((!AMgr.options.NoRetryExhausted && + replayWithoutInlining(Pred, CalleeLC))) return; NumMaxBlockCountReachedInInlined++; } else @@ -1155,7 +1180,7 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF) { - currentBuilderContext = &BldCtx; + currBldrCtx = &BldCtx; // Check for NULL conditions; e.g. "for(;;)" if (!Condition) { @@ -1238,7 +1263,7 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term, builder.markInfeasible(false); } } - currentBuilderContext = 0; + currBldrCtx = 0; } /// processIndirectGoto - Called by CoreEngine. Used to generate successor @@ -1287,10 +1312,25 @@ void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path /// nodes when the control reaches the end of a function. -void ExprEngine::processEndOfFunction(NodeBuilderContext& BC) { - StateMgr.EndPath(BC.Pred->getState()); +void ExprEngine::processEndOfFunction(NodeBuilderContext& BC, + ExplodedNode *Pred) { + StateMgr.EndPath(Pred->getState()); + ExplodedNodeSet Dst; - getCheckerManager().runCheckersForEndPath(BC, Dst, *this); + if (Pred->getLocationContext()->inTopFrame()) { + // Remove dead symbols. + ExplodedNodeSet AfterRemovedDead; + removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead); + + // Notify checkers. + for (ExplodedNodeSet::iterator I = AfterRemovedDead.begin(), + E = AfterRemovedDead.end(); I != E; ++I) { + getCheckerManager().runCheckersForEndPath(BC, Dst, *I, *this); + } + } else { + getCheckerManager().runCheckersForEndPath(BC, Dst, Pred, *this); + } + Engine.enqueueEndOfFunction(Dst); } @@ -1404,7 +1444,7 @@ void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, ExplodedNode *Pred, ExplodedNodeSet &Dst) { - StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); ProgramStateRef state = Pred->getState(); const LocationContext *LCtx = Pred->getLocationContext(); @@ -1422,7 +1462,7 @@ void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, V = UnknownVal(); } - Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), false, 0, + Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0, ProgramPoint::PostLValueKind); return; } @@ -1434,19 +1474,23 @@ void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, } if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { SVal V = svalBuilder.getFunctionPointer(FD); - Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), false, 0, + Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0, ProgramPoint::PostLValueKind); return; } if (isa<FieldDecl>(D)) { - // FIXME: Compute lvalue of fields. - Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, UnknownVal()), - false, 0, ProgramPoint::PostLValueKind); + // 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. + SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy, + currBldrCtx->blockCount()); + state = state->assume(cast<DefinedOrUnknownSVal>(V), true); + Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0, + ProgramPoint::PostLValueKind); return; } - assert (false && - "ValueDecl support for this ValueDecl not implemented."); + llvm_unreachable("Support for this Decl not implemented."); } /// VisitArraySubscriptExpr - Transfer function for array accesses @@ -1461,7 +1505,7 @@ void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A, ExplodedNodeSet checkerPreStmt; getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this); - StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currentBuilderContext); + StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currBldrCtx); for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(), ei = checkerPreStmt.end(); it != ei; ++it) { @@ -1471,8 +1515,8 @@ void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A, state->getSVal(Idx, LCtx), state->getSVal(Base, LCtx)); assert(A->isGLValue()); - Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V), - false, 0, ProgramPoint::PostLValueKind); + Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V), 0, + ProgramPoint::PostLValueKind); } } @@ -1480,52 +1524,40 @@ void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A, void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, ExplodedNodeSet &TopDst) { - StmtNodeBuilder Bldr(Pred, TopDst, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, TopDst, *currBldrCtx); ExplodedNodeSet Dst; - Decl *member = M->getMemberDecl(); + ValueDecl *Member = M->getMemberDecl(); - if (VarDecl *VD = dyn_cast<VarDecl>(member)) { - assert(M->isGLValue()); + // Handle static member variables and enum constants accessed via + // member syntax. + if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) { Bldr.takeNodes(Pred); - VisitCommonDeclRefExpr(M, VD, Pred, Dst); + VisitCommonDeclRefExpr(M, Member, Pred, Dst); Bldr.addNodes(Dst); return; } - // Handle C++ method calls. - if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(member)) { - Bldr.takeNodes(Pred); - SVal MDVal = svalBuilder.getFunctionPointer(MD); - ProgramStateRef state = - Pred->getState()->BindExpr(M, Pred->getLocationContext(), MDVal); - Bldr.generateNode(M, Pred, state); - return; - } + ProgramStateRef state = Pred->getState(); + const LocationContext *LCtx = Pred->getLocationContext(); + Expr *BaseExpr = M->getBase(); + // Handle C++ method calls. + if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(Member)) { + if (MD->isInstance()) + state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr); - FieldDecl *field = dyn_cast<FieldDecl>(member); - if (!field) // FIXME: skipping member expressions for non-fields - return; + SVal MDVal = svalBuilder.getFunctionPointer(MD); + state = state->BindExpr(M, LCtx, MDVal); - Expr *baseExpr = M->getBase()->IgnoreParens(); - ProgramStateRef state = Pred->getState(); - const LocationContext *LCtx = Pred->getLocationContext(); - SVal baseExprVal = state->getSVal(baseExpr, Pred->getLocationContext()); - if (isa<nonloc::LazyCompoundVal>(baseExprVal) || - isa<nonloc::CompoundVal>(baseExprVal) || - // FIXME: This can originate by conjuring a symbol for an unknown - // temporary struct object, see test/Analysis/fields.c: - // (p = getit()).x - isa<nonloc::SymbolVal>(baseExprVal)) { - Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, UnknownVal())); + Bldr.generateNode(M, Pred, state); return; } - // FIXME: Should we insert some assumption logic in here to determine - // if "Base" is a valid piece of memory? Before we put this assumption - // later when using FieldOffset lvals (which we no longer have). + // Handle regular struct fields / member variables. + state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr); + SVal baseExprVal = state->getSVal(BaseExpr, LCtx); - // For all other cases, compute an lvalue. + FieldDecl *field = cast<FieldDecl>(Member); SVal L = state->getLValue(field, baseExprVal); if (M->isGLValue()) { if (field->getType()->isReferenceType()) { @@ -1535,7 +1567,7 @@ void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, L = UnknownVal(); } - Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), false, 0, + Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), 0, ProgramPoint::PostLValueKind); } else { Bldr.takeNodes(Pred); @@ -1548,40 +1580,48 @@ void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, /// This method is used by evalStore and (soon) VisitDeclStmt, and others. void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, ExplodedNode *Pred, - SVal location, SVal Val, bool atDeclInit) { + SVal location, SVal Val, + bool atDeclInit, const ProgramPoint *PP) { + + const LocationContext *LC = Pred->getLocationContext(); + PostStmt PS(StoreE, LC); + if (!PP) + PP = &PS; // Do a previsit of the bind. ExplodedNodeSet CheckedSet; getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val, - StoreE, *this, - ProgramPoint::PostStmtKind); + StoreE, *this, *PP); + // If the location is not a 'Loc', it will already be handled by + // the checkers. There is nothing left to do. + if (!isa<Loc>(location)) { + Dst = CheckedSet; + return; + } + ExplodedNodeSet TmpDst; - StmtNodeBuilder Bldr(CheckedSet, TmpDst, *currentBuilderContext); + StmtNodeBuilder Bldr(CheckedSet, TmpDst, *currBldrCtx); - const LocationContext *LC = Pred->getLocationContext(); for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); I!=E; ++I) { ExplodedNode *PredI = *I; ProgramStateRef state = PredI->getState(); - - if (atDeclInit) { - const VarRegion *VR = - cast<VarRegion>(cast<loc::MemRegionVal>(location).getRegion()); - - state = state->bindDecl(VR, Val); - } else { - state = state->bindLoc(location, Val); - } - + + // When binding the value, pass on the hint that this is a initialization. + // For initializations, we do not need to inform clients of region + // changes. + state = state->bindLoc(cast<Loc>(location), + Val, /* notifyChanges = */ !atDeclInit); + const MemRegion *LocReg = 0; - if (loc::MemRegionVal *LocRegVal = dyn_cast<loc::MemRegionVal>(&location)) + if (loc::MemRegionVal *LocRegVal = dyn_cast<loc::MemRegionVal>(&location)) { LocReg = LocRegVal->getRegion(); - + } + const ProgramPoint L = PostStore(StoreE, LC, LocReg, 0); - Bldr.generateNode(L, PredI, state, false); + Bldr.generateNode(L, state, PredI); } - Dst.insert(TmpDst); } @@ -1671,7 +1711,7 @@ void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst, if (Tmp.empty()) return; - StmtNodeBuilder Bldr(Tmp, Dst, *currentBuilderContext); + StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx); if (location.isUndef()) return; @@ -1684,8 +1724,7 @@ void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst, // This is important. We must nuke the old binding. Bldr.generateNode(NodeEx, *NI, state->BindExpr(BoundEx, LCtx, UnknownVal()), - false, tag, - ProgramPoint::PostLoadKind); + tag, ProgramPoint::PostLoadKind); } else { if (LoadTy.isNull()) @@ -1693,7 +1732,7 @@ void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst, SVal V = state->getSVal(cast<Loc>(location), LoadTy); Bldr.generateNode(NodeEx, *NI, state->bindExprAndLocation(BoundEx, LCtx, location, V), - false, tag, ProgramPoint::PostLoadKind); + tag, ProgramPoint::PostLoadKind); } } } @@ -1706,7 +1745,7 @@ void ExprEngine::evalLocation(ExplodedNodeSet &Dst, SVal location, const ProgramPointTag *tag, bool isLoad) { - StmtNodeBuilder BldrTop(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx); // Early checks for performance reason. if (location.isUnknown()) { return; @@ -1714,7 +1753,7 @@ void ExprEngine::evalLocation(ExplodedNodeSet &Dst, ExplodedNodeSet Src; BldrTop.takeNodes(Pred); - StmtNodeBuilder Bldr(Pred, Src, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx); if (Pred->getState() != state) { // Associate this new state with an ExplodedNode. // FIXME: If I pass null tag, the graph is incorrect, e.g for @@ -1725,9 +1764,8 @@ void ExprEngine::evalLocation(ExplodedNodeSet &Dst, // instead "int *p" is noted as // "Variable 'p' initialized to a null pointer value" - // FIXME: why is 'tag' not used instead of etag? - static SimpleProgramPointTag etag("ExprEngine: Location"); - Bldr.generateNode(NodeEx, Pred, state, false, &etag); + static SimpleProgramPointTag tag("ExprEngine: Location"); + Bldr.generateNode(NodeEx, Pred, state, &tag); } ExplodedNodeSet Tmp; getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad, @@ -1736,16 +1774,18 @@ void ExprEngine::evalLocation(ExplodedNodeSet &Dst, } std::pair<const ProgramPointTag *, const ProgramPointTag*> -ExprEngine::getEagerlyAssumeTags() { +ExprEngine::geteagerlyAssumeBinOpBifurcationTags() { static SimpleProgramPointTag - EagerlyAssumeTrue("ExprEngine : Eagerly Assume True"), - EagerlyAssumeFalse("ExprEngine : Eagerly Assume False"); - return std::make_pair(&EagerlyAssumeTrue, &EagerlyAssumeFalse); + eagerlyAssumeBinOpBifurcationTrue("ExprEngine : Eagerly Assume True"), + eagerlyAssumeBinOpBifurcationFalse("ExprEngine : Eagerly Assume False"); + return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue, + &eagerlyAssumeBinOpBifurcationFalse); } -void ExprEngine::evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src, - const Expr *Ex) { - StmtNodeBuilder Bldr(Src, Dst, *currentBuilderContext); +void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst, + ExplodedNodeSet &Src, + const Expr *Ex) { + StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx); for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) { ExplodedNode *Pred = *I; @@ -1762,28 +1802,28 @@ void ExprEngine::evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src, nonloc::SymbolVal *SEV = dyn_cast<nonloc::SymbolVal>(&V); if (SEV && SEV->isExpression()) { const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags = - getEagerlyAssumeTags(); + geteagerlyAssumeBinOpBifurcationTags(); // First assume that the condition is true. if (ProgramStateRef StateTrue = state->assume(*SEV, true)) { SVal Val = svalBuilder.makeIntVal(1U, Ex->getType()); StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val); - Bldr.generateNode(Ex, Pred, StateTrue, false, tags.first); + Bldr.generateNode(Ex, Pred, StateTrue, tags.first); } // Next, assume that the condition is false. if (ProgramStateRef StateFalse = state->assume(*SEV, false)) { SVal Val = svalBuilder.makeIntVal(0U, Ex->getType()); StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val); - Bldr.generateNode(Ex, Pred, StateFalse, false, tags.second); + Bldr.generateNode(Ex, Pred, StateFalse, tags.second); } } } } -void ExprEngine::VisitAsmStmt(const AsmStmt *A, ExplodedNode *Pred, - ExplodedNodeSet &Dst) { - StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); +void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred, + ExplodedNodeSet &Dst) { + StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); // We have processed both the inputs and the outputs. All of the outputs // should evaluate to Locs. Nuke all of their values. @@ -1793,7 +1833,7 @@ void ExprEngine::VisitAsmStmt(const AsmStmt *A, ExplodedNode *Pred, ProgramStateRef state = Pred->getState(); - for (AsmStmt::const_outputs_iterator OI = A->begin_outputs(), + for (GCCAsmStmt::const_outputs_iterator OI = A->begin_outputs(), OE = A->end_outputs(); OI != OE; ++OI) { SVal X = state->getSVal(*OI, Pred->getLocationContext()); assert (!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef. @@ -1807,7 +1847,7 @@ void ExprEngine::VisitAsmStmt(const AsmStmt *A, ExplodedNode *Pred, void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred, ExplodedNodeSet &Dst) { - StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); Bldr.generateNode(A, Pred, Pred->getState()); } @@ -1932,7 +1972,7 @@ struct DOTGraphTraits<ExplodedNode*> : if (StmtPoint *L = dyn_cast<StmtPoint>(&Loc)) { const Stmt *S = L->getStmt(); - Out << S->getStmtClassName() << ' ' << (void*) S << ' '; + Out << S->getStmtClassName() << ' ' << (const void*) S << ' '; LangOptions LO; // FIXME. S->printPretty(Out, 0, PrintingPolicy(LO)); printLocation(Out, S->getLocStart()); @@ -2038,8 +2078,8 @@ struct DOTGraphTraits<ExplodedNode*> : } ProgramStateRef state = N->getState(); - Out << "\\|StateID: " << (void*) state.getPtr() - << " NodeID: " << (void*) N << "\\|"; + Out << "\\|StateID: " << (const void*) state.getPtr() + << " NodeID: " << (const void*) N << "\\|"; state->printDOT(Out); Out << "\\l"; diff --git a/lib/StaticAnalyzer/Core/ExprEngineC.cpp b/lib/StaticAnalyzer/Core/ExprEngineC.cpp index 46cba81..00b2f4a 100644 --- a/lib/StaticAnalyzer/Core/ExprEngineC.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngineC.cpp @@ -45,8 +45,8 @@ void ExprEngine::VisitBinaryOperator(const BinaryOperator* B, // EXPERIMENTAL: "Conjured" symbols. // FIXME: Handle structs. if (RightV.isUnknown()) { - unsigned Count = currentBuilderContext->getCurrentBlockCount(); - RightV = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), LCtx, Count); + unsigned Count = currBldrCtx->blockCount(); + RightV = svalBuilder.conjureSymbolVal(0, B->getRHS(), LCtx, Count); } // Simulate the effects of a "store": bind the value of the RHS // to the L-Value represented by the LHS. @@ -57,7 +57,7 @@ void ExprEngine::VisitBinaryOperator(const BinaryOperator* B, } if (!B->isAssignmentOp()) { - StmtNodeBuilder Bldr(*it, Tmp2, *currentBuilderContext); + StmtNodeBuilder Bldr(*it, Tmp2, *currBldrCtx); if (B->isAdditiveOp()) { // If one of the operands is a location, conjure a symbol for the other @@ -65,16 +65,16 @@ void ExprEngine::VisitBinaryOperator(const BinaryOperator* B, // results in an ElementRegion. // TODO: This can be removed after we enable history tracking with // SymSymExpr. - unsigned Count = currentBuilderContext->getCurrentBlockCount(); + unsigned Count = currBldrCtx->blockCount(); if (isa<Loc>(LeftV) && RHS->getType()->isIntegerType() && RightV.isUnknown()) { - RightV = svalBuilder.getConjuredSymbolVal(RHS, LCtx, - RHS->getType(), Count); + RightV = svalBuilder.conjureSymbolVal(RHS, LCtx, RHS->getType(), + Count); } if (isa<Loc>(RightV) && LHS->getType()->isIntegerType() && LeftV.isUnknown()) { - LeftV = svalBuilder.getConjuredSymbolVal(LHS, LCtx, - LHS->getType(), Count); + LeftV = svalBuilder.conjureSymbolVal(LHS, LCtx, LHS->getType(), + Count); } } @@ -145,15 +145,11 @@ void ExprEngine::VisitBinaryOperator(const BinaryOperator* B, SVal LHSVal; if (Result.isUnknown()) { - - unsigned Count = currentBuilderContext->getCurrentBlockCount(); - // The symbolic value is actually for the type of the left-hand side // expression, not the computation type, as this is the value the // LValue on the LHS will bind to. - LHSVal = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), LCtx, - LTy, Count); - + LHSVal = svalBuilder.conjureSymbolVal(0, B->getRHS(), LCtx, LTy, + currBldrCtx->blockCount()); // However, we need to convert the symbol to the computation type. Result = svalBuilder.evalCast(LHSVal, CTy, LTy); } @@ -208,11 +204,10 @@ void ExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred, } ExplodedNodeSet Tmp; - StmtNodeBuilder Bldr(Pred, Tmp, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, Tmp, *currBldrCtx); Bldr.generateNode(BE, Pred, State->BindExpr(BE, Pred->getLocationContext(), V), - false, 0, - ProgramPoint::PostLValueKind); + 0, ProgramPoint::PostLValueKind); // FIXME: Move all post/pre visits to ::Visit(). getCheckerManager().runCheckersForPostStmt(Dst, Tmp, BE, *this); @@ -242,12 +237,14 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, if (const ExplicitCastExpr *ExCast=dyn_cast_or_null<ExplicitCastExpr>(CastE)) T = ExCast->getTypeAsWritten(); - StmtNodeBuilder Bldr(dstPreStmt, Dst, *currentBuilderContext); + StmtNodeBuilder Bldr(dstPreStmt, Dst, *currBldrCtx); for (ExplodedNodeSet::iterator I = dstPreStmt.begin(), E = dstPreStmt.end(); I != E; ++I) { Pred = *I; - + ProgramStateRef state = Pred->getState(); + const LocationContext *LCtx = Pred->getLocationContext(); + switch (CastE->getCastKind()) { case CK_LValueToRValue: llvm_unreachable("LValueToRValue casts handled earlier."); @@ -267,7 +264,10 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, case CK_NonAtomicToAtomic: // True no-ops. case CK_NoOp: - case CK_FunctionToPointerDecay: { + case CK_ConstructorConversion: + case CK_UserDefinedConversion: + case CK_FunctionToPointerDecay: + case CK_BuiltinFnToFnPtr: { // Copy the SVal of Ex to CastE. ProgramStateRef state = Pred->getState(); const LocationContext *LCtx = Pred->getLocationContext(); @@ -276,6 +276,9 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, Bldr.generateNode(CastE, Pred, state); continue; } + case CK_MemberPointerToBoolean: + // FIXME: For now, member pointers are represented by void *. + // FALLTHROUGH case CK_Dependent: case CK_ArrayToPointerDecay: case CK_BitCast: @@ -304,8 +307,6 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, case CK_AnyPointerToBlockPointerCast: case CK_ObjCObjectLValueCast: { // Delegate to SValBuilder to process. - ProgramStateRef state = Pred->getState(); - const LocationContext *LCtx = Pred->getLocationContext(); SVal V = state->getSVal(Ex, LCtx); V = svalBuilder.evalCast(V, T, ExTy); state = state->BindExpr(CastE, LCtx, V); @@ -315,8 +316,6 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, case CK_DerivedToBase: case CK_UncheckedDerivedToBase: { // For DerivedToBase cast, delegate to the store manager. - ProgramStateRef state = Pred->getState(); - const LocationContext *LCtx = Pred->getLocationContext(); SVal val = state->getSVal(Ex, LCtx); val = getStoreManager().evalDerivedToBase(val, CastE); state = state->BindExpr(CastE, LCtx, val); @@ -325,8 +324,6 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, } // Handle C++ dyn_cast. case CK_Dynamic: { - ProgramStateRef state = Pred->getState(); - const LocationContext *LCtx = Pred->getLocationContext(); SVal val = state->getSVal(Ex, LCtx); // Compute the type of the result. @@ -347,7 +344,7 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, if (T->isReferenceType()) { // A bad_cast exception is thrown if input value is a reference. // Currently, we model this, by generating a sink. - Bldr.generateNode(CastE, Pred, state, true); + Bldr.generateSink(CastE, Pred, state); continue; } else { // If the cast fails on a pointer, bind to 0. @@ -356,9 +353,9 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, } else { // If we don't know if the cast succeeded, conjure a new symbol. if (val.isUnknown()) { - DefinedOrUnknownSVal NewSym = svalBuilder.getConjuredSymbolVal(NULL, - CastE, LCtx, resultType, - currentBuilderContext->getCurrentBlockCount()); + DefinedOrUnknownSVal NewSym = + svalBuilder.conjureSymbolVal(0, CastE, LCtx, resultType, + currBldrCtx->blockCount()); state = state->BindExpr(CastE, LCtx, NewSym); } else // Else, bind to the derived region value. @@ -367,27 +364,29 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, Bldr.generateNode(CastE, Pred, state); continue; } + case CK_NullToMemberPointer: { + // FIXME: For now, member pointers are represented by void *. + SVal V = svalBuilder.makeIntValWithPtrWidth(0, true); + state = state->BindExpr(CastE, LCtx, V); + Bldr.generateNode(CastE, Pred, state); + continue; + } // Various C++ casts that are not handled yet. case CK_ToUnion: case CK_BaseToDerived: - case CK_NullToMemberPointer: case CK_BaseToDerivedMemberPointer: case CK_DerivedToBaseMemberPointer: case CK_ReinterpretMemberPointer: - case CK_UserDefinedConversion: - case CK_ConstructorConversion: case CK_VectorSplat: - case CK_MemberPointerToBoolean: case CK_LValueBitCast: { // Recover some path-sensitivty by conjuring a new value. QualType resultType = CastE->getType(); if (CastE->isGLValue()) resultType = getContext().getPointerType(resultType); - const LocationContext *LCtx = Pred->getLocationContext(); - SVal result = svalBuilder.getConjuredSymbolVal(NULL, CastE, LCtx, - resultType, currentBuilderContext->getCurrentBlockCount()); - ProgramStateRef state = Pred->getState()->BindExpr(CastE, LCtx, - result); + SVal result = svalBuilder.conjureSymbolVal(0, CastE, LCtx, + resultType, + currBldrCtx->blockCount()); + state = state->BindExpr(CastE, LCtx, result); Bldr.generateNode(CastE, Pred, state); continue; } @@ -398,7 +397,7 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, void ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL, ExplodedNode *Pred, ExplodedNodeSet &Dst) { - StmtNodeBuilder B(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder B(Pred, Dst, *currBldrCtx); const InitListExpr *ILE = cast<InitListExpr>(CL->getInitializer()->IgnoreParens()); @@ -442,7 +441,7 @@ void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred, ExplodedNodeSet dstPreVisit; getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, DS, *this); - StmtNodeBuilder B(dstPreVisit, Dst, *currentBuilderContext); + StmtNodeBuilder B(dstPreVisit, Dst, *currBldrCtx); const VarDecl *VD = dyn_cast<VarDecl>(D); for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end(); I!=E; ++I) { @@ -478,8 +477,8 @@ void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred, Ty = getContext().getPointerType(Ty); } - InitVal = svalBuilder.getConjuredSymbolVal(NULL, InitEx, LC, Ty, - currentBuilderContext->getCurrentBlockCount()); + InitVal = svalBuilder.conjureSymbolVal(0, InitEx, LC, Ty, + currBldrCtx->blockCount()); } B.takeNodes(N); ExplodedNodeSet Dst2; @@ -488,7 +487,7 @@ void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred, } } else { - B.generateNode(DS, N,state->bindDeclWithNoInit(state->getRegion(VD, LC))); + B.generateNode(DS, N, state); } } } @@ -498,7 +497,7 @@ void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred, assert(B->getOpcode() == BO_LAnd || B->getOpcode() == BO_LOr); - StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); ProgramStateRef state = Pred->getState(); ExplodedNode *N = Pred; @@ -531,10 +530,28 @@ void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred, else { // If there is no terminator, by construction the last statement // in SrcBlock is the value of the enclosing expression. + // However, we still need to constrain that value to be 0 or 1. assert(!SrcBlock->empty()); CFGStmt Elem = cast<CFGStmt>(*SrcBlock->rbegin()); - const Stmt *S = Elem.getStmt(); - X = N->getState()->getSVal(S, Pred->getLocationContext()); + const Expr *RHS = cast<Expr>(Elem.getStmt()); + SVal RHSVal = N->getState()->getSVal(RHS, Pred->getLocationContext()); + + DefinedOrUnknownSVal DefinedRHS = cast<DefinedOrUnknownSVal>(RHSVal); + ProgramStateRef StTrue, StFalse; + llvm::tie(StTrue, StFalse) = N->getState()->assume(DefinedRHS); + if (StTrue) { + if (StFalse) { + // We can't constrain the value to 0 or 1; the best we can do is a cast. + X = getSValBuilder().evalCast(RHSVal, B->getType(), RHS->getType()); + } else { + // The value is known to be true. + X = getSValBuilder().makeIntVal(1, B->getType()); + } + } else { + // The value is known to be false. + assert(StFalse && "Infeasible path!"); + X = getSValBuilder().makeIntVal(0, B->getType()); + } } Bldr.generateNode(B, Pred, state->BindExpr(B, Pred->getLocationContext(), X)); @@ -543,14 +560,15 @@ void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred, void ExprEngine::VisitInitListExpr(const InitListExpr *IE, ExplodedNode *Pred, ExplodedNodeSet &Dst) { - StmtNodeBuilder B(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder B(Pred, Dst, *currBldrCtx); ProgramStateRef state = Pred->getState(); const LocationContext *LCtx = Pred->getLocationContext(); QualType T = getContext().getCanonicalType(IE->getType()); unsigned NumInitElements = IE->getNumInits(); - if (T->isArrayType() || T->isRecordType() || T->isVectorType()) { + if (T->isArrayType() || T->isRecordType() || T->isVectorType() || + T->isAnyComplexType()) { llvm::ImmutableList<SVal> vals = getBasicVals().getEmptySValList(); // Handle base case where the initializer has no elements. @@ -590,7 +608,7 @@ void ExprEngine::VisitGuardedExpr(const Expr *Ex, const Expr *R, ExplodedNode *Pred, ExplodedNodeSet &Dst) { - StmtNodeBuilder B(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder B(Pred, Dst, *currBldrCtx); ProgramStateRef state = Pred->getState(); const LocationContext *LCtx = Pred->getLocationContext(); const CFGBlock *SrcBlock = 0; @@ -631,7 +649,7 @@ void ExprEngine::VisitGuardedExpr(const Expr *Ex, void ExprEngine:: VisitOffsetOfExpr(const OffsetOfExpr *OOE, ExplodedNode *Pred, ExplodedNodeSet &Dst) { - StmtNodeBuilder B(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder B(Pred, Dst, *currBldrCtx); APSInt IV; if (OOE->EvaluateAsInt(IV, getContext())) { assert(IV.getBitWidth() == getContext().getTypeSize(OOE->getType())); @@ -650,7 +668,7 @@ void ExprEngine:: VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex, ExplodedNode *Pred, ExplodedNodeSet &Dst) { - StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); QualType T = Ex->getTypeOfArgument(); @@ -683,7 +701,7 @@ VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex, void ExprEngine::VisitUnaryOperator(const UnaryOperator* U, ExplodedNode *Pred, ExplodedNodeSet &Dst) { - StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); switch (U->getOpcode()) { default: { Bldr.takeNodes(Pred); @@ -816,7 +834,7 @@ void ExprEngine::VisitIncrementDecrementOperator(const UnaryOperator* U, evalLoad(Tmp, U, Ex, Pred, state, loc); ExplodedNodeSet Dst2; - StmtNodeBuilder Bldr(Tmp, Dst2, *currentBuilderContext); + StmtNodeBuilder Bldr(Tmp, Dst2, *currBldrCtx); for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end();I!=E;++I) { state = (*I)->getState(); @@ -840,16 +858,17 @@ void ExprEngine::VisitIncrementDecrementOperator(const UnaryOperator* U, if (U->getType()->isAnyPointerType()) RHS = svalBuilder.makeArrayIndex(1); - else + else if (U->getType()->isIntegralOrEnumerationType()) RHS = svalBuilder.makeIntVal(1, U->getType()); + else + RHS = UnknownVal(); SVal Result = evalBinOp(state, Op, V2, RHS, U->getType()); // Conjure a new symbol if necessary to recover precision. if (Result.isUnknown()){ DefinedOrUnknownSVal SymVal = - svalBuilder.getConjuredSymbolVal(NULL, Ex, LCtx, - currentBuilderContext->getCurrentBlockCount()); + svalBuilder.conjureSymbolVal(0, Ex, LCtx, currBldrCtx->blockCount()); Result = SymVal; // If the value is a location, ++/-- should always preserve diff --git a/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp b/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp index 44a860f..b3baa79 100644 --- a/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp @@ -25,20 +25,28 @@ using namespace ento; void ExprEngine::CreateCXXTemporaryObject(const MaterializeTemporaryExpr *ME, ExplodedNode *Pred, ExplodedNodeSet &Dst) { - StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); const Expr *tempExpr = ME->GetTemporaryExpr()->IgnoreParens(); ProgramStateRef state = Pred->getState(); const LocationContext *LCtx = Pred->getLocationContext(); // Bind the temporary object to the value of the expression. Then bind // the expression to the location of the object. - SVal V = state->getSVal(tempExpr, Pred->getLocationContext()); - - const MemRegion *R = - svalBuilder.getRegionManager().getCXXTempObjectRegion(ME, LCtx); + 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. + const MemRegion *MR = V.getAsRegion(); + if (!MR || !isa<CXXTempObjectRegion>(MR)) { + const MemRegion *R = + svalBuilder.getRegionManager().getCXXTempObjectRegion(ME, LCtx); + + SVal L = loc::MemRegionVal(R); + state = state->bindLoc(L, V); + V = L; + } - state = state->bindLoc(loc::MemRegionVal(R), V); - Bldr.generateNode(ME, Pred, state->BindExpr(ME, LCtx, loc::MemRegionVal(R))); + Bldr.generateNode(ME, Pred, state->BindExpr(ME, LCtx, V)); } void ExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *CE, @@ -53,9 +61,9 @@ void ExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *CE, case CXXConstructExpr::CK_Complete: { // See if we're constructing an existing region by looking at the next // element in the CFG. - const CFGBlock *B = currentBuilderContext->getBlock(); - if (currentStmtIdx + 1 < B->size()) { - CFGElement Next = (*B)[currentStmtIdx+1]; + const CFGBlock *B = currBldrCtx->getBlock(); + if (currStmtIdx + 1 < B->size()) { + CFGElement Next = (*B)[currStmtIdx+1]; // Is this a constructor for a local variable? if (const CFGStmt *StmtElem = dyn_cast<CFGStmt>(&Next)) { @@ -101,8 +109,12 @@ void ExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *CE, // FIXME: This will eventually need to handle new-expressions as well. } - // If we couldn't find an existing region to construct into, we'll just - // generate a symbolic region, which is fine. + // If we couldn't find an existing region to construct into, assume we're + // constructing a temporary. + if (!Target) { + MemRegionManager &MRMgr = getSValBuilder().getRegionManager(); + Target = MRMgr.getCXXTempObjectRegion(CE, LCtx); + } break; } @@ -137,7 +149,7 @@ void ExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *CE, *Call, *this); ExplodedNodeSet DstInvalidated; - StmtNodeBuilder Bldr(DstPreCall, DstInvalidated, *currentBuilderContext); + StmtNodeBuilder Bldr(DstPreCall, DstInvalidated, *currBldrCtx); for (ExplodedNodeSet::iterator I = DstPreCall.begin(), E = DstPreCall.end(); I != E; ++I) defaultEvalCall(Bldr, *I, *Call); @@ -151,6 +163,7 @@ void ExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *CE, void ExprEngine::VisitCXXDestructor(QualType ObjectType, const MemRegion *Dest, const Stmt *S, + bool IsBaseDtor, ExplodedNode *Pred, ExplodedNodeSet &Dst) { const LocationContext *LCtx = Pred->getLocationContext(); @@ -171,7 +184,7 @@ void ExprEngine::VisitCXXDestructor(QualType ObjectType, CallEventManager &CEMgr = getStateManager().getCallEventManager(); CallEventRef<CXXDestructorCall> Call = - CEMgr.getCXXDestructorCall(DtorDecl, S, Dest, State, LCtx); + CEMgr.getCXXDestructorCall(DtorDecl, S, Dest, IsBaseDtor, State, LCtx); PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), Call->getSourceRange().getBegin(), @@ -182,7 +195,7 @@ void ExprEngine::VisitCXXDestructor(QualType ObjectType, *Call, *this); ExplodedNodeSet DstInvalidated; - StmtNodeBuilder Bldr(DstPreCall, DstInvalidated, *currentBuilderContext); + StmtNodeBuilder Bldr(DstPreCall, DstInvalidated, *currBldrCtx); for (ExplodedNodeSet::iterator I = DstPreCall.begin(), E = DstPreCall.end(); I != E; ++I) defaultEvalCall(Bldr, *I, *Call); @@ -198,12 +211,13 @@ void ExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred, // Also, we need to decide how allocators actually work -- they're not // really part of the CXXNewExpr because they happen BEFORE the // CXXConstructExpr subexpression. See PR12014 for some discussion. - StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); - unsigned blockCount = currentBuilderContext->getCurrentBlockCount(); + unsigned blockCount = currBldrCtx->blockCount(); const LocationContext *LCtx = Pred->getLocationContext(); - DefinedOrUnknownSVal symVal = - svalBuilder.getConjuredSymbolVal(0, CNE, LCtx, CNE->getType(), blockCount); + DefinedOrUnknownSVal symVal = svalBuilder.conjureSymbolVal(0, CNE, LCtx, + CNE->getType(), + blockCount); ProgramStateRef State = Pred->getState(); CallEventManager &CEMgr = getStateManager().getCallEventManager(); @@ -215,6 +229,18 @@ void ExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred, // we should be using the usual pre-/(default-)eval-/post-call checks here. State = Call->invalidateRegions(blockCount); + // 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. + // C++11 [basic.stc.dynamic.allocation]p3. + FunctionDecl *FD = CNE->getOperatorNew(); + if (FD && getContext().getLangOpts().CXXExceptions) { + QualType Ty = FD->getType(); + if (const FunctionProtoType *ProtoType = Ty->getAs<FunctionProtoType>()) + if (!ProtoType->isNothrow(getContext())) + State = State->assume(symVal, true); + } + if (CNE->isArray()) { // FIXME: allocating an array requires simulating the constructors. // For now, just return a symbolicated region. @@ -232,11 +258,12 @@ void ExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred, // CXXNewExpr, we need to make sure that the constructed object is not // immediately invalidated here. (The placement call should happen before // the constructor call anyway.) - FunctionDecl *FD = CNE->getOperatorNew(); if (FD && FD->isReservedGlobalPlacementOperator()) { // Non-array placement new should always return the placement location. SVal PlacementLoc = State->getSVal(CNE->getPlacementArg(0), LCtx); - State = State->BindExpr(CNE, LCtx, PlacementLoc); + SVal Result = svalBuilder.evalCast(PlacementLoc, CNE->getType(), + CNE->getPlacementArg(0)->getType()); + State = State->BindExpr(CNE, LCtx, Result); } else { State = State->BindExpr(CNE, LCtx, symVal); } @@ -259,7 +286,7 @@ void ExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred, void ExprEngine::VisitCXXDeleteExpr(const CXXDeleteExpr *CDE, ExplodedNode *Pred, ExplodedNodeSet &Dst) { - StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); ProgramStateRef state = Pred->getState(); Bldr.generateNode(CDE, Pred, state); } @@ -274,18 +301,18 @@ void ExprEngine::VisitCXXCatchStmt(const CXXCatchStmt *CS, } const LocationContext *LCtx = Pred->getLocationContext(); - SVal V = svalBuilder.getConjuredSymbolVal(CS, LCtx, VD->getType(), - currentBuilderContext->getCurrentBlockCount()); + SVal V = svalBuilder.conjureSymbolVal(CS, LCtx, VD->getType(), + currBldrCtx->blockCount()); ProgramStateRef state = Pred->getState(); state = state->bindLoc(state->getLValue(VD, LCtx), V); - StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); Bldr.generateNode(CS, Pred, state); } void ExprEngine::VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred, ExplodedNodeSet &Dst) { - StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); // Get the this object region from StoreManager. const LocationContext *LCtx = Pred->getLocationContext(); diff --git a/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp b/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp index 3b2e4ec..3ead081 100644 --- a/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp @@ -17,19 +17,22 @@ #include "clang/StaticAnalyzer/Core/CheckerManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/AST/CXXInheritance.h" #include "clang/AST/DeclCXX.h" +#include "clang/AST/ParentMap.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/SaveAndRestore.h" -#define CXX_INLINING_ENABLED 1 - using namespace clang; using namespace ento; STATISTIC(NumOfDynamicDispatchPathSplits, "The # of times we split the path due to imprecise dynamic dispatch info"); +STATISTIC(NumInlinedCalls, + "The # of times we inlined a call"); + void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) { // Get the entry block in the CFG of the callee. const StackFrameContext *calleeCtx = CE.getCalleeContext(); @@ -64,35 +67,47 @@ static std::pair<const Stmt*, const StackFrameContext *SF = Node->getLocation().getLocationContext()->getCurrentStackFrame(); - // Back up through the ExplodedGraph until we reach a statement node. + // Back up through the ExplodedGraph until we reach a statement node in this + // stack frame. while (Node) { const ProgramPoint &PP = Node->getLocation(); - if (const StmtPoint *SP = dyn_cast<StmtPoint>(&PP)) { - S = SP->getStmt(); - break; - } else if (const CallExitEnd *CEE = dyn_cast<CallExitEnd>(&PP)) { - S = CEE->getCalleeContext()->getCallSite(); - if (S) + if (PP.getLocationContext()->getCurrentStackFrame() == SF) { + if (const StmtPoint *SP = dyn_cast<StmtPoint>(&PP)) { + S = SP->getStmt(); break; - // If we have an implicit call, we'll probably end up with a - // StmtPoint inside the callee, which is acceptable. - // (It's possible a function ONLY contains implicit calls -- such as an - // implicitly-generated destructor -- so we shouldn't just skip back to - // the CallEnter node and keep going.) + } else if (const CallExitEnd *CEE = dyn_cast<CallExitEnd>(&PP)) { + S = CEE->getCalleeContext()->getCallSite(); + if (S) + break; + + // If there is no statement, this is an implicitly-generated call. + // We'll walk backwards over it and then continue the loop to find + // an actual statement. + const CallEnter *CE; + do { + Node = Node->getFirstPred(); + CE = Node->getLocationAs<CallEnter>(); + } while (!CE || CE->getCalleeContext() != CEE->getCalleeContext()); + + // Continue searching the graph. + } } else if (const CallEnter *CE = dyn_cast<CallEnter>(&PP)) { // If we reached the CallEnter for this function, it has no statements. if (CE->getCalleeContext() == SF) break; } + if (Node->pred_empty()) + return std::pair<const Stmt*, const CFGBlock*>((Stmt*)0, (CFGBlock*)0); + Node = *Node->pred_begin(); } const CFGBlock *Blk = 0; if (S) { // Now, get the enclosing basic block. - while (Node && Node->pred_size() >=1 ) { + while (Node) { const ProgramPoint &PP = Node->getLocation(); if (isa<BlockEdge>(PP) && (PP.getLocationContext()->getCurrentStackFrame() == SF)) { @@ -100,6 +115,9 @@ static std::pair<const Stmt*, Blk = EPP.getDst(); break; } + if (Node->pred_empty()) + return std::pair<const Stmt*, const CFGBlock*>(S, (CFGBlock*)0); + Node = *Node->pred_begin(); } } @@ -107,6 +125,82 @@ static std::pair<const Stmt*, return std::pair<const Stmt*, const CFGBlock*>(S, Blk); } +/// Adjusts a return value when the called function's return type does not +/// match the caller's expression type. This can happen when a dynamic call +/// is devirtualized, and the overridding method has a covariant (more specific) +/// return type than the parent's method. For C++ objects, this means we need +/// to add base casts. +static SVal adjustReturnValue(SVal V, QualType ExpectedTy, QualType ActualTy, + StoreManager &StoreMgr) { + // For now, the only adjustments we handle apply only to locations. + if (!isa<Loc>(V)) + return V; + + // If the types already match, don't do any unnecessary work. + ExpectedTy = ExpectedTy.getCanonicalType(); + ActualTy = ActualTy.getCanonicalType(); + if (ExpectedTy == ActualTy) + return V; + + // No adjustment is needed between Objective-C pointer types. + if (ExpectedTy->isObjCObjectPointerType() && + ActualTy->isObjCObjectPointerType()) + return V; + + // C++ object pointers may need "derived-to-base" casts. + const CXXRecordDecl *ExpectedClass = ExpectedTy->getPointeeCXXRecordDecl(); + const CXXRecordDecl *ActualClass = ActualTy->getPointeeCXXRecordDecl(); + if (ExpectedClass && ActualClass) { + CXXBasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/true, + /*DetectVirtual=*/false); + if (ActualClass->isDerivedFrom(ExpectedClass, Paths) && + !Paths.isAmbiguous(ActualTy->getCanonicalTypeUnqualified())) { + return StoreMgr.evalDerivedToBase(V, Paths.front()); + } + } + + // Unfortunately, Objective-C does not enforce that overridden methods have + // covariant return types, so we can't assert that that never happens. + // Be safe and return UnknownVal(). + return UnknownVal(); +} + +void ExprEngine::removeDeadOnEndOfFunction(NodeBuilderContext& BC, + ExplodedNode *Pred, + ExplodedNodeSet &Dst) { + NodeBuilder Bldr(Pred, Dst, BC); + + // Find the last statement in the function and the corresponding basic block. + const Stmt *LastSt = 0; + const CFGBlock *Blk = 0; + llvm::tie(LastSt, Blk) = getLastStmt(Pred); + if (!Blk || !LastSt) { + return; + } + + // If the last statement is return, everything it references should stay live. + if (isa<ReturnStmt>(LastSt)) + return; + + // Here, we call the Symbol Reaper with 0 stack context telling it to clean up + // everything on the stack. We use LastStmt as a diagnostic statement, with + // which the PreStmtPurgeDead point will be associated. + currBldrCtx = &BC; + removeDead(Pred, Dst, 0, 0, LastSt, + ProgramPoint::PostStmtPurgeDeadSymbolsKind); + currBldrCtx = 0; +} + +static bool wasDifferentDeclUsedForInlining(CallEventRef<> Call, + const StackFrameContext *calleeCtx) { + const Decl *RuntimeCallee = calleeCtx->getDecl(); + const Decl *StaticDecl = Call->getDecl(); + assert(RuntimeCallee); + if (!StaticDecl) + return true; + return RuntimeCallee->getCanonicalDecl() != StaticDecl->getCanonicalDecl(); +} + /// The call exit is simulated with a sequence of nodes, which occur between /// CallExitBegin and CallExitEnd. The following operations occur between the /// two program points: @@ -133,6 +227,11 @@ void ExprEngine::processCallExit(ExplodedNode *CEBNode) { const CFGBlock *Blk = 0; llvm::tie(LastSt, Blk) = getLastStmt(CEBNode); + // Generate a CallEvent /before/ cleaning the state, so that we can get the + // correct value for 'this' (if necessary). + CallEventManager &CEMgr = getStateManager().getCallEventManager(); + CallEventRef<> Call = CEMgr.getCaller(calleeCtx, state); + // Step 2: generate node with bound return value: CEBNode -> BindedRetNode. // If the callee returns an expression, bind its value to CallExpr. @@ -140,6 +239,19 @@ void ExprEngine::processCallExit(ExplodedNode *CEBNode) { if (const ReturnStmt *RS = dyn_cast_or_null<ReturnStmt>(LastSt)) { const LocationContext *LCtx = CEBNode->getLocationContext(); SVal V = state->getSVal(RS, LCtx); + + // Ensure that the return type matches the type of the returned Expr. + if (wasDifferentDeclUsedForInlining(Call, calleeCtx)) { + QualType ReturnedTy = + CallEvent::getDeclaredResultType(calleeCtx->getDecl()); + if (!ReturnedTy.isNull()) { + if (const Expr *Ex = dyn_cast<Expr>(CE)) { + V = adjustReturnValue(V, Ex->getType(), ReturnedTy, + getStoreManager()); + } + } + } + state = state->BindExpr(CE, callerCtx, V); } @@ -149,23 +261,25 @@ void ExprEngine::processCallExit(ExplodedNode *CEBNode) { svalBuilder.getCXXThis(CCE->getConstructor()->getParent(), calleeCtx); SVal ThisV = state->getSVal(This); - // Always bind the region to the CXXConstructExpr. + // If the constructed object is a prvalue, get its bindings. + // Note that we have to be careful here because constructors embedded + // in DeclStmts are not marked as lvalues. + if (!CCE->isGLValue()) + if (const MemRegion *MR = ThisV.getAsRegion()) + if (isa<CXXTempObjectRegion>(MR)) + ThisV = state->getSVal(cast<Loc>(ThisV)); + state = state->BindExpr(CCE, callerCtx, ThisV); } } - // Generate a CallEvent /before/ cleaning the state, so that we can get the - // correct value for 'this' (if necessary). - CallEventManager &CEMgr = getStateManager().getCallEventManager(); - CallEventRef<> Call = CEMgr.getCaller(calleeCtx, state); - // Step 3: BindedRetNode -> CleanedNodes // If we can find a statement and a block in the inlined function, run remove // dead bindings before returning from the call. This is important to ensure // that we report the issues such as leaks in the stack contexts in which // they occurred. ExplodedNodeSet CleanedNodes; - if (LastSt && Blk) { + if (LastSt && Blk && AMgr.options.AnalysisPurgeOpt != PurgeNone) { static SimpleProgramPointTag retValBind("ExprEngine : Bind Return Value"); PostStmt Loc(LastSt, calleeCtx, &retValBind); bool isNew; @@ -175,14 +289,14 @@ void ExprEngine::processCallExit(ExplodedNode *CEBNode) { return; NodeBuilderContext Ctx(getCoreEngine(), Blk, BindedRetNode); - currentBuilderContext = &Ctx; + currBldrCtx = &Ctx; // Here, we call the Symbol Reaper with 0 statement and caller location // context, telling it to clean up everything in the callee's context // (and it's children). We use LastStmt as a diagnostic statement, which // which the PreStmtPurge Dead point will be associated. removeDead(BindedRetNode, CleanedNodes, 0, callerCtx, LastSt, ProgramPoint::PostStmtPurgeDeadSymbolsKind); - currentBuilderContext = 0; + currBldrCtx = 0; } else { CleanedNodes.Add(CEBNode); } @@ -204,9 +318,9 @@ void ExprEngine::processCallExit(ExplodedNode *CEBNode) { // result onto the work list. // CEENode -> Dst -> WorkList NodeBuilderContext Ctx(Engine, calleeCtx->getCallSiteBlock(), CEENode); - SaveAndRestore<const NodeBuilderContext*> NBCSave(currentBuilderContext, + SaveAndRestore<const NodeBuilderContext*> NBCSave(currBldrCtx, &Ctx); - SaveAndRestore<unsigned> CBISave(currentStmtIdx, calleeCtx->getIndex()); + SaveAndRestore<unsigned> CBISave(currStmtIdx, calleeCtx->getIndex()); CallEventRef<> UpdatedCall = Call.cloneWithState(CEEState); @@ -236,14 +350,48 @@ void ExprEngine::processCallExit(ExplodedNode *CEBNode) { } } -static unsigned getNumberStackFrames(const LocationContext *LCtx) { - unsigned count = 0; +void ExprEngine::examineStackFrames(const Decl *D, const LocationContext *LCtx, + bool &IsRecursive, unsigned &StackDepth) { + IsRecursive = false; + StackDepth = 0; + while (LCtx) { - if (isa<StackFrameContext>(LCtx)) - ++count; + if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LCtx)) { + const Decl *DI = SFC->getDecl(); + + // Mark recursive (and mutually recursive) functions and always count + // them when measuring the stack depth. + if (DI == D) { + IsRecursive = true; + ++StackDepth; + LCtx = LCtx->getParent(); + continue; + } + + // Do not count the small functions when determining the stack depth. + AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(DI); + const CFG *CalleeCFG = CalleeADC->getCFG(); + if (CalleeCFG->getNumBlockIDs() > AMgr.options.getAlwaysInlineSize()) + ++StackDepth; + } LCtx = LCtx->getParent(); } - return count; + +} + +static bool IsInStdNamespace(const FunctionDecl *FD) { + const DeclContext *DC = FD->getEnclosingNamespaceContext(); + const NamespaceDecl *ND = dyn_cast<NamespaceDecl>(DC); + if (!ND) + return false; + + while (const DeclContext *Parent = ND->getParent()) { + if (!isa<NamespaceDecl>(Parent)) + break; + ND = cast<NamespaceDecl>(Parent); + } + + return ND->getName() == "std"; } // Determine if we should inline the call. @@ -256,14 +404,18 @@ bool ExprEngine::shouldInlineDecl(const Decl *D, ExplodedNode *Pred) { if (!CalleeCFG) return false; - if (getNumberStackFrames(Pred->getLocationContext()) - == AMgr.InlineMaxStackDepth) + bool IsRecursive = false; + unsigned StackDepth = 0; + examineStackFrames(D, Pred->getLocationContext(), IsRecursive, StackDepth); + if ((StackDepth >= AMgr.options.InlineMaxStackDepth) && + ((CalleeCFG->getNumBlockIDs() > AMgr.options.getAlwaysInlineSize()) + || IsRecursive)) return false; if (Engine.FunctionSummaries->hasReachedMaxBlockCount(D)) return false; - if (CalleeCFG->getNumBlockIDs() > AMgr.InlineMaxFunctionSize) + if (CalleeCFG->getNumBlockIDs() > AMgr.options.InlineMaxFunctionSize) return false; // Do not inline variadic calls (for now). @@ -276,6 +428,21 @@ bool ExprEngine::shouldInlineDecl(const Decl *D, ExplodedNode *Pred) { return false; } + if (getContext().getLangOpts().CPlusPlus) { + if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { + // Conditionally allow the inlining of template functions. + if (!getAnalysisManager().options.mayInlineTemplateFunctions()) + if (FD->getTemplatedKind() != FunctionDecl::TK_NonTemplate) + return false; + + // Conditionally allow the inlining of C++ standard library functions. + if (!getAnalysisManager().options.mayInlineCXXStandardLibrary()) + if (getContext().getSourceManager().isInSystemHeader(FD->getLocation())) + if (IsInStdNamespace(FD)) + return false; + } + } + // It is possible that the live variables analysis cannot be // run. If so, bail out. if (!CalleeADC->getAnalysis<RelaxedLiveVariables>()) @@ -284,26 +451,21 @@ bool ExprEngine::shouldInlineDecl(const Decl *D, ExplodedNode *Pred) { return true; } -/// The GDM component containing the dynamic dispatch bifurcation info. When -/// the exact type of the receiver is not known, we want to explore both paths - -/// one on which we do inline it and the other one on which we don't. This is -/// done to ensure we do not drop coverage. -/// This is the map from the receiver region to a bool, specifying either we -/// consider this region's information precise or not along the given path. -namespace clang { -namespace ento { -enum DynamicDispatchMode { DynamicDispatchModeInlined = 1, - DynamicDispatchModeConservative }; - -struct DynamicDispatchBifurcationMap {}; -typedef llvm::ImmutableMap<const MemRegion*, - unsigned int> DynamicDispatchBifur; -template<> struct ProgramStateTrait<DynamicDispatchBifurcationMap> - : public ProgramStatePartialTrait<DynamicDispatchBifur> { - static void *GDMIndex() { static int index; return &index; } -}; - -}} +// The GDM component containing the dynamic dispatch bifurcation info. When +// the exact type of the receiver is not known, we want to explore both paths - +// one on which we do inline it and the other one on which we don't. This is +// done to ensure we do not drop coverage. +// This is the map from the receiver region to a bool, specifying either we +// consider this region's information precise or not along the given path. +namespace { + enum DynamicDispatchMode { + DynamicDispatchModeInlined = 1, + DynamicDispatchModeConservative + }; +} +REGISTER_TRAIT_WITH_PROGRAMSTATE(DynamicDispatchBifurcationMap, + CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, + unsigned)) bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D, NodeBuilder &Bldr, ExplodedNode *Pred, @@ -314,24 +476,19 @@ bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D, const StackFrameContext *CallerSFC = CurLC->getCurrentStackFrame(); const LocationContext *ParentOfCallee = 0; + AnalyzerOptions &Opts = getAnalysisManager().options; + // FIXME: Refactor this check into a hypothetical CallEvent::canInline. switch (Call.getKind()) { case CE_Function: break; case CE_CXXMember: case CE_CXXMemberOperator: - if (!CXX_INLINING_ENABLED) + if (!Opts.mayInlineCXXMemberFunction(CIMK_MemberFunctions)) return false; break; case CE_CXXConstructor: { - if (!CXX_INLINING_ENABLED) - return false; - - // Only inline constructors and destructors if we built the CFGs for them - // properly. - const AnalysisDeclContext *ADC = CallerSFC->getAnalysisDeclContext(); - if (!ADC->getCFGBuildOptions().AddImplicitDtors || - !ADC->getCFGBuildOptions().AddInitializers) + if (!Opts.mayInlineCXXMemberFunction(CIMK_Constructors)) return false; const CXXConstructorCall &Ctor = cast<CXXConstructorCall>(Call); @@ -341,9 +498,31 @@ bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D, if (Target && isa<ElementRegion>(Target)) return false; + // FIXME: This is a hack. We don't use the correct region for a new + // expression, so if we inline the constructor its result will just be + // thrown away. This short-term hack is tracked in <rdar://problem/12180598> + // and the longer-term possible fix is discussed in PR12014. + const CXXConstructExpr *CtorExpr = Ctor.getOriginExpr(); + if (const Stmt *Parent = CurLC->getParentMap().getParent(CtorExpr)) + if (isa<CXXNewExpr>(Parent)) + return false; + + // Inlining constructors requires including initializers in the CFG. + const AnalysisDeclContext *ADC = CallerSFC->getAnalysisDeclContext(); + assert(ADC->getCFGBuildOptions().AddInitializers && "No CFG initializers"); + (void)ADC; + + // If the destructor is trivial, it's always safe to inline the constructor. + if (Ctor.getDecl()->getParent()->hasTrivialDestructor()) + break; + + // For other types, only inline constructors if destructor inlining is + // also enabled. + if (!Opts.mayInlineCXXMemberFunction(CIMK_Destructors)) + return false; + // FIXME: This is a hack. We don't handle temporary destructors // right now, so we shouldn't inline their constructors. - const CXXConstructExpr *CtorExpr = Ctor.getOriginExpr(); if (CtorExpr->getConstructionKind() == CXXConstructExpr::CK_Complete) if (!Target || !isa<DeclRegion>(Target)) return false; @@ -351,15 +530,13 @@ bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D, break; } case CE_CXXDestructor: { - if (!CXX_INLINING_ENABLED) + if (!Opts.mayInlineCXXMemberFunction(CIMK_Destructors)) return false; - // Only inline constructors and destructors if we built the CFGs for them - // properly. + // Inlining destructors requires building the CFG correctly. const AnalysisDeclContext *ADC = CallerSFC->getAnalysisDeclContext(); - if (!ADC->getCFGBuildOptions().AddImplicitDtors || - !ADC->getCFGBuildOptions().AddInitializers) - return false; + assert(ADC->getCFGBuildOptions().AddImplicitDtors && "No CFG destructors"); + (void)ADC; const CXXDestructorCall &Dtor = cast<CXXDestructorCall>(Call); @@ -371,9 +548,6 @@ bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D, break; } case CE_CXXAllocator: - if (!CXX_INLINING_ENABLED) - return false; - // Do not inline allocators until we model deallocators. // This is unfortunate, but basically necessary for smart pointers and such. return false; @@ -387,8 +561,10 @@ bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D, break; } case CE_ObjCMessage: - if (!(getAnalysisManager().IPAMode == DynamicDispatch || - getAnalysisManager().IPAMode == DynamicDispatchBifurcate)) + if (!Opts.mayInlineObjCMethod()) + return false; + if (!(getAnalysisManager().options.IPAMode == DynamicDispatch || + getAnalysisManager().options.IPAMode == DynamicDispatchBifurcate)) return false; break; } @@ -406,8 +582,8 @@ bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D, AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D); const StackFrameContext *CalleeSFC = CalleeADC->getStackFrame(ParentOfCallee, CallE, - currentBuilderContext->getBlock(), - currentStmtIdx); + currBldrCtx->getBlock(), + currStmtIdx); CallEnter Loc(CallE, CalleeSFC, CurLC); @@ -426,6 +602,12 @@ bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D, // added onto the work list so remove it from the node builder. Bldr.takeNodes(Pred); + NumInlinedCalls++; + + // Mark the decl as visited. + if (VisitedCallees) + VisitedCallees->insert(D); + return true; } @@ -520,8 +702,8 @@ ProgramStateRef ExprEngine::bindReturnValue(const CallEvent &Call, // Conjure a symbol if the return value is unknown. QualType ResultTy = Call.getResultType(); SValBuilder &SVB = getSValBuilder(); - unsigned Count = currentBuilderContext->getCurrentBlockCount(); - SVal R = SVB.getConjuredSymbolVal(0, E, LCtx, ResultTy, Count); + unsigned Count = currBldrCtx->blockCount(); + SVal R = SVB.conjureSymbolVal(0, E, LCtx, ResultTy, Count); return State->BindExpr(E, LCtx, R); } @@ -529,8 +711,7 @@ ProgramStateRef ExprEngine::bindReturnValue(const CallEvent &Call, // a conjured return value. void ExprEngine::conservativeEvalCall(const CallEvent &Call, NodeBuilder &Bldr, ExplodedNode *Pred, ProgramStateRef State) { - unsigned Count = currentBuilderContext->getCurrentBlockCount(); - State = Call.invalidateRegions(Count, State); + State = Call.invalidateRegions(currBldrCtx->blockCount(), State); State = bindReturnValue(Call, Pred->getLocationContext(), State); // And make the result node. @@ -562,13 +743,13 @@ void ExprEngine::defaultEvalCall(NodeBuilder &Bldr, ExplodedNode *Pred, if (D) { if (RD.mayHaveOtherDefinitions()) { // Explore with and without inlining the call. - if (getAnalysisManager().IPAMode == DynamicDispatchBifurcate) { + if (getAnalysisManager().options.IPAMode == DynamicDispatchBifurcate) { BifurcateCall(RD.getDispatchRegion(), *Call, D, Bldr, Pred); return; } // Don't inline if we're not in any dynamic dispatch mode. - if (getAnalysisManager().IPAMode != DynamicDispatch) { + if (getAnalysisManager().options.IPAMode != DynamicDispatch) { conservativeEvalCall(*Call, Bldr, Pred, State); return; } @@ -593,7 +774,7 @@ void ExprEngine::BifurcateCall(const MemRegion *BifurReg, // Check if we've performed the split already - note, we only want // to split the path once per memory region. ProgramStateRef State = Pred->getState(); - const unsigned int *BState = + const unsigned *BState = State->get<DynamicDispatchBifurcationMap>(BifurReg); if (BState) { // If we are on "inline path", keep inlining if possible. @@ -630,7 +811,7 @@ void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred, ExplodedNodeSet dstPreVisit; getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, RS, *this); - StmtNodeBuilder B(dstPreVisit, Dst, *currentBuilderContext); + StmtNodeBuilder B(dstPreVisit, Dst, *currBldrCtx); if (RS->getRetValue()) { for (ExplodedNodeSet::iterator it = dstPreVisit.begin(), diff --git a/lib/StaticAnalyzer/Core/ExprEngineObjC.cpp b/lib/StaticAnalyzer/Core/ExprEngineObjC.cpp index e3bc498..51dda19b 100644 --- a/lib/StaticAnalyzer/Core/ExprEngineObjC.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngineObjC.cpp @@ -28,7 +28,7 @@ void ExprEngine::VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr *Ex, SVal location = state->getLValue(Ex->getDecl(), baseVal); ExplodedNodeSet dstIvar; - StmtNodeBuilder Bldr(Pred, dstIvar, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, dstIvar, *currBldrCtx); Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, location)); // Perform the post-condition check of the ObjCIvarRefExpr and store @@ -88,7 +88,7 @@ void ExprEngine::VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S, evalLocation(dstLocation, S, elem, Pred, state, elementV, NULL, false); ExplodedNodeSet Tmp; - StmtNodeBuilder Bldr(Pred, Tmp, *currentBuilderContext); + StmtNodeBuilder Bldr(Pred, Tmp, *currBldrCtx); for (ExplodedNodeSet::iterator NI = dstLocation.begin(), NE = dstLocation.end(); NI!=NE; ++NI) { @@ -112,8 +112,8 @@ void ExprEngine::VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S, // For now, just 'conjure' up a symbolic value. QualType T = R->getValueType(); assert(Loc::isLocType(T)); - unsigned Count = currentBuilderContext->getCurrentBlockCount(); - SymbolRef Sym = SymMgr.getConjuredSymbol(elem, LCtx, T, Count); + SymbolRef Sym = SymMgr.conjureSymbol(elem, LCtx, T, + currBldrCtx->blockCount()); SVal V = svalBuilder.makeLoc(Sym); hasElems = hasElems->bindLoc(elementV, V); @@ -132,14 +132,6 @@ void ExprEngine::VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S, getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this); } -static bool isSubclass(const ObjCInterfaceDecl *Class, IdentifierInfo *II) { - if (!Class) - return false; - if (Class->getIdentifier() == II) - return true; - return isSubclass(Class->getSuperClass(), II); -} - void ExprEngine::VisitObjCMessage(const ObjCMessageExpr *ME, ExplodedNode *Pred, ExplodedNodeSet &Dst) { @@ -157,7 +149,7 @@ void ExprEngine::VisitObjCMessage(const ObjCMessageExpr *ME, // Proceed with evaluate the message expression. ExplodedNodeSet dstEval; - StmtNodeBuilder Bldr(dstGenericPrevisit, dstEval, *currentBuilderContext); + StmtNodeBuilder Bldr(dstGenericPrevisit, dstEval, *currBldrCtx); for (ExplodedNodeSet::iterator DI = dstGenericPrevisit.begin(), DE = dstGenericPrevisit.end(); DI != DE; ++DI) { @@ -184,68 +176,30 @@ void ExprEngine::VisitObjCMessage(const ObjCMessageExpr *ME, // Check if the "raise" message was sent. assert(notNilState); - if (Msg->getSelector() == RaiseSel) { + if (ObjCNoRet.isImplicitNoReturn(ME)) { // If we raise an exception, for now treat it as a sink. // Eventually we will want to handle exceptions properly. - Bldr.generateNode(currentStmt, Pred, State, true); + Bldr.generateSink(currStmt, Pred, State); continue; } // Generate a transition to non-Nil state. - if (notNilState != State) - Pred = Bldr.generateNode(currentStmt, Pred, notNilState); + if (notNilState != State) { + Pred = Bldr.generateNode(currStmt, Pred, notNilState); + assert(Pred && "Should have cached out already!"); + } } } else { - // Check for special class methods. - if (const ObjCInterfaceDecl *Iface = Msg->getReceiverInterface()) { - if (!NSExceptionII) { - ASTContext &Ctx = getContext(); - NSExceptionII = &Ctx.Idents.get("NSException"); - } - - if (isSubclass(Iface, NSExceptionII)) { - enum { NUM_RAISE_SELECTORS = 2 }; - - // Lazily create a cache of the selectors. - if (!NSExceptionInstanceRaiseSelectors) { - ASTContext &Ctx = getContext(); - NSExceptionInstanceRaiseSelectors = - new Selector[NUM_RAISE_SELECTORS]; - SmallVector<IdentifierInfo*, NUM_RAISE_SELECTORS> II; - unsigned idx = 0; - - // raise:format: - II.push_back(&Ctx.Idents.get("raise")); - II.push_back(&Ctx.Idents.get("format")); - NSExceptionInstanceRaiseSelectors[idx++] = - Ctx.Selectors.getSelector(II.size(), &II[0]); - - // raise:format:arguments: - II.push_back(&Ctx.Idents.get("arguments")); - NSExceptionInstanceRaiseSelectors[idx++] = - Ctx.Selectors.getSelector(II.size(), &II[0]); - } - - Selector S = Msg->getSelector(); - bool RaisesException = false; - for (unsigned i = 0; i < NUM_RAISE_SELECTORS; ++i) { - if (S == NSExceptionInstanceRaiseSelectors[i]) { - RaisesException = true; - break; - } - } - if (RaisesException) { - // If we raise an exception, for now treat it as a sink. - // Eventually we will want to handle exceptions properly. - Bldr.generateNode(currentStmt, Pred, Pred->getState(), true); - continue; - } - - } + // Check for special class methods that are known to not return + // and that we should treat as a sink. + if (ObjCNoRet.isImplicitNoReturn(ME)) { + // If we raise an exception, for now treat it as a sink. + // Eventually we will want to handle exceptions properly. + Bldr.generateSink(currStmt, Pred, Pred->getState()); + continue; } } - // Evaluate the call. defaultEvalCall(Bldr, Pred, *UpdatedMsg); } diff --git a/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp b/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp index 982bcbf..fd875f6 100644 --- a/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp +++ b/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp @@ -17,8 +17,8 @@ #include "clang/AST/Decl.h" #include "clang/Basic/SourceManager.h" #include "clang/Basic/FileManager.h" -#include "clang/Rewrite/Rewriter.h" -#include "clang/Rewrite/HTMLRewrite.h" +#include "clang/Rewrite/Core/Rewriter.h" +#include "clang/Rewrite/Core/HTMLRewrite.h" #include "clang/Lex/Lexer.h" #include "clang/Lex/Preprocessor.h" #include "llvm/Support/FileSystem.h" @@ -189,7 +189,7 @@ void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D, << (*path.rbegin())->getLocation().asLocation().getExpansionColumnNumber() << "</a></td></tr>\n" "<tr><td class=\"rowname\">Description:</td><td>" - << D.getDescription() << "</td></tr>\n"; + << D.getVerboseDescription() << "</td></tr>\n"; // Output any other meta data. @@ -209,15 +209,15 @@ void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D, std::string s; llvm::raw_string_ostream os(s); - const std::string& BugDesc = D.getDescription(); + StringRef BugDesc = D.getVerboseDescription(); if (!BugDesc.empty()) os << "\n<!-- BUGDESC " << BugDesc << " -->\n"; - const std::string& BugType = D.getBugType(); + StringRef BugType = D.getBugType(); if (!BugType.empty()) os << "\n<!-- BUGTYPE " << BugType << " -->\n"; - const std::string& BugCategory = D.getCategory(); + StringRef BugCategory = D.getCategory(); if (!BugCategory.empty()) os << "\n<!-- BUGCATEGORY " << BugCategory << " -->\n"; @@ -267,8 +267,7 @@ void HTMLDiagnostics::ReportDiag(const PathDiagnostic& D, } if (filesMade) { - filesMade->push_back(std::make_pair(StringRef(getName()), - llvm::sys::path::filename(H.str()))); + filesMade->addDiagnostic(D, getName(), llvm::sys::path::filename(H.str())); } // Emit the HTML to disk. diff --git a/lib/StaticAnalyzer/Core/MemRegion.cpp b/lib/StaticAnalyzer/Core/MemRegion.cpp index 62e602a..fab10cf 100644 --- a/lib/StaticAnalyzer/Core/MemRegion.cpp +++ b/lib/StaticAnalyzer/Core/MemRegion.cpp @@ -352,7 +352,7 @@ void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const { } void FunctionTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, - const FunctionDecl *FD, + const NamedDecl *FD, const MemRegion*) { ID.AddInteger(MemRegion::FunctionTextRegionKind); ID.AddPointer(FD); @@ -444,7 +444,7 @@ void MemRegion::dumpToStream(raw_ostream &os) const { } void AllocaRegion::dumpToStream(raw_ostream &os) const { - os << "alloca{" << (void*) Ex << ',' << Cnt << '}'; + os << "alloca{" << (const void*) Ex << ',' << Cnt << '}'; } void FunctionTextRegion::dumpToStream(raw_ostream &os) const { @@ -452,7 +452,7 @@ void FunctionTextRegion::dumpToStream(raw_ostream &os) const { } void BlockTextRegion::dumpToStream(raw_ostream &os) const { - os << "block_code{" << (void*) this << '}'; + os << "block_code{" << (const void*) this << '}'; } void BlockDataRegion::dumpToStream(raw_ostream &os) const { @@ -461,12 +461,12 @@ void BlockDataRegion::dumpToStream(raw_ostream &os) const { void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const { // FIXME: More elaborate pretty-printing. - os << "{ " << (void*) CL << " }"; + os << "{ " << (const void*) CL << " }"; } void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const { os << "temp_object{" << getValueType().getAsString() << ',' - << (void*) Ex << '}'; + << (const void*) Ex << '}'; } void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const { @@ -748,11 +748,11 @@ const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D, } else { assert(D->isStaticLocal()); - const Decl *D = STC->getDecl(); - if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) + const Decl *STCD = STC->getDecl(); + if (isa<FunctionDecl>(STCD) || isa<ObjCMethodDecl>(STCD)) sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind, - getFunctionTextRegion(FD)); - else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) { + getFunctionTextRegion(cast<NamedDecl>(STCD))); + else if (const BlockDecl *BD = dyn_cast<BlockDecl>(STCD)) { const BlockTextRegion *BTR = getBlockTextRegion(BD, C.getCanonicalType(BD->getSignatureAsWritten()->getType()), @@ -761,8 +761,6 @@ const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D, BTR); } else { - // FIXME: For ObjC-methods, we need a new CodeTextRegion. For now - // just use the main global memspace. sReg = getGlobalsRegion(); } } @@ -845,7 +843,7 @@ MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx, } const FunctionTextRegion * -MemRegionManager::getFunctionTextRegion(const FunctionDecl *FD) { +MemRegionManager::getFunctionTextRegion(const NamedDecl *FD) { return getSubRegion<FunctionTextRegion>(FD, getCodeRegion()); } @@ -990,6 +988,10 @@ const MemRegion *MemRegion::getBaseRegion() const { return R; } +bool MemRegion::isSubRegionOf(const MemRegion *R) const { + return false; +} + //===----------------------------------------------------------------------===// // View handling. //===----------------------------------------------------------------------===// @@ -1107,7 +1109,7 @@ RegionOffset MemRegion::getAsOffset() const { // If our base region is symbolic, we don't know what type it really is. // Pretend the type of the symbol is the true dynamic type. // (This will at least be self-consistent for the life of the symbol.) - Ty = SR->getSymbol()->getType(getContext())->getPointeeType(); + Ty = SR->getSymbol()->getType()->getPointeeType(); } const CXXRecordDecl *Child = Ty->getAsCXXRecordDecl(); @@ -1166,8 +1168,12 @@ RegionOffset MemRegion::getAsOffset() const { R = FR->getSuperRegion(); const RecordDecl *RD = FR->getDecl()->getParent(); - if (!RD->isCompleteDefinition()) { + if (RD->isUnion() || !RD->isCompleteDefinition()) { // We cannot compute offset for incomplete type. + // For unions, we could treat everything as offset 0, but we'd rather + // treat each field as a symbolic offset so they aren't stored on top + // of each other, since we depend on things in typed regions actually + // matching their types. SymbolicOffsetBase = R; } diff --git a/lib/StaticAnalyzer/Core/PathDiagnostic.cpp b/lib/StaticAnalyzer/Core/PathDiagnostic.cpp index c849778..0f48d1e 100644 --- a/lib/StaticAnalyzer/Core/PathDiagnostic.cpp +++ b/lib/StaticAnalyzer/Core/PathDiagnostic.cpp @@ -21,6 +21,7 @@ #include "clang/AST/ParentMap.h" #include "clang/AST/StmtCXX.h" #include "llvm/ADT/SmallString.h" +#include "llvm/ADT/StringExtras.h" using namespace clang; using namespace ento; @@ -104,11 +105,12 @@ void PathPieces::flattenTo(PathPieces &Primary, PathPieces &Current, PathDiagnostic::~PathDiagnostic() {} PathDiagnostic::PathDiagnostic(const Decl *declWithIssue, - StringRef bugtype, StringRef desc, - StringRef category) + StringRef bugtype, StringRef verboseDesc, + StringRef shortDesc, StringRef category) : DeclWithIssue(declWithIssue), BugType(StripTrailingDots(bugtype)), - Desc(StripTrailingDots(desc)), + VerboseDesc(StripTrailingDots(verboseDesc)), + ShortDesc(StripTrailingDots(shortDesc)), Category(StripTrailingDots(category)), path(pathImpl) {} @@ -198,6 +200,7 @@ void PathDiagnosticConsumer::HandlePathDiagnostic(PathDiagnostic *D) { if (orig_size <= new_size) return; + assert(orig != D); Diags.RemoveNode(orig); delete orig; } @@ -205,39 +208,151 @@ void PathDiagnosticConsumer::HandlePathDiagnostic(PathDiagnostic *D) { Diags.InsertNode(OwningD.take()); } +static llvm::Optional<bool> comparePath(const PathPieces &X, + const PathPieces &Y); +static llvm::Optional<bool> +compareControlFlow(const PathDiagnosticControlFlowPiece &X, + const PathDiagnosticControlFlowPiece &Y) { + FullSourceLoc XSL = X.getStartLocation().asLocation(); + FullSourceLoc YSL = Y.getStartLocation().asLocation(); + if (XSL != YSL) + return XSL.isBeforeInTranslationUnitThan(YSL); + FullSourceLoc XEL = X.getEndLocation().asLocation(); + FullSourceLoc YEL = Y.getEndLocation().asLocation(); + if (XEL != YEL) + return XEL.isBeforeInTranslationUnitThan(YEL); + return llvm::Optional<bool>(); +} + +static llvm::Optional<bool> +compareMacro(const PathDiagnosticMacroPiece &X, + const PathDiagnosticMacroPiece &Y) { + return comparePath(X.subPieces, Y.subPieces); +} + +static llvm::Optional<bool> +compareCall(const PathDiagnosticCallPiece &X, + const PathDiagnosticCallPiece &Y) { + FullSourceLoc X_CEL = X.callEnter.asLocation(); + FullSourceLoc Y_CEL = Y.callEnter.asLocation(); + if (X_CEL != Y_CEL) + return X_CEL.isBeforeInTranslationUnitThan(Y_CEL); + FullSourceLoc X_CEWL = X.callEnterWithin.asLocation(); + FullSourceLoc Y_CEWL = Y.callEnterWithin.asLocation(); + if (X_CEWL != Y_CEWL) + return X_CEWL.isBeforeInTranslationUnitThan(Y_CEWL); + FullSourceLoc X_CRL = X.callReturn.asLocation(); + FullSourceLoc Y_CRL = Y.callReturn.asLocation(); + if (X_CRL != Y_CRL) + return X_CRL.isBeforeInTranslationUnitThan(Y_CRL); + return comparePath(X.path, Y.path); +} + +static llvm::Optional<bool> comparePiece(const PathDiagnosticPiece &X, + const PathDiagnosticPiece &Y) { + if (X.getKind() != Y.getKind()) + return X.getKind() < Y.getKind(); + + FullSourceLoc XL = X.getLocation().asLocation(); + FullSourceLoc YL = Y.getLocation().asLocation(); + if (XL != YL) + return XL.isBeforeInTranslationUnitThan(YL); + + if (X.getString() != Y.getString()) + return X.getString() < Y.getString(); + + if (X.getRanges().size() != Y.getRanges().size()) + return X.getRanges().size() < Y.getRanges().size(); + + const SourceManager &SM = XL.getManager(); + + for (unsigned i = 0, n = X.getRanges().size(); i < n; ++i) { + SourceRange XR = X.getRanges()[i]; + SourceRange YR = Y.getRanges()[i]; + if (XR != YR) { + if (XR.getBegin() != YR.getBegin()) + return SM.isBeforeInTranslationUnit(XR.getBegin(), YR.getBegin()); + return SM.isBeforeInTranslationUnit(XR.getEnd(), YR.getEnd()); + } + } + + switch (X.getKind()) { + case clang::ento::PathDiagnosticPiece::ControlFlow: + return compareControlFlow(cast<PathDiagnosticControlFlowPiece>(X), + cast<PathDiagnosticControlFlowPiece>(Y)); + case clang::ento::PathDiagnosticPiece::Event: + return llvm::Optional<bool>(); + case clang::ento::PathDiagnosticPiece::Macro: + return compareMacro(cast<PathDiagnosticMacroPiece>(X), + cast<PathDiagnosticMacroPiece>(Y)); + case clang::ento::PathDiagnosticPiece::Call: + return compareCall(cast<PathDiagnosticCallPiece>(X), + cast<PathDiagnosticCallPiece>(Y)); + } + llvm_unreachable("all cases handled"); +} + +static llvm::Optional<bool> comparePath(const PathPieces &X, + const PathPieces &Y) { + if (X.size() != Y.size()) + return X.size() < Y.size(); + for (unsigned i = 0, n = X.size(); i != n; ++i) { + llvm::Optional<bool> b = comparePiece(*X[i], *Y[i]); + if (b.hasValue()) + return b.getValue(); + } + return llvm::Optional<bool>(); +} + +static bool compare(const PathDiagnostic &X, const PathDiagnostic &Y) { + FullSourceLoc XL = X.getLocation().asLocation(); + FullSourceLoc YL = Y.getLocation().asLocation(); + if (XL != YL) + return XL.isBeforeInTranslationUnitThan(YL); + if (X.getBugType() != Y.getBugType()) + return X.getBugType() < Y.getBugType(); + if (X.getCategory() != Y.getCategory()) + return X.getCategory() < Y.getCategory(); + if (X.getVerboseDescription() != Y.getVerboseDescription()) + return X.getVerboseDescription() < Y.getVerboseDescription(); + if (X.getShortDescription() != Y.getShortDescription()) + return X.getShortDescription() < Y.getShortDescription(); + if (X.getDeclWithIssue() != Y.getDeclWithIssue()) { + const Decl *XD = X.getDeclWithIssue(); + if (!XD) + return true; + const Decl *YD = Y.getDeclWithIssue(); + if (!YD) + return false; + SourceLocation XDL = XD->getLocation(); + SourceLocation YDL = YD->getLocation(); + if (XDL != YDL) { + const SourceManager &SM = XL.getManager(); + return SM.isBeforeInTranslationUnit(XDL, YDL); + } + } + PathDiagnostic::meta_iterator XI = X.meta_begin(), XE = X.meta_end(); + PathDiagnostic::meta_iterator YI = Y.meta_begin(), YE = Y.meta_end(); + if (XE - XI != YE - YI) + return (XE - XI) < (YE - YI); + for ( ; XI != XE ; ++XI, ++YI) { + if (*XI != *YI) + return (*XI) < (*YI); + } + llvm::Optional<bool> b = comparePath(X.path, Y.path); + assert(b.hasValue()); + return b.getValue(); +} namespace { struct CompareDiagnostics { // Compare if 'X' is "<" than 'Y'. bool operator()(const PathDiagnostic *X, const PathDiagnostic *Y) const { - // First compare by location - const FullSourceLoc &XLoc = X->getLocation().asLocation(); - const FullSourceLoc &YLoc = Y->getLocation().asLocation(); - if (XLoc < YLoc) - return true; - if (XLoc != YLoc) + if (X == Y) return false; - - // Next, compare by bug type. - StringRef XBugType = X->getBugType(); - StringRef YBugType = Y->getBugType(); - if (XBugType < YBugType) - return true; - if (XBugType != YBugType) - return false; - - // Next, compare by bug description. - StringRef XDesc = X->getDescription(); - StringRef YDesc = Y->getDescription(); - if (XDesc < YDesc) - return true; - if (XDesc != YDesc) - return false; - - // FIXME: Further refine by comparing PathDiagnosticPieces? - return false; - } -}; + return compare(*X, *Y); + } +}; } void PathDiagnosticConsumer::FlushDiagnostics( @@ -250,11 +365,9 @@ void PathDiagnosticConsumer::FlushDiagnostics( std::vector<const PathDiagnostic *> BatchDiags; for (llvm::FoldingSet<PathDiagnostic>::iterator it = Diags.begin(), et = Diags.end(); it != et; ++it) { - BatchDiags.push_back(&*it); + const PathDiagnostic *D = &*it; + BatchDiags.push_back(D); } - - // Clear out the FoldingSet. - Diags.clear(); // Sort the diagnostics so that they are always emitted in a deterministic // order. @@ -269,6 +382,42 @@ void PathDiagnosticConsumer::FlushDiagnostics( const PathDiagnostic *D = *it; delete D; } + + // Clear out the FoldingSet. + Diags.clear(); +} + +void PathDiagnosticConsumer::FilesMade::addDiagnostic(const PathDiagnostic &PD, + StringRef ConsumerName, + StringRef FileName) { + llvm::FoldingSetNodeID NodeID; + NodeID.Add(PD); + void *InsertPos; + PDFileEntry *Entry = FindNodeOrInsertPos(NodeID, InsertPos); + if (!Entry) { + Entry = Alloc.Allocate<PDFileEntry>(); + Entry = new (Entry) PDFileEntry(NodeID); + InsertNode(Entry, InsertPos); + } + + // Allocate persistent storage for the file name. + char *FileName_cstr = (char*) Alloc.Allocate(FileName.size(), 1); + memcpy(FileName_cstr, FileName.data(), FileName.size()); + + Entry->files.push_back(std::make_pair(ConsumerName, + StringRef(FileName_cstr, + FileName.size()))); +} + +PathDiagnosticConsumer::PDFileEntry::ConsumerFiles * +PathDiagnosticConsumer::FilesMade::getFiles(const PathDiagnostic &PD) { + llvm::FoldingSetNodeID NodeID; + NodeID.Add(PD); + void *InsertPos; + PDFileEntry *Entry = FindNodeOrInsertPos(NodeID, InsertPos); + if (!Entry) + return 0; + return &Entry->files; } //===----------------------------------------------------------------------===// @@ -437,8 +586,8 @@ PathDiagnosticLocation const CFGBlock *BSrc = BE->getSrc(); S = BSrc->getTerminatorCondition(); } - else if (const PostStmt *PS = dyn_cast<PostStmt>(&P)) { - S = PS->getStmt(); + else if (const StmtPoint *SP = dyn_cast<StmtPoint>(&P)) { + S = SP->getStmt(); } else if (const PostImplicitCall *PIE = dyn_cast<PostImplicitCall>(&P)) { return PathDiagnosticLocation(PIE->getLocation(), SMng); @@ -453,6 +602,9 @@ PathDiagnosticLocation CEE->getLocationContext(), SMng); } + else { + llvm_unreachable("Unexpected ProgramPoint"); + } return PathDiagnosticLocation(S, SMng, P.getLocationContext()); } @@ -463,21 +615,26 @@ PathDiagnosticLocation assert(N && "Cannot create a location with a null node."); const ExplodedNode *NI = N; + const Stmt *S = 0; while (NI) { ProgramPoint P = NI->getLocation(); - const LocationContext *LC = P.getLocationContext(); if (const StmtPoint *PS = dyn_cast<StmtPoint>(&P)) - return PathDiagnosticLocation(PS->getStmt(), SM, LC); - else if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) { - const Stmt *Term = BE->getSrc()->getTerminator(); - if (Term) { - return PathDiagnosticLocation(Term, SM, LC); - } - } + S = PS->getStmt(); + else if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) + S = BE->getSrc()->getTerminator(); + if (S) + break; NI = NI->succ_empty() ? 0 : *(NI->succ_begin()); } + if (S) { + const LocationContext *LC = NI->getLocationContext(); + if (S->getLocStart().isValid()) + return PathDiagnosticLocation(S, SM, LC); + return PathDiagnosticLocation(getValidSourceLocation(S, LC), SM); + } + return createDeclEnd(N->getLocationContext(), SM); } @@ -587,24 +744,6 @@ void PathDiagnosticLocation::flatten() { } } -PathDiagnosticLocation PathDiagnostic::getLocation() const { - assert(path.size() > 0 && - "getLocation() requires a non-empty PathDiagnostic."); - - PathDiagnosticPiece *p = path.rbegin()->getPtr(); - - while (true) { - if (PathDiagnosticCallPiece *cp = dyn_cast<PathDiagnosticCallPiece>(p)) { - assert(!cp->path.empty()); - p = cp->path.rbegin()->getPtr(); - continue; - } - break; - } - - return p->getLocation(); -} - //===----------------------------------------------------------------------===// // Manipulation of PathDiagnosticCallPieces. //===----------------------------------------------------------------------===// @@ -753,10 +892,9 @@ void PathDiagnosticMacroPiece::Profile(llvm::FoldingSetNodeID &ID) const { } void PathDiagnostic::Profile(llvm::FoldingSetNodeID &ID) const { - if (!path.empty()) - getLocation().Profile(ID); + ID.Add(getLocation()); ID.AddString(BugType); - ID.AddString(Desc); + ID.AddString(VerboseDesc); ID.AddString(Category); } @@ -818,42 +956,16 @@ std::string StackHintGeneratorForSymbol::getMessage(const ExplodedNode *N){ return getMessageForSymbolNotFound(); } -/// TODO: This is copied from clang diagnostics. Maybe we could just move it to -/// some common place. (Same as HandleOrdinalModifier.) -void StackHintGeneratorForSymbol::printOrdinal(unsigned ValNo, - llvm::raw_svector_ostream &Out) { - assert(ValNo != 0 && "ValNo must be strictly positive!"); - - // We could use text forms for the first N ordinals, but the numeric - // forms are actually nicer in diagnostics because they stand out. - Out << ValNo; - - // It is critically important that we do this perfectly for - // user-written sequences with over 100 elements. - switch (ValNo % 100) { - case 11: - case 12: - case 13: - Out << "th"; return; - default: - switch (ValNo % 10) { - case 1: Out << "st"; return; - case 2: Out << "nd"; return; - case 3: Out << "rd"; return; - default: Out << "th"; return; - } - } -} - std::string StackHintGeneratorForSymbol::getMessageForArg(const Expr *ArgE, - unsigned ArgIndex) { + unsigned ArgIndex) { + // Printed parameters start at 1, not 0. + ++ArgIndex; + SmallString<200> buf; llvm::raw_svector_ostream os(buf); - os << Msg << " via "; - // Printed parameters start at 1, not 0. - printOrdinal(++ArgIndex, os); - os << " parameter"; + os << Msg << " via " << ArgIndex << llvm::getOrdinalSuffix(ArgIndex) + << " parameter"; return os.str(); } diff --git a/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp b/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp index d5fdd9d..17ef4cf 100644 --- a/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp +++ b/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp @@ -13,8 +13,9 @@ #include "clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h" #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" -#include "clang/Basic/SourceManager.h" #include "clang/Basic/FileManager.h" +#include "clang/Basic/SourceManager.h" +#include "clang/Basic/Version.h" #include "clang/Lex/Preprocessor.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Support/Casting.h" @@ -47,7 +48,6 @@ namespace { PathGenerationScheme getGenerationScheme() const { return Extensive; } bool supportsLogicalOpControlFlow() const { return true; } bool supportsAllBlockEdges() const { return true; } - virtual bool useVerboseDescription() const { return false; } virtual bool supportsCrossFileDiagnostics() const { return SupportsCrossFileDiagnostics; } @@ -247,6 +247,7 @@ static void ReportEvent(raw_ostream &o, const PathDiagnosticPiece& P, // Output the short text. // FIXME: Really use a short string. Indent(o, indent) << "<key>message</key>\n"; + Indent(o, indent); EmitString(o, P.getString()) << '\n'; // Finish up. @@ -409,10 +410,13 @@ void PlistDiagnostics::FlushDiagnosticsImpl( "<plist version=\"1.0\">\n"; // Write the root object: a <dict> containing... + // - "clang_version", the string representation of clang version // - "files", an <array> mapping from FIDs to file names // - "diagnostics", an <array> containing the path diagnostics - o << "<dict>\n" - " <key>files</key>\n" + o << "<dict>\n" << + " <key>clang_version</key>\n"; + EmitString(o, getClangFullVersion()) << '\n'; + o << " <key>files</key>\n" " <array>\n"; for (SmallVectorImpl<FileID>::iterator I=Fids.begin(), E=Fids.end(); @@ -443,7 +447,7 @@ void PlistDiagnostics::FlushDiagnosticsImpl( // Output the bug type and bug category. o << " <key>description</key>"; - EmitString(o, D->getDescription()) << '\n'; + EmitString(o, D->getShortDescription()) << '\n'; o << " <key>category</key>"; EmitString(o, D->getCategory()) << '\n'; o << " <key>type</key>"; @@ -499,19 +503,23 @@ void PlistDiagnostics::FlushDiagnosticsImpl( // Output the diagnostic to the sub-diagnostic client, if any. if (!filesMade->empty()) { StringRef lastName; - for (FilesMade::iterator I = filesMade->begin(), E = filesMade->end(); - I != E; ++I) { - StringRef newName = I->first; - if (newName != lastName) { - if (!lastName.empty()) - o << " </array>\n"; - lastName = newName; - o << " <key>" << lastName << "_files</key>\n"; - o << " <array>\n"; + PDFileEntry::ConsumerFiles *files = filesMade->getFiles(*D); + if (files) { + for (PDFileEntry::ConsumerFiles::const_iterator CI = files->begin(), + CE = files->end(); CI != CE; ++CI) { + StringRef newName = CI->first; + if (newName != lastName) { + if (!lastName.empty()) { + o << " </array>\n"; + } + lastName = newName; + o << " <key>" << lastName << "_files</key>\n"; + o << " <array>\n"; + } + o << " <string>" << CI->second << "</string>\n"; } - o << " <string>" << I->second << "</string>\n"; + o << " </array>\n"; } - o << " </array>\n"; } // Close up the entry. @@ -521,10 +529,5 @@ void PlistDiagnostics::FlushDiagnosticsImpl( o << " </array>\n"; // Finish. - o << "</dict>\n</plist>"; - - if (filesMade) { - StringRef Name(getName()); - filesMade->push_back(std::make_pair(Name, OutputFile)); - } + o << "</dict>\n</plist>"; } diff --git a/lib/StaticAnalyzer/Core/ProgramState.cpp b/lib/StaticAnalyzer/Core/ProgramState.cpp index 2000338..b49a11e 100644 --- a/lib/StaticAnalyzer/Core/ProgramState.cpp +++ b/lib/StaticAnalyzer/Core/ProgramState.cpp @@ -22,10 +22,6 @@ using namespace clang; using namespace ento; -// Give the vtable for ConstraintManager somewhere to live. -// FIXME: Move this elsewhere. -ConstraintManager::~ConstraintManager() {} - namespace clang { namespace ento { /// Increments the number of times this state is referenced. @@ -75,8 +71,8 @@ ProgramStateManager::ProgramStateManager(ASTContext &Ctx, StoreManagerCreator CreateSMgr, ConstraintManagerCreator CreateCMgr, llvm::BumpPtrAllocator &alloc, - SubEngine &SubEng) - : Eng(&SubEng), EnvMgr(alloc), GDMFactory(alloc), + SubEngine *SubEng) + : Eng(SubEng), EnvMgr(alloc), GDMFactory(alloc), svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)), CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) { StoreMgr.reset((*CreateSMgr)(*this)); @@ -110,47 +106,25 @@ ProgramStateManager::removeDeadBindings(ProgramStateRef state, SymReaper); NewState.setStore(newStore); SymReaper.setReapedStore(newStore); - - return getPersistentState(NewState); -} - -ProgramStateRef ProgramStateManager::MarshalState(ProgramStateRef state, - const StackFrameContext *InitLoc) { - // make up an empty state for now. - ProgramState State(this, - EnvMgr.getInitialEnvironment(), - StoreMgr->getInitialStore(InitLoc), - GDMFactory.getEmptyMap()); - return getPersistentState(State); + ProgramStateRef Result = getPersistentState(NewState); + return ConstraintMgr->removeDeadBindings(Result, SymReaper); } ProgramStateRef ProgramState::bindCompoundLiteral(const CompoundLiteralExpr *CL, const LocationContext *LC, SVal V) const { const StoreRef &newStore = - getStateManager().StoreMgr->BindCompoundLiteral(getStore(), CL, LC, V); + getStateManager().StoreMgr->bindCompoundLiteral(getStore(), CL, LC, V); return makeWithStore(newStore); } -ProgramStateRef ProgramState::bindDecl(const VarRegion* VR, SVal IVal) const { - const StoreRef &newStore = - getStateManager().StoreMgr->BindDecl(getStore(), VR, IVal); - return makeWithStore(newStore); -} - -ProgramStateRef ProgramState::bindDeclWithNoInit(const VarRegion* VR) const { - const StoreRef &newStore = - getStateManager().StoreMgr->BindDeclWithNoInit(getStore(), VR); - return makeWithStore(newStore); -} - -ProgramStateRef ProgramState::bindLoc(Loc LV, SVal V) const { +ProgramStateRef ProgramState::bindLoc(Loc LV, SVal V, bool notifyChanges) const { ProgramStateManager &Mgr = getStateManager(); ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(), LV, V)); const MemRegion *MR = LV.getAsRegion(); - if (MR && Mgr.getOwningEngine()) + if (MR && Mgr.getOwningEngine() && notifyChanges) return Mgr.getOwningEngine()->processRegionChange(newState, MR); return newState; @@ -204,11 +178,12 @@ ProgramState::invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions, return makeWithStore(newStore); } -ProgramStateRef ProgramState::unbindLoc(Loc LV) const { +ProgramStateRef ProgramState::killBinding(Loc LV) const { assert(!isa<loc::MemRegionVal>(LV) && "Use invalidateRegion instead."); Store OldStore = getStore(); - const StoreRef &newStore = getStateManager().StoreMgr->Remove(OldStore, LV); + const StoreRef &newStore = + getStateManager().StoreMgr->killBinding(OldStore, LV); if (newStore.getStore() == OldStore) return this; @@ -249,7 +224,9 @@ SVal ProgramState::getSVal(Loc location, QualType T) const { // about). if (!T.isNull()) { if (SymbolRef sym = V.getAsSymbol()) { - if (const llvm::APSInt *Int = getSymVal(sym)) { + if (const llvm::APSInt *Int = getStateManager() + .getConstraintManager() + .getSymVal(this, sym)) { // FIXME: Because we don't correctly model (yet) sign-extension // and truncation of symbolic values, we need to convert // the integer value to the correct signedness and bitwidth. @@ -710,7 +687,9 @@ bool ProgramState::isTainted(SymbolRef Sym, TaintTagType Kind) const { bool Tainted = false; for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), SE =Sym->symbol_end(); SI != SE; ++SI) { - assert(isa<SymbolData>(*SI)); + if (!isa<SymbolData>(*SI)) + continue; + const TaintTagType *Tag = get<TaintMap>(*SI); Tainted = (Tag && *Tag == Kind); @@ -734,15 +713,10 @@ bool ProgramState::isTainted(SymbolRef Sym, TaintTagType Kind) const { } /// The GDM component containing the dynamic type info. This is a map from a -/// symbol to it's most likely type. -namespace clang { -namespace ento { -typedef llvm::ImmutableMap<const MemRegion *, DynamicTypeInfo> DynamicTypeMap; -template<> struct ProgramStateTrait<DynamicTypeMap> - : public ProgramStatePartialTrait<DynamicTypeMap> { - static void *GDMIndex() { static int index; return &index; } -}; -}} +/// symbol to its most likely type. +REGISTER_TRAIT_WITH_PROGRAMSTATE(DynamicTypeMap, + CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, + DynamicTypeInfo)) DynamicTypeInfo ProgramState::getDynamicTypeInfo(const MemRegion *Reg) const { Reg = Reg->StripCasts(); @@ -758,7 +732,7 @@ DynamicTypeInfo ProgramState::getDynamicTypeInfo(const MemRegion *Reg) const { if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) { SymbolRef Sym = SR->getSymbol(); - return DynamicTypeInfo(Sym->getType(getStateManager().getContext())); + return DynamicTypeInfo(Sym->getType()); } return DynamicTypeInfo(); diff --git a/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp b/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp index 550404a..411094b 100644 --- a/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ b/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -24,9 +24,6 @@ using namespace clang; using namespace ento; -namespace { class ConstraintRange {}; } -static int ConstraintRangeIndex = 0; - /// A Range represents the closed range [from, to]. The caller must /// guarantee that from <= to. Note that Range is immutable, so as not /// to subvert RangeSet's immutability. @@ -280,23 +277,15 @@ public: }; } // end anonymous namespace -typedef llvm::ImmutableMap<SymbolRef,RangeSet> ConstraintRangeTy; - -namespace clang { -namespace ento { -template<> -struct ProgramStateTrait<ConstraintRange> - : public ProgramStatePartialTrait<ConstraintRangeTy> { - static inline void *GDMIndex() { return &ConstraintRangeIndex; } -}; -} -} +REGISTER_TRAIT_WITH_PROGRAMSTATE(ConstraintRange, + CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, + RangeSet)) namespace { class RangeConstraintManager : public SimpleConstraintManager{ RangeSet GetRange(ProgramStateRef state, SymbolRef sym); public: - RangeConstraintManager(SubEngine &subengine, BasicValueFactory &BVF) + RangeConstraintManager(SubEngine *subengine, BasicValueFactory &BVF) : SimpleConstraintManager(subengine, BVF) {} ProgramStateRef assumeSymNE(ProgramStateRef state, SymbolRef sym, @@ -324,12 +313,7 @@ public: const llvm::APSInt& Adjustment); const llvm::APSInt* getSymVal(ProgramStateRef St, SymbolRef sym) const; - - // FIXME: Refactor into SimpleConstraintManager? - bool isEqual(ProgramStateRef St, SymbolRef sym, const llvm::APSInt& V) const { - const llvm::APSInt *i = getSymVal(St, sym); - return i ? *i == V : false; - } + ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym); ProgramStateRef removeDeadBindings(ProgramStateRef St, SymbolReaper& SymReaper); @@ -343,7 +327,7 @@ private: } // end anonymous namespace ConstraintManager * -ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, SubEngine &Eng) { +ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, SubEngine *Eng) { return new RangeConstraintManager(Eng, StMgr.getBasicVals()); } @@ -353,6 +337,30 @@ const llvm::APSInt* RangeConstraintManager::getSymVal(ProgramStateRef St, return T ? T->getConcreteValue() : NULL; } +ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State, + SymbolRef Sym) { + const RangeSet *Ranges = State->get<ConstraintRange>(Sym); + + // If we don't have any information about this symbol, it's underconstrained. + if (!Ranges) + return ConditionTruthVal(); + + // If we have a concrete value, see if it's zero. + if (const llvm::APSInt *Value = Ranges->getConcreteValue()) + return *Value == 0; + + BasicValueFactory &BV = getBasicVals(); + APSIntType IntType = BV.getAPSIntType(Sym->getType()); + llvm::APSInt Zero = IntType.getZeroValue(); + + // Check if zero is in the set of possible values. + if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty()) + return false; + + // Zero is a possible value, but it is not the /only/ possible value. + return ConditionTruthVal(); +} + /// Scan all symbols referenced by the constraints. If the symbol is not alive /// as marked in LSymbols, mark it as dead in DSymbols. ProgramStateRef @@ -379,8 +387,18 @@ RangeConstraintManager::GetRange(ProgramStateRef state, SymbolRef sym) { // Lazily generate a new RangeSet representing all possible values for the // given symbol type. BasicValueFactory &BV = getBasicVals(); - QualType T = sym->getType(BV.getContext()); - return RangeSet(F, BV.getMinValue(T), BV.getMaxValue(T)); + QualType T = sym->getType(); + + 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()); + } + + return Result; } //===------------------------------------------------------------------------=== diff --git a/lib/StaticAnalyzer/Core/RegionStore.cpp b/lib/StaticAnalyzer/Core/RegionStore.cpp index bc4e4bb..aed994d 100644 --- a/lib/StaticAnalyzer/Core/RegionStore.cpp +++ b/lib/StaticAnalyzer/Core/RegionStore.cpp @@ -15,9 +15,6 @@ // //===----------------------------------------------------------------------===// #include "clang/AST/CharUnits.h" -#include "clang/AST/DeclCXX.h" -#include "clang/AST/ExprCXX.h" -#include "clang/AST/CXXInheritance.h" #include "clang/Analysis/Analyses/LiveVariables.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Basic/TargetInfo.h" @@ -193,19 +190,6 @@ public: /// casts from arrays to pointers. SVal ArrayToPointer(Loc Array); - /// For DerivedToBase casts, create a CXXBaseObjectRegion and return it. - virtual SVal evalDerivedToBase(SVal derived, QualType basePtrType); - - /// \brief Evaluates C++ dynamic_cast cast. - /// The callback may result in the following 3 scenarios: - /// - Successful cast (ex: derived is subclass of base). - /// - Failed cast (ex: derived is definitely not a subclass of base). - /// - We don't know (base is a symbolic region and we don't have - /// enough info to determine if the cast will succeed at run time). - /// The function returns an SVal representing the derived class; it's - /// valid only if Failed flag is set to false. - virtual SVal evalDynamicCast(SVal base, QualType derivedPtrType,bool &Failed); - StoreRef getInitialStore(const LocationContext *InitLoc) { return StoreRef(RBFactory.getEmptyMap().getRootWithoutRetain(), *this); } @@ -244,7 +228,7 @@ public: // Made public for helper classes. RegionBindings removeBinding(RegionBindings B, BindingKey K); RegionBindings removeBinding(RegionBindings B, const MemRegion *R, - BindingKey::Kind k); + BindingKey::Kind k); RegionBindings removeBinding(RegionBindings B, const MemRegion *R) { return removeBinding(removeBinding(B, R, BindingKey::Direct), R, @@ -266,15 +250,20 @@ public: // Part of public interface to class. .getRootWithoutRetain(), *this); } - StoreRef BindCompoundLiteral(Store store, const CompoundLiteralExpr *CL, + /// \brief Create a new store that binds a value to a compound literal. + /// + /// \param ST The original store whose bindings are the basis for the new + /// store. + /// + /// \param CL The compound literal to bind (the binding key). + /// + /// \param LC The LocationContext for the binding. + /// + /// \param V The value to bind to the compound literal. + StoreRef bindCompoundLiteral(Store ST, + const CompoundLiteralExpr *CL, const LocationContext *LC, SVal V); - StoreRef BindDecl(Store store, const VarRegion *VR, SVal InitVal); - - StoreRef BindDeclWithNoInit(Store store, const VarRegion *) { - return StoreRef(store, *this); - } - /// BindStruct - Bind a compound value to a structure. StoreRef BindStruct(Store store, const TypedValueRegion* R, SVal V); @@ -287,7 +276,10 @@ public: // Part of public interface to class. /// as a Default binding. StoreRef BindAggregate(Store store, const TypedRegion *R, SVal DefaultVal); - StoreRef Remove(Store store, Loc LV); + /// \brief Create a new store with the specified binding removed. + /// \param ST the original store, that is the basis for the new store. + /// \param L the location whose binding should be removed. + StoreRef killBinding(Store ST, Loc L); void incrementReferenceCount(Store store) { GetRegionBindings(store).manualRetain(); @@ -477,12 +469,8 @@ public: } bool AddToWorkList(const MemRegion *R, const ClusterBindings *C) { - if (C) { - if (Visited.count(C)) - return false; - Visited.insert(C); - } - + if (C && !Visited.insert(C)) + return false; WL.push_back(R); return true; } @@ -534,6 +522,46 @@ bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R, return true; } +static inline bool isUnionField(const FieldRegion *FR) { + return FR->getDecl()->getParent()->isUnion(); +} + +typedef SmallVector<const FieldDecl *, 8> FieldVector; + +void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields) { + assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); + + const MemRegion *Base = K.getConcreteOffsetRegion(); + const MemRegion *R = K.getRegion(); + + while (R != Base) { + if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) + if (!isUnionField(FR)) + Fields.push_back(FR->getDecl()); + + R = cast<SubRegion>(R)->getSuperRegion(); + } +} + +static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields) { + assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); + + if (Fields.empty()) + return true; + + FieldVector FieldsInBindingKey; + getSymbolicOffsetFields(K, FieldsInBindingKey); + + ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size(); + if (Delta >= 0) + return std::equal(FieldsInBindingKey.begin() + Delta, + FieldsInBindingKey.end(), + Fields.begin()); + else + return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(), + Fields.begin() - Delta); +} + RegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B, const SubRegion *R) { BindingKey SRKey = BindingKey::Make(R, BindingKey::Default); @@ -543,10 +571,12 @@ RegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B, return RBFactory.remove(B, R); } - if (SRKey.hasSymbolicOffset()) { - const SubRegion *Base = cast<SubRegion>(SRKey.getConcreteOffsetRegion()); - B = removeSubRegionBindings(B, Base); - return addBinding(B, Base, BindingKey::Default, UnknownVal()); + FieldVector FieldsInSymbolicSubregions; + bool HasSymbolicOffset = SRKey.hasSymbolicOffset(); + if (HasSymbolicOffset) { + getSymbolicOffsetFields(SRKey, FieldsInSymbolicSubregions); + R = cast<SubRegion>(SRKey.getConcreteOffsetRegion()); + SRKey = BindingKey::Make(R, BindingKey::Default); } // This assumes the region being invalidated is char-aligned. This isn't @@ -574,11 +604,17 @@ RegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B, I != E; ++I) { BindingKey NextKey = I.getKey(); if (NextKey.getRegion() == SRKey.getRegion()) { + // FIXME: This doesn't catch the case where we're really invalidating a + // region with a symbolic offset. Example: + // R: points[i].y + // Next: points[0].x + if (NextKey.getOffset() > SRKey.getOffset() && NextKey.getOffset() - SRKey.getOffset() < Length) { // Case 1: The next binding is inside the region we're invalidating. // Remove it. Result = CBFactory.remove(Result, NextKey); + } else if (NextKey.getOffset() == SRKey.getOffset()) { // Case 2: The next binding is at the same offset as the region we're // invalidating. In this case, we need to leave default bindings alone, @@ -589,6 +625,7 @@ RegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B, if (NextKey.isDirect()) Result = CBFactory.remove(Result, NextKey); } + } else if (NextKey.hasSymbolicOffset()) { const MemRegion *Base = NextKey.getConcreteOffsetRegion(); if (R->isSubRegionOf(Base)) { @@ -596,16 +633,24 @@ RegionBindings RegionStoreManager::removeSubRegionBindings(RegionBindings B, // its concrete region. We don't know if the binding is still valid, so // we'll be conservative and remove it. if (NextKey.isDirect()) - Result = CBFactory.remove(Result, NextKey); + if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) + Result = CBFactory.remove(Result, NextKey); } else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) { // Case 4: The next key is symbolic, but we changed a known // super-region. In this case the binding is certainly no longer valid. if (R == Base || BaseSR->isSubRegionOf(R)) - Result = CBFactory.remove(Result, NextKey); + if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) + Result = CBFactory.remove(Result, NextKey); } } } + // If we're invalidating a region with a symbolic offset, we need to make sure + // we don't treat the base region as uninitialized anymore. + // FIXME: This isn't very precise; see the example in the loop. + if (HasSymbolicOffset) + Result = CBFactory.add(Result, SRKey, UnknownVal()); + if (Result.isEmpty()) return RBFactory.remove(B, ClusterHead); return RBFactory.add(B, ClusterHead, Result); @@ -724,7 +769,7 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { // Invalidate the region by setting its default value to // conjured symbol. The type of the symbol is irrelavant. DefinedOrUnknownSVal V = - svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); + svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); B = RM.addBinding(B, baseR, BindingKey::Default, V); return; } @@ -739,8 +784,8 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { if (T->isStructureOrClassType()) { // Invalidate the region by setting its default value to // conjured symbol. The type of the symbol is irrelavant. - DefinedOrUnknownSVal V = - svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); + DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, + Ctx.IntTy, Count); B = RM.addBinding(B, baseR, BindingKey::Default, V); return; } @@ -748,7 +793,7 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { if (const ArrayType *AT = Ctx.getAsArrayType(T)) { // Set the default value of the array to conjured symbol. DefinedOrUnknownSVal V = - svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, + svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, AT->getElementType(), Count); B = RM.addBinding(B, baseR, BindingKey::Default, V); return; @@ -764,8 +809,8 @@ void invalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { } - DefinedOrUnknownSVal V = svalBuilder.getConjuredSymbolVal(baseR, Ex, LCtx, - T,Count); + DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, + T,Count); assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); B = RM.addBinding(B, baseR, BindingKey::Direct, V); } @@ -779,10 +824,9 @@ RegionBindings RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, // Bind the globals memory space to a new symbol that we will use to derive // the bindings for all globals. const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K); - SVal V = - svalBuilder.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, Ex, LCtx, - /* symbol type, doesn't matter */ Ctx.IntTy, - Count); + SVal V = svalBuilder.conjureSymbolVal(/* SymbolTag = */ (const void*) GS, Ex, LCtx, + /* type does not matter */ Ctx.IntTy, + Count); B = removeBinding(B, GS); B = addBinding(B, BindingKey::Make(GS, BindingKey::Default), V); @@ -897,103 +941,6 @@ SVal RegionStoreManager::ArrayToPointer(Loc Array) { return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR, Ctx)); } -// This mirrors Type::getCXXRecordDeclForPointerType(), but there doesn't -// appear to be another need for this in the rest of the codebase. -static const CXXRecordDecl *GetCXXRecordDeclForReferenceType(QualType Ty) { - if (const ReferenceType *RT = Ty->getAs<ReferenceType>()) - if (const RecordType *RCT = RT->getPointeeType()->getAs<RecordType>()) - return dyn_cast<CXXRecordDecl>(RCT->getDecl()); - return 0; -} - -SVal RegionStoreManager::evalDerivedToBase(SVal derived, QualType baseType) { - const CXXRecordDecl *baseDecl; - - if (baseType->isPointerType()) - baseDecl = baseType->getCXXRecordDeclForPointerType(); - else if (baseType->isReferenceType()) - baseDecl = GetCXXRecordDeclForReferenceType(baseType); - else - baseDecl = baseType->getAsCXXRecordDecl(); - - assert(baseDecl && "not a CXXRecordDecl?"); - - loc::MemRegionVal *derivedRegVal = dyn_cast<loc::MemRegionVal>(&derived); - if (!derivedRegVal) - return derived; - - const MemRegion *baseReg = - MRMgr.getCXXBaseObjectRegion(baseDecl, derivedRegVal->getRegion()); - - return loc::MemRegionVal(baseReg); -} - -SVal RegionStoreManager::evalDynamicCast(SVal base, QualType derivedType, - bool &Failed) { - Failed = false; - - loc::MemRegionVal *baseRegVal = dyn_cast<loc::MemRegionVal>(&base); - if (!baseRegVal) - return UnknownVal(); - const MemRegion *BaseRegion = baseRegVal->stripCasts(/*StripBases=*/false); - - // Assume the derived class is a pointer or a reference to a CXX record. - derivedType = derivedType->getPointeeType(); - assert(!derivedType.isNull()); - const CXXRecordDecl *DerivedDecl = derivedType->getAsCXXRecordDecl(); - if (!DerivedDecl && !derivedType->isVoidType()) - return UnknownVal(); - - // Drill down the CXXBaseObject chains, which represent upcasts (casts from - // derived to base). - const MemRegion *SR = BaseRegion; - while (const TypedRegion *TSR = dyn_cast_or_null<TypedRegion>(SR)) { - QualType BaseType = TSR->getLocationType()->getPointeeType(); - assert(!BaseType.isNull()); - const CXXRecordDecl *SRDecl = BaseType->getAsCXXRecordDecl(); - if (!SRDecl) - return UnknownVal(); - - // If found the derived class, the cast succeeds. - if (SRDecl == DerivedDecl) - return loc::MemRegionVal(TSR); - - if (!derivedType->isVoidType()) { - // 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, - /*DetectVirtual=*/false); - if (SRDecl->isDerivedFrom(DerivedDecl, Paths)) { - SVal Result = loc::MemRegionVal(TSR); - const CXXBasePath &Path = *Paths.begin(); - for (CXXBasePath::const_iterator I = Path.begin(), E = Path.end(); - I != E; ++I) { - Result = evalDerivedToBase(Result, I->Base->getType()); - } - return Result; - } - } - - if (const CXXBaseObjectRegion *R = dyn_cast<CXXBaseObjectRegion>(TSR)) - // Drill down the chain to get the derived classes. - SR = R->getSuperRegion(); - else { - // We reached the bottom of the hierarchy. - - // If this is a cast to void*, return the region. - if (derivedType->isVoidType()) - return loc::MemRegionVal(TSR); - - // We did not find the derived class. We we must be casting the base to - // derived, so the cast should fail. - Failed = true; - return UnknownVal(); - } - } - - return UnknownVal(); -} - //===----------------------------------------------------------------------===// // Loading values from regions. //===----------------------------------------------------------------------===// @@ -1047,7 +994,7 @@ SVal RegionStoreManager::getBinding(Store store, Loc L, QualType T) { T = TR->getLocationType(); else { const SymbolicRegion *SR = cast<SymbolicRegion>(MR); - T = SR->getSymbol()->getType(Ctx); + T = SR->getSymbol()->getType(); } } MR = GetElementZeroRegion(MR, T); @@ -1540,14 +1487,14 @@ bool RegionStoreManager::includedInBindings(Store store, // Binding values to regions. //===----------------------------------------------------------------------===// -StoreRef RegionStoreManager::Remove(Store store, Loc L) { +StoreRef RegionStoreManager::killBinding(Store ST, Loc L) { if (isa<loc::MemRegionVal>(L)) if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion()) - return StoreRef(removeBinding(GetRegionBindings(store), + return StoreRef(removeBinding(GetRegionBindings(ST), R).getRootWithoutRetain(), *this); - return StoreRef(store, *this); + return StoreRef(ST, *this); } StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { @@ -1560,6 +1507,8 @@ StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { // Check if the region is a struct region. if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) { QualType Ty = TR->getValueType(); + if (Ty->isArrayType()) + return BindArray(store, TR, V); if (Ty->isStructureOrClassType()) return BindStruct(store, TR, V); if (Ty->isVectorType()) @@ -1569,13 +1518,9 @@ StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { // Binding directly to a symbolic region should be treated as binding // to element 0. - QualType T = SR->getSymbol()->getType(Ctx); - - // FIXME: Is this the right way to handle symbols that are references? - if (const PointerType *PT = T->getAs<PointerType>()) - T = PT->getPointeeType(); - else - T = T->getAs<ReferenceType>()->getPointeeType(); + QualType T = SR->getSymbol()->getType(); + if (T->isAnyPointerType() || T->isReferenceType()) + T = T->getPointeeType(); R = GetElementZeroRegion(SR, T); } @@ -1589,26 +1534,12 @@ StoreRef RegionStoreManager::Bind(Store store, Loc L, SVal V) { return StoreRef(addBinding(B, Key, V).getRootWithoutRetain(), *this); } -StoreRef RegionStoreManager::BindDecl(Store store, const VarRegion *VR, - SVal InitVal) { - - QualType T = VR->getDecl()->getType(); - - if (T->isArrayType()) - return BindArray(store, VR, InitVal); - if (T->isStructureOrClassType()) - return BindStruct(store, VR, InitVal); - - return Bind(store, svalBuilder.makeLoc(VR), InitVal); -} - // FIXME: this method should be merged into Bind(). -StoreRef RegionStoreManager::BindCompoundLiteral(Store store, +StoreRef RegionStoreManager::bindCompoundLiteral(Store ST, const CompoundLiteralExpr *CL, const LocationContext *LC, SVal V) { - return Bind(store, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)), - V); + return Bind(ST, loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)), V); } StoreRef RegionStoreManager::setImplicitDefaultValue(Store store, @@ -1864,7 +1795,7 @@ RegionBindings RegionStoreManager::removeBinding(RegionBindings B, RegionBindings RegionStoreManager::removeBinding(RegionBindings B, const MemRegion *R, - BindingKey::Kind k){ + BindingKey::Kind k){ return removeBinding(B, BindingKey::Make(R, k)); } @@ -1897,7 +1828,6 @@ public: void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C); void VisitCluster(const MemRegion *baseR, const ClusterBindings &C); - void VisitBindingKey(BindingKey K); bool UpdatePostponed(); void VisitBinding(SVal V); }; @@ -1932,17 +1862,21 @@ void removeDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, const StackArgumentsSpaceRegion *StackReg = cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); const StackFrameContext *RegCtx = StackReg->getStackFrame(); - if (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx)) + if (CurrentLCtx && + (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx))) AddToWorkList(TR, &C); } } void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR, const ClusterBindings &C) { - for (ClusterBindings::iterator I = C.begin(), E = C.end(); I != E; ++I) { - VisitBindingKey(I.getKey()); + // Mark the symbol for any SymbolicRegion with live bindings as live itself. + // This means we should continue to track that symbol. + if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR)) + SymReaper.markLive(SymR->getSymbol()); + + for (ClusterBindings::iterator I = C.begin(), E = C.end(); I != E; ++I) VisitBinding(I.getData()); - } } void removeDeadBindingsWorker::VisitBinding(SVal V) { @@ -1979,8 +1913,8 @@ void removeDeadBindingsWorker::VisitBinding(SVal V) { if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) { BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(), E = BR->referenced_vars_end(); - for ( ; I != E; ++I) - AddToWorkList(I.getCapturedRegion()); + for ( ; I != E; ++I) + AddToWorkList(I.getCapturedRegion()); } } @@ -1991,20 +1925,6 @@ void removeDeadBindingsWorker::VisitBinding(SVal V) { SymReaper.markLive(*SI); } -void removeDeadBindingsWorker::VisitBindingKey(BindingKey K) { - const MemRegion *R = K.getRegion(); - - // Mark this region "live" by adding it to the worklist. This will cause - // use to visit all regions in the cluster (if we haven't visited them - // already). - if (AddToWorkList(R)) { - // Mark the symbol for any live SymbolicRegion as "live". This means we - // should continue to track that symbol. - if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R)) - SymReaper.markLive(SymR->getSymbol()); - } -} - bool removeDeadBindingsWorker::UpdatePostponed() { // See if any postponed SymbolicRegions are actually live now, after // having done a scan. @@ -2012,7 +1932,7 @@ bool removeDeadBindingsWorker::UpdatePostponed() { for (SmallVectorImpl<const SymbolicRegion*>::iterator I = Postponed.begin(), E = Postponed.end() ; I != E ; ++I) { - if (const SymbolicRegion *SR = cast_or_null<SymbolicRegion>(*I)) { + if (const SymbolicRegion *SR = *I) { if (SymReaper.isLive(SR->getSymbol())) { changed |= AddToWorkList(SR); *I = NULL; diff --git a/lib/StaticAnalyzer/Core/SValBuilder.cpp b/lib/StaticAnalyzer/Core/SValBuilder.cpp index d1936cd..b87169a 100644 --- a/lib/StaticAnalyzer/Core/SValBuilder.cpp +++ b/lib/StaticAnalyzer/Core/SValBuilder.cpp @@ -106,25 +106,23 @@ SValBuilder::getRegionValueSymbolVal(const TypedValueRegion* region) { return nonloc::SymbolVal(sym); } -DefinedOrUnknownSVal -SValBuilder::getConjuredSymbolVal(const void *symbolTag, - const Expr *expr, - const LocationContext *LCtx, - unsigned count) { +DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *symbolTag, + const Expr *expr, + const LocationContext *LCtx, + unsigned count) { QualType T = expr->getType(); - return getConjuredSymbolVal(symbolTag, expr, LCtx, T, count); + return conjureSymbolVal(symbolTag, expr, LCtx, T, count); } -DefinedOrUnknownSVal -SValBuilder::getConjuredSymbolVal(const void *symbolTag, - const Expr *expr, - const LocationContext *LCtx, - QualType type, - unsigned count) { +DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *symbolTag, + const Expr *expr, + const LocationContext *LCtx, + QualType type, + unsigned count) { if (!SymbolManager::canSymbolicate(type)) return UnknownVal(); - SymbolRef sym = SymMgr.getConjuredSymbol(expr, LCtx, type, count, symbolTag); + SymbolRef sym = SymMgr.conjureSymbol(expr, LCtx, type, count, symbolTag); if (Loc::isLocType(type)) return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); @@ -133,15 +131,14 @@ SValBuilder::getConjuredSymbolVal(const void *symbolTag, } -DefinedOrUnknownSVal -SValBuilder::getConjuredSymbolVal(const Stmt *stmt, - const LocationContext *LCtx, - QualType type, - unsigned visitCount) { +DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const Stmt *stmt, + const LocationContext *LCtx, + QualType type, + unsigned visitCount) { if (!SymbolManager::canSymbolicate(type)) return UnknownVal(); - SymbolRef sym = SymMgr.getConjuredSymbol(stmt, LCtx, type, visitCount); + SymbolRef sym = SymMgr.conjureSymbol(stmt, LCtx, type, visitCount); if (Loc::isLocType(type)) return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); @@ -157,7 +154,7 @@ SValBuilder::getConjuredHeapSymbolVal(const Expr *E, assert(Loc::isLocType(T)); assert(SymbolManager::canSymbolicate(T)); - SymbolRef sym = SymMgr.getConjuredSymbol(E, LCtx, T, VisitCount); + SymbolRef sym = SymMgr.conjureSymbol(E, LCtx, T, VisitCount); return loc::MemRegionVal(MemMgr.getSymbolicHeapRegion(sym)); } diff --git a/lib/StaticAnalyzer/Core/SVals.cpp b/lib/StaticAnalyzer/Core/SVals.cpp index 8437f50..e34ab6a 100644 --- a/lib/StaticAnalyzer/Core/SVals.cpp +++ b/lib/StaticAnalyzer/Core/SVals.cpp @@ -51,7 +51,8 @@ const FunctionDecl *SVal::getAsFunctionDecl() const { if (const loc::MemRegionVal* X = dyn_cast<loc::MemRegionVal>(this)) { const MemRegion* R = X->getRegion(); if (const FunctionTextRegion *CTR = R->getAs<FunctionTextRegion>()) - return CTR->getDecl(); + if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CTR->getDecl())) + return FD; } return 0; diff --git a/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp b/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp index 5568f1c..4236ee4 100644 --- a/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp +++ b/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp @@ -67,7 +67,9 @@ ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef state, ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef state, Loc cond, bool assumption) { state = assumeAux(state, cond, assumption); - return SU.processAssume(state, cond, assumption); + if (NotifyAssumeClients && SU) + return SU->processAssume(state, cond, assumption); + return state; } ProgramStateRef SimpleConstraintManager::assumeAux(ProgramStateRef state, @@ -113,7 +115,9 @@ ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef state, NonLoc cond, bool assumption) { state = assumeAux(state, cond, assumption); - return SU.processAssume(state, cond, assumption); + if (NotifyAssumeClients && SU) + return SU->processAssume(state, cond, assumption); + return state; } static BinaryOperator::Opcode NegateComparison(BinaryOperator::Opcode op) { @@ -136,7 +140,7 @@ ProgramStateRef SimpleConstraintManager::assumeAuxForSymbol(ProgramStateRef State, SymbolRef Sym, bool Assumption) { BasicValueFactory &BVF = getBasicVals(); - QualType T = Sym->getType(BVF.getContext()); + QualType T = Sym->getType(); // None of the constraint solvers currently support non-integer types. if (!T->isIntegerType()) @@ -186,7 +190,7 @@ ProgramStateRef SimpleConstraintManager::assumeAux(ProgramStateRef state, BinaryOperator::Opcode op = SE->getOpcode(); // Implicitly compare non-comparison expressions to 0. if (!BinaryOperator::isComparisonOp(op)) { - QualType T = SE->getType(BasicVals.getContext()); + QualType T = SE->getType(); const llvm::APSInt &zero = BasicVals.getValue(0, T); op = (Assumption ? BO_NE : BO_EQ); return assumeSymRel(state, SE, op, zero); @@ -235,11 +239,9 @@ ProgramStateRef SimpleConstraintManager::assumeSymRel(ProgramStateRef state, assert(BinaryOperator::isComparisonOp(op) && "Non-comparison ops should be rewritten as comparisons to zero."); - BasicValueFactory &BVF = getBasicVals(); - ASTContext &Ctx = BVF.getContext(); - // Get the type used for calculating wraparound. - APSIntType WraparoundType = BVF.getAPSIntType(LHS->getType(Ctx)); + BasicValueFactory &BVF = getBasicVals(); + APSIntType WraparoundType = BVF.getAPSIntType(LHS->getType()); // We only handle simple comparisons of the form "$sym == constant" // or "($sym+constant1) == constant2". diff --git a/lib/StaticAnalyzer/Core/SimpleConstraintManager.h b/lib/StaticAnalyzer/Core/SimpleConstraintManager.h index 088d70c..01f0b4e 100644 --- a/lib/StaticAnalyzer/Core/SimpleConstraintManager.h +++ b/lib/StaticAnalyzer/Core/SimpleConstraintManager.h @@ -22,10 +22,10 @@ namespace clang { namespace ento { class SimpleConstraintManager : public ConstraintManager { - SubEngine &SU; + SubEngine *SU; BasicValueFactory &BVF; public: - SimpleConstraintManager(SubEngine &subengine, BasicValueFactory &BV) + SimpleConstraintManager(SubEngine *subengine, BasicValueFactory &BV) : SU(subengine), BVF(BV) {} virtual ~SimpleConstraintManager(); diff --git a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp index ad58a07..fbc6ba0 100644 --- a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp +++ b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp @@ -81,7 +81,7 @@ SVal SimpleSValBuilder::evalCastFromNonLoc(NonLoc val, QualType castTy) { } if (const SymExpr *se = val.getAsSymbolicExpression()) { - QualType T = Context.getCanonicalType(se->getType(Context)); + QualType T = Context.getCanonicalType(se->getType()); // If types are the same or both are integers, ignore the cast. // FIXME: Remove this hack when we support symbolic truncation/extension. // HACK: If both castTy and T are integers, ignore the cast. This is @@ -276,7 +276,7 @@ SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS, // with the given constant. // FIXME: This is an approximation of Sema::UsualArithmeticConversions. ASTContext &Ctx = getContext(); - QualType SymbolType = LHS->getType(Ctx); + QualType SymbolType = LHS->getType(); uint64_t ValWidth = RHS.getBitWidth(); uint64_t TypeWidth = Ctx.getTypeSize(SymbolType); @@ -318,7 +318,9 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, return makeTruthVal(false, resultTy); case BO_Xor: case BO_Sub: - return makeIntVal(0, resultTy); + if (resultTy->isIntegralOrEnumerationType()) + return makeIntVal(0, resultTy); + return evalCastFromNonLoc(makeIntVal(0, /*Unsigned=*/false), resultTy); case BO_Or: case BO_And: return evalCastFromNonLoc(lhs, resultTy); @@ -459,7 +461,7 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, case BO_NE: // Negate the comparison and make a value. opc = NegateComparison(opc); - assert(symIntExpr->getType(Context) == resultTy); + assert(symIntExpr->getType() == resultTy); return makeNonLoc(symIntExpr->getLHS(), opc, symIntExpr->getRHS(), resultTy); } @@ -505,7 +507,8 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, } else if (isa<SymbolData>(Sym)) { // Does the symbol simplify to a constant? If so, "fold" the constant // by setting 'lhs' to a ConcreteInt and try again. - if (const llvm::APSInt *Constant = state->getSymVal(Sym)) { + if (const llvm::APSInt *Constant = state->getConstraintManager() + .getSymVal(state, Sym)) { lhs = nonloc::ConcreteInt(*Constant); continue; } @@ -916,14 +919,8 @@ SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state, else if (isa<SubRegion>(region)) { superR = region; index = rhs; - if (const PointerType *PT = resultTy->getAs<PointerType>()) { - elementType = PT->getPointeeType(); - } - else { - const ObjCObjectPointerType *OT = - resultTy->getAs<ObjCObjectPointerType>(); - elementType = OT->getPointeeType(); - } + if (resultTy->isAnyPointerType()) + elementType = resultTy->getPointeeType(); } if (NonLoc *indexV = dyn_cast<NonLoc>(&index)) { @@ -946,7 +943,7 @@ const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state, return &X->getValue(); if (SymbolRef Sym = V.getAsSymbol()) - return state->getSymVal(Sym); + return state->getConstraintManager().getSymVal(state, Sym); // FIXME: Add support for SymExprs. return NULL; diff --git a/lib/StaticAnalyzer/Core/Store.cpp b/lib/StaticAnalyzer/Core/Store.cpp index 3af60a1..939ae54 100644 --- a/lib/StaticAnalyzer/Core/Store.cpp +++ b/lib/StaticAnalyzer/Core/Store.cpp @@ -15,6 +15,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/AST/CharUnits.h" +#include "clang/AST/CXXInheritance.h" #include "clang/AST/DeclObjC.h" using namespace clang; @@ -233,6 +234,91 @@ SVal StoreManager::evalDerivedToBase(SVal Derived, const CastExpr *Cast) { return Result; } +SVal StoreManager::evalDerivedToBase(SVal Derived, const CXXBasePath &Path) { + // Walk through the path to create nested CXXBaseRegions. + SVal Result = Derived; + for (CXXBasePath::const_iterator I = Path.begin(), E = Path.end(); + I != E; ++I) { + Result = evalDerivedToBase(Result, I->Base->getType()); + } + return Result; +} + +SVal StoreManager::evalDerivedToBase(SVal Derived, QualType BaseType) { + loc::MemRegionVal *DerivedRegVal = dyn_cast<loc::MemRegionVal>(&Derived); + if (!DerivedRegVal) + return Derived; + + const CXXRecordDecl *BaseDecl = BaseType->getPointeeCXXRecordDecl(); + if (!BaseDecl) + BaseDecl = BaseType->getAsCXXRecordDecl(); + assert(BaseDecl && "not a C++ object?"); + + const MemRegion *BaseReg = + MRMgr.getCXXBaseObjectRegion(BaseDecl, DerivedRegVal->getRegion()); + + return loc::MemRegionVal(BaseReg); +} + +SVal StoreManager::evalDynamicCast(SVal Base, QualType DerivedType, + bool &Failed) { + Failed = false; + + loc::MemRegionVal *BaseRegVal = dyn_cast<loc::MemRegionVal>(&Base); + if (!BaseRegVal) + return UnknownVal(); + const MemRegion *BaseRegion = BaseRegVal->stripCasts(/*StripBases=*/false); + + // Assume the derived class is a pointer or a reference to a CXX record. + DerivedType = DerivedType->getPointeeType(); + assert(!DerivedType.isNull()); + const CXXRecordDecl *DerivedDecl = DerivedType->getAsCXXRecordDecl(); + if (!DerivedDecl && !DerivedType->isVoidType()) + return UnknownVal(); + + // Drill down the CXXBaseObject chains, which represent upcasts (casts from + // derived to base). + const MemRegion *SR = BaseRegion; + while (const TypedRegion *TSR = dyn_cast_or_null<TypedRegion>(SR)) { + QualType BaseType = TSR->getLocationType()->getPointeeType(); + assert(!BaseType.isNull()); + const CXXRecordDecl *SRDecl = BaseType->getAsCXXRecordDecl(); + if (!SRDecl) + return UnknownVal(); + + // If found the derived class, the cast succeeds. + if (SRDecl == DerivedDecl) + return loc::MemRegionVal(TSR); + + if (!DerivedType->isVoidType()) { + // 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, + /*DetectVirtual=*/false); + if (SRDecl->isDerivedFrom(DerivedDecl, Paths)) + return evalDerivedToBase(loc::MemRegionVal(TSR), Paths.front()); + } + + if (const CXXBaseObjectRegion *R = dyn_cast<CXXBaseObjectRegion>(TSR)) + // Drill down the chain to get the derived classes. + SR = R->getSuperRegion(); + else { + // We reached the bottom of the hierarchy. + + // If this is a cast to void*, return the region. + if (DerivedType->isVoidType()) + return loc::MemRegionVal(TSR); + + // We did not find the derived class. We we must be casting the base to + // derived, so the cast should fail. + Failed = true; + return UnknownVal(); + } + } + + return UnknownVal(); +} + /// CastRetrievedVal - Used by subclasses of StoreManager to implement /// implicit casts that arise from loads from regions that are reinterpreted diff --git a/lib/StaticAnalyzer/Core/SymbolManager.cpp b/lib/StaticAnalyzer/Core/SymbolManager.cpp index 0bc192d..0c5098b 100644 --- a/lib/StaticAnalyzer/Core/SymbolManager.cpp +++ b/lib/StaticAnalyzer/Core/SymbolManager.cpp @@ -117,21 +117,17 @@ bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const { SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) { itr.push_back(SE); - while (!isa<SymbolData>(itr.back())) expand(); } SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() { assert(!itr.empty() && "attempting to iterate on an 'end' iterator"); - assert(isa<SymbolData>(itr.back())); - itr.pop_back(); - if (!itr.empty()) - while (!isa<SymbolData>(itr.back())) expand(); + expand(); return *this; } SymbolRef SymExpr::symbol_iterator::operator*() { assert(!itr.empty() && "attempting to dereference an 'end' iterator"); - return cast<SymbolData>(itr.back()); + return itr.back(); } void SymExpr::symbol_iterator::expand() { @@ -187,11 +183,11 @@ SymbolManager::getRegionValueSymbol(const TypedValueRegion* R) { return cast<SymbolRegionValue>(SD); } -const SymbolConjured* -SymbolManager::getConjuredSymbol(const Stmt *E, const LocationContext *LCtx, - QualType T, unsigned Count, - const void *SymbolTag) { - +const SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E, + const LocationContext *LCtx, + QualType T, + unsigned Count, + const void *SymbolTag) { llvm::FoldingSetNodeID profile; SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag); void *InsertPos; @@ -328,23 +324,24 @@ const SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs, return cast<SymSymExpr>(data); } -QualType SymbolConjured::getType(ASTContext&) const { +QualType SymbolConjured::getType() const { return T; } -QualType SymbolDerived::getType(ASTContext &Ctx) const { +QualType SymbolDerived::getType() const { return R->getValueType(); } -QualType SymbolExtent::getType(ASTContext &Ctx) const { +QualType SymbolExtent::getType() const { + ASTContext &Ctx = R->getMemRegionManager()->getContext(); return Ctx.getSizeType(); } -QualType SymbolMetadata::getType(ASTContext&) const { +QualType SymbolMetadata::getType() const { return T; } -QualType SymbolRegionValue::getType(ASTContext &C) const { +QualType SymbolRegionValue::getType() const { return R->getValueType(); } @@ -466,41 +463,56 @@ bool SymbolReaper::isLive(SymbolRef sym) { markDependentsLive(sym); return true; } - - if (const SymbolDerived *derived = dyn_cast<SymbolDerived>(sym)) { - if (isLive(derived->getParentSymbol())) { - markLive(sym); - return true; - } - return false; - } - - if (const SymbolExtent *extent = dyn_cast<SymbolExtent>(sym)) { - if (isLiveRegion(extent->getRegion())) { - markLive(sym); - return true; - } - return false; + + bool KnownLive; + + switch (sym->getKind()) { + case SymExpr::RegionValueKind: + // FIXME: We should be able to use isLiveRegion here (this behavior + // predates isLiveRegion), but doing so causes test failures. Investigate. + KnownLive = true; + break; + case SymExpr::ConjuredKind: + KnownLive = false; + break; + case SymExpr::DerivedKind: + KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol()); + break; + case SymExpr::ExtentKind: + KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion()); + break; + case SymExpr::MetadataKind: + KnownLive = MetadataInUse.count(sym) && + isLiveRegion(cast<SymbolMetadata>(sym)->getRegion()); + if (KnownLive) + MetadataInUse.erase(sym); + break; + case SymExpr::SymIntKind: + KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS()); + break; + case SymExpr::IntSymKind: + KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS()); + break; + case SymExpr::SymSymKind: + KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) && + isLive(cast<SymSymExpr>(sym)->getRHS()); + break; + case SymExpr::CastSymbolKind: + KnownLive = isLive(cast<SymbolCast>(sym)->getOperand()); + break; } - if (const SymbolMetadata *metadata = dyn_cast<SymbolMetadata>(sym)) { - if (MetadataInUse.count(sym)) { - if (isLiveRegion(metadata->getRegion())) { - markLive(sym); - MetadataInUse.erase(sym); - return true; - } - } - return false; - } + if (KnownLive) + markLive(sym); - // Interogate the symbol. It may derive from an input value to - // the analyzed function/method. - return isa<SymbolRegionValue>(sym); + return KnownLive; } bool SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const { + if (LCtx == 0) + return false; + if (LCtx != ELCtx) { // If the reaper's location context is a parent of the expression's // location context, then the expression value is now "out of scope". @@ -508,6 +520,7 @@ SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const { return false; return true; } + // If no statement is provided, everything is this and parent contexts is live. if (!Loc) return true; @@ -517,10 +530,16 @@ SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const { bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{ const StackFrameContext *VarContext = VR->getStackFrame(); + + if (!VarContext) + return true; + + if (!LCtx) + return false; const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame(); if (VarContext == CurrentContext) { - // If no statemetnt is provided, everything is live. + // If no statement is provided, everything is live. if (!Loc) return true; diff --git a/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp b/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp index 66bf4bb..e09f4e3 100644 --- a/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp +++ b/lib/StaticAnalyzer/Core/TextPathDiagnostics.cpp @@ -41,7 +41,6 @@ public: PathGenerationScheme getGenerationScheme() const { return Minimal; } bool supportsLogicalOpControlFlow() const { return true; } bool supportsAllBlockEdges() const { return true; } - virtual bool useVerboseDescription() const { return true; } virtual bool supportsCrossFileDiagnostics() const { return true; } }; |