diff options
Diffstat (limited to 'clang/lib/StaticAnalyzer/Core')
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/ExprEngine.cpp | 156 | ||||
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp | 77 | ||||
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp | 61 | ||||
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/MemRegion.cpp | 4 | ||||
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp | 133 | ||||
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/SValBuilder.cpp | 870 | ||||
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/SVals.cpp | 10 |
7 files changed, 768 insertions, 543 deletions
diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 45af22de50ae..d8f56f2f8cff 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -185,6 +185,17 @@ typedef llvm::ImmutableMap<ConstructedObjectKey, SVal> REGISTER_TRAIT_WITH_PROGRAMSTATE(ObjectsUnderConstruction, ObjectsUnderConstructionMap) +// This trait is responsible for storing the index of the element that is to be +// constructed in the next iteration. As a result a CXXConstructExpr is only +// stored if it is array type. Also the index is the index of the continous +// memory region, which is important for multi-dimensional arrays. E.g:: int +// arr[2][2]; assume arr[1][1] will be the next element under construction, so +// the index is 3. +typedef llvm::ImmutableMap< + std::pair<const CXXConstructExpr *, const LocationContext *>, unsigned> + IndexOfElementToConstructMap; +REGISTER_TRAIT_WITH_PROGRAMSTATE(IndexOfElementToConstruct, + IndexOfElementToConstructMap) //===----------------------------------------------------------------------===// // Engine construction and deletion. //===----------------------------------------------------------------------===// @@ -441,16 +452,65 @@ ProgramStateRef ExprEngine::createTemporaryRegionIfNeeded( return State; } +ProgramStateRef ExprEngine::setIndexOfElementToConstruct( + ProgramStateRef State, const CXXConstructExpr *E, + const LocationContext *LCtx, unsigned Idx) { + auto Key = std::make_pair(E, LCtx->getStackFrame()); + + assert(!State->contains<IndexOfElementToConstruct>(Key) || Idx > 0); + + return State->set<IndexOfElementToConstruct>(Key, Idx); +} + +Optional<unsigned> +ExprEngine::getIndexOfElementToConstruct(ProgramStateRef State, + const CXXConstructExpr *E, + const LocationContext *LCtx) { + + return Optional<unsigned>::create( + State->get<IndexOfElementToConstruct>({E, LCtx->getStackFrame()})); +} + +ProgramStateRef +ExprEngine::removeIndexOfElementToConstruct(ProgramStateRef State, + const CXXConstructExpr *E, + const LocationContext *LCtx) { + auto Key = std::make_pair(E, LCtx->getStackFrame()); + + assert(E && State->contains<IndexOfElementToConstruct>(Key)); + return State->remove<IndexOfElementToConstruct>(Key); +} + ProgramStateRef ExprEngine::addObjectUnderConstruction(ProgramStateRef State, const ConstructionContextItem &Item, const LocationContext *LC, SVal V) { ConstructedObjectKey Key(Item, LC->getStackFrame()); + + const CXXConstructExpr *E = nullptr; + + if (auto DS = dyn_cast_or_null<DeclStmt>(Item.getStmtOrNull())) { + if (auto VD = dyn_cast_or_null<VarDecl>(DS->getSingleDecl())) + E = dyn_cast<CXXConstructExpr>(VD->getInit()); + } + + if (!E && !Item.getStmtOrNull()) { + auto CtorInit = Item.getCXXCtorInitializer(); + E = dyn_cast<CXXConstructExpr>(CtorInit->getInit()); + } + // FIXME: Currently the state might already contain the marker due to // incorrect handling of temporaries bound to default parameters. - assert(!State->get<ObjectsUnderConstruction>(Key) || - Key.getItem().getKind() == - ConstructionContextItem::TemporaryDestructorKind); + // The state will already contain the marker if we construct elements + // in an array, as we visit the same statement multiple times before + // the array declaration. The marker is removed when we exit the + // constructor call. + assert((!State->get<ObjectsUnderConstruction>(Key) || + Key.getItem().getKind() == + ConstructionContextItem::TemporaryDestructorKind || + State->contains<IndexOfElementToConstruct>({E, LC})) && + "The object is already marked as `UnderConstruction`, when it's not " + "supposed to!"); return State->set<ObjectsUnderConstruction>(Key, V); } @@ -582,6 +642,69 @@ printObjectsUnderConstructionJson(raw_ostream &Out, ProgramStateRef State, } } +static void printIndicesOfElementsToConstructJson( + raw_ostream &Out, ProgramStateRef State, const char *NL, + const LocationContext *LCtx, const ASTContext &Context, + unsigned int Space = 0, bool IsDot = false) { + using KeyT = std::pair<const Expr *, const LocationContext *>; + + PrintingPolicy PP = + LCtx->getAnalysisDeclContext()->getASTContext().getPrintingPolicy(); + + ++Space; + bool HasItem = false; + + // Store the last key. + KeyT LastKey; + for (const auto &I : State->get<IndexOfElementToConstruct>()) { + const KeyT &Key = I.first; + if (Key.second != LCtx) + continue; + + if (!HasItem) { + Out << "[" << NL; + HasItem = true; + } + + LastKey = Key; + } + + for (const auto &I : State->get<IndexOfElementToConstruct>()) { + const KeyT &Key = I.first; + unsigned Value = I.second; + if (Key.second != LCtx) + continue; + + Indent(Out, Space, IsDot) << "{ "; + + // Expr + const Expr *E = Key.first; + Out << "\"stmt_id\": " << E->getID(Context); + + // Kind - hack to display the current index + Out << ", \"kind\": \"Cur: " << Value - 1 << "\""; + + // Pretty-print + Out << ", \"pretty\": "; + Out << "\"" << E->getStmtClassName() << " " + << E->getSourceRange().printToString(Context.getSourceManager()) << " '" + << QualType::getAsString(E->getType().split(), PP); + Out << "'\""; + + Out << ", \"value\": \"Next: " << Value << "\" }"; + + if (Key != LastKey) + Out << ','; + Out << NL; + } + + if (HasItem) + Indent(Out, --Space, IsDot) << ']'; // End of "location_context". + else { + Out << "null "; + } +} + void ExprEngine::printJson(raw_ostream &Out, ProgramStateRef State, const LocationContext *LCtx, const char *NL, unsigned int Space, bool IsDot) const { @@ -600,6 +723,23 @@ void ExprEngine::printJson(raw_ostream &Out, ProgramStateRef State, Out << "null," << NL; } + Indent(Out, Space, IsDot) << "\"index_of_element\": "; + if (LCtx && !State->get<IndexOfElementToConstruct>().isEmpty()) { + ++Space; + + auto &Context = getContext(); + Out << '[' << NL; + LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) { + printIndicesOfElementsToConstructJson(Out, State, NL, LC, Context, Space, + IsDot); + }); + + --Space; + Indent(Out, Space, IsDot) << "]," << NL; // End of "index_of_element". + } else { + Out << "null," << NL; + } + getCheckerManager().runCheckersForPrintStateJson(Out, State, NL, Space, IsDot); } @@ -961,8 +1101,9 @@ void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor, // This workaround will just run the first destructor (which will still // invalidate the entire array). EvalCallOptions CallOpts; - Region = makeZeroElementRegion(state, loc::MemRegionVal(Region), varType, - CallOpts.IsArrayCtorOrDtor).getAsRegion(); + Region = makeElementRegion(state, loc::MemRegionVal(Region), varType, + CallOpts.IsArrayCtorOrDtor) + .getAsRegion(); VisitCXXDestructor(varType, Region, Dtor.getTriggerStmt(), /*IsBase=*/false, Pred, Dst, CallOpts); @@ -1045,8 +1186,7 @@ void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, // This workaround will just run the first destructor (which will still // invalidate the entire array). EvalCallOptions CallOpts; - FieldVal = makeZeroElementRegion(State, FieldVal, T, - CallOpts.IsArrayCtorOrDtor); + FieldVal = makeElementRegion(State, FieldVal, T, CallOpts.IsArrayCtorOrDtor); VisitCXXDestructor(T, FieldVal.getAsRegion(), CurDtor->getBody(), /*IsBase=*/false, Pred, Dst, CallOpts); @@ -1105,7 +1245,7 @@ void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, CallOpts.IsArrayCtorOrDtor = true; } } else { - // We'd eventually need to makeZeroElementRegion() trick here, + // We'd eventually need to makeElementRegion() trick here, // but for now we don't have the respective construction contexts, // so MR would always be null in this case. Do nothing for now. } diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp index 6d979da2755f..08fac9fb2e69 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp @@ -94,15 +94,17 @@ void ExprEngine::performTrivialCopy(NodeBuilder &Bldr, ExplodedNode *Pred, } } - -SVal ExprEngine::makeZeroElementRegion(ProgramStateRef State, SVal LValue, - QualType &Ty, bool &IsArray) { +SVal ExprEngine::makeElementRegion(ProgramStateRef State, SVal LValue, + QualType &Ty, bool &IsArray, unsigned Idx) { SValBuilder &SVB = State->getStateManager().getSValBuilder(); ASTContext &Ctx = SVB.getContext(); - while (const ArrayType *AT = Ctx.getAsArrayType(Ty)) { - Ty = AT->getElementType(); - LValue = State->getLValue(Ty, SVB.makeZeroArrayIndex(), LValue); + if (const ArrayType *AT = Ctx.getAsArrayType(Ty)) { + while (AT) { + Ty = AT->getElementType(); + AT = dyn_cast<ArrayType>(AT->getElementType()); + } + LValue = State->getLValue(Ty, SVB.makeArrayIndex(Idx), LValue); IsArray = true; } @@ -111,7 +113,7 @@ SVal ExprEngine::makeZeroElementRegion(ProgramStateRef State, SVal LValue, SVal ExprEngine::computeObjectUnderConstruction( const Expr *E, ProgramStateRef State, const LocationContext *LCtx, - const ConstructionContext *CC, EvalCallOptions &CallOpts) { + const ConstructionContext *CC, EvalCallOptions &CallOpts, unsigned Idx) { SValBuilder &SVB = getSValBuilder(); MemRegionManager &MRMgr = SVB.getRegionManager(); ASTContext &ACtx = SVB.getContext(); @@ -125,8 +127,8 @@ SVal ExprEngine::computeObjectUnderConstruction( const auto *DS = DSCC->getDeclStmt(); const auto *Var = cast<VarDecl>(DS->getSingleDecl()); QualType Ty = Var->getType(); - return makeZeroElementRegion(State, State->getLValue(Var, LCtx), Ty, - CallOpts.IsArrayCtorOrDtor); + return makeElementRegion(State, State->getLValue(Var, LCtx), Ty, + CallOpts.IsArrayCtorOrDtor, Idx); } case ConstructionContext::CXX17ElidedCopyConstructorInitializerKind: case ConstructionContext::SimpleConstructorInitializerKind: { @@ -158,8 +160,8 @@ SVal ExprEngine::computeObjectUnderConstruction( } QualType Ty = Field->getType(); - return makeZeroElementRegion(State, FieldVal, Ty, - CallOpts.IsArrayCtorOrDtor); + return makeElementRegion(State, FieldVal, Ty, CallOpts.IsArrayCtorOrDtor, + Idx); } case ConstructionContext::NewAllocatedObjectKind: { if (AMgr.getAnalyzerOptions().MayInlineCXXAllocator) { @@ -172,8 +174,12 @@ SVal ExprEngine::computeObjectUnderConstruction( // TODO: In fact, we need to call the constructor for every // allocated element, not just the first one! CallOpts.IsArrayCtorOrDtor = true; - return loc::MemRegionVal(getStoreManager().GetElementZeroRegion( - MR, NE->getType()->getPointeeType())); + + auto R = MRMgr.getElementRegion(NE->getType()->getPointeeType(), + svalBuilder.makeArrayIndex(Idx), MR, + SVB.getContext()); + + return loc::MemRegionVal(R); } return V; } @@ -484,10 +490,6 @@ void ExprEngine::handleConstructor(const Expr *E, } } - // FIXME: Handle arrays, which run the same constructor for every element. - // For now, we just run the first constructor (which should still invalidate - // the entire array). - EvalCallOptions CallOpts; auto C = getCurrentCFGElement().getAs<CFGConstructor>(); assert(C || getCurrentCFGElement().getAs<CFGStmt>()); @@ -500,9 +502,15 @@ void ExprEngine::handleConstructor(const Expr *E, // Inherited constructors are always base class constructors. assert(CE && !CIE && "A complete constructor is inherited?!"); + unsigned Idx = 0; + if (CE->getType()->isArrayType()) { + Idx = getIndexOfElementToConstruct(State, CE, LCtx).value_or(0u); + State = setIndexOfElementToConstruct(State, CE, LCtx, Idx + 1); + } + // The target region is found from construction context. std::tie(State, Target) = - handleConstructionContext(CE, State, LCtx, CC, CallOpts); + handleConstructionContext(CE, State, LCtx, CC, CallOpts, Idx); break; } case CXXConstructExpr::CK_VirtualBase: { @@ -894,14 +902,39 @@ void ExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred, SVal Result = symVal; if (CNE->isArray()) { - // FIXME: allocating an array requires simulating the constructors. - // For now, just return a symbolicated region. + if (const auto *NewReg = cast_or_null<SubRegion>(symVal.getAsRegion())) { - QualType ObjTy = CNE->getType()->getPointeeType(); + // If each element is initialized by their default constructor, the field + // values are properly placed inside the required region, however if an + // initializer list is used, this doesn't happen automatically. + auto *Init = CNE->getInitializer(); + bool isInitList = dyn_cast_or_null<InitListExpr>(Init); + + QualType ObjTy = + isInitList ? Init->getType() : CNE->getType()->getPointeeType(); const ElementRegion *EleReg = - getStoreManager().GetElementZeroRegion(NewReg, ObjTy); + MRMgr.getElementRegion(ObjTy, svalBuilder.makeArrayIndex(0), NewReg, + svalBuilder.getContext()); Result = loc::MemRegionVal(EleReg); + + // If the array is list initialized, we bind the initializer list to the + // memory region here, otherwise we would lose it. + if (isInitList) { + Bldr.takeNodes(Pred); + Pred = Bldr.generateNode(CNE, Pred, State); + + SVal V = State->getSVal(Init, LCtx); + ExplodedNodeSet evaluated; + evalBind(evaluated, CNE, Pred, Result, V, true); + + Bldr.takeNodes(Pred); + Bldr.addNodes(evaluated); + + Pred = *evaluated.begin(); + State = Pred->getState(); + } } + State = State->BindExpr(CNE, Pred->getLocationContext(), Result); Bldr.generateNode(CNE, Pred, State); return; diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp index e1649f0b3df6..ebcca92a3e4e 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp @@ -227,6 +227,13 @@ void ExprEngine::processCallExit(ExplodedNode *CEBNode) { // Step 2: generate node with bound return value: CEBNode -> BindedRetNode. + // If this variable is set to 'true' the analyzer will evaluate the call + // statement we are about to exit again, instead of continuing the execution + // from the statement after the call. This is useful for non-POD type array + // construction where the CXXConstructExpr is referenced only once in the CFG, + // but we want to evaluate it as many times as many elements the array has. + bool ShouldRepeatCall = false; + // If the callee returns an expression, bind its value to CallExpr. if (CE) { if (const ReturnStmt *RS = dyn_cast_or_null<ReturnStmt>(LastSt)) { @@ -255,6 +262,12 @@ void ExprEngine::processCallExit(ExplodedNode *CEBNode) { SVal ThisV = state->getSVal(This); ThisV = state->getSVal(ThisV.castAs<Loc>()); state = state->BindExpr(CCE, callerCtx, ThisV); + + ShouldRepeatCall = shouldRepeatCtorCall(state, CCE, callerCtx); + + if (!ShouldRepeatCall && + getIndexOfElementToConstruct(state, CCE, callerCtx)) + state = removeIndexOfElementToConstruct(state, CCE, callerCtx); } if (const auto *CNE = dyn_cast<CXXNewExpr>(CE)) { @@ -358,9 +371,10 @@ void ExprEngine::processCallExit(ExplodedNode *CEBNode) { // Enqueue the next element in the block. for (ExplodedNodeSet::iterator PSI = Dst.begin(), PSE = Dst.end(); - PSI != PSE; ++PSI) { - Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(), - calleeCtx->getIndex()+1); + PSI != PSE; ++PSI) { + unsigned Idx = calleeCtx->getIndex() + (ShouldRepeatCall ? 0 : 1); + + Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(), Idx); } } } @@ -800,8 +814,11 @@ ExprEngine::mayInlineCallKind(const CallEvent &Call, const ExplodedNode *Pred, // initializers for array fields in default move/copy constructors. // We still allow construction into ElementRegion targets when they don't // represent array elements. - if (CallOpts.IsArrayCtorOrDtor) - return CIP_DisallowedOnce; + if (CallOpts.IsArrayCtorOrDtor) { + if (!shouldInlineArrayConstruction( + dyn_cast<ArrayType>(CtorExpr->getType()))) + return CIP_DisallowedOnce; + } // Inlining constructors requires including initializers in the CFG. const AnalysisDeclContext *ADC = CallerSFC->getAnalysisDeclContext(); @@ -852,7 +869,7 @@ ExprEngine::mayInlineCallKind(const CallEvent &Call, const ExplodedNode *Pred, assert(ADC->getCFGBuildOptions().AddImplicitDtors && "No CFG destructors"); (void)ADC; - // FIXME: We don't handle constructors or destructors for arrays properly. + // FIXME: We don't handle destructors for arrays properly. if (CallOpts.IsArrayCtorOrDtor) return CIP_DisallowedOnce; @@ -1065,6 +1082,38 @@ bool ExprEngine::shouldInlineCall(const CallEvent &Call, const Decl *D, return true; } +bool ExprEngine::shouldInlineArrayConstruction(const ArrayType *Type) { + if (!Type) + return false; + + // FIXME: Handle other arrays types. + if (const auto *CAT = dyn_cast<ConstantArrayType>(Type)) { + unsigned Size = getContext().getConstantArrayElementCount(CAT); + + return Size <= AMgr.options.maxBlockVisitOnPath; + } + + return false; +} + +bool ExprEngine::shouldRepeatCtorCall(ProgramStateRef State, + const CXXConstructExpr *E, + const LocationContext *LCtx) { + + if (!E) + return false; + + auto Ty = E->getType(); + + // FIXME: Handle non constant array types + if (const auto *CAT = dyn_cast<ConstantArrayType>(Ty)) { + unsigned Size = getContext().getConstantArrayElementCount(CAT); + return Size > getIndexOfElementToConstruct(State, E, LCtx); + } + + return false; +} + static bool isTrivialObjectAssignment(const CallEvent &Call) { const CXXInstanceCall *ICall = dyn_cast<CXXInstanceCall>(&Call); if (!ICall) diff --git a/clang/lib/StaticAnalyzer/Core/MemRegion.cpp b/clang/lib/StaticAnalyzer/Core/MemRegion.cpp index f0cda835e07c..81c11099e93f 100644 --- a/clang/lib/StaticAnalyzer/Core/MemRegion.cpp +++ b/clang/lib/StaticAnalyzer/Core/MemRegion.cpp @@ -794,7 +794,11 @@ DefinedOrUnknownSVal MemRegionManager::getStaticSize(const MemRegion *MR, if (Size.isZero()) return true; + if (getContext().getLangOpts().StrictFlexArrays >= 2) + return false; + const AnalyzerOptions &Opts = SVB.getAnalyzerOptions(); + // FIXME: this option is probably redundant with -fstrict-flex-arrays=1. if (Opts.ShouldConsiderSingleElementArraysAsFlexibleArrayMembers && Size.isOne()) return true; diff --git a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp b/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp index e788a7a60830..2d4dfae1e750 100644 --- a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ b/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -1213,13 +1213,21 @@ public: } RangeSet VisitSymExpr(SymbolRef Sym) { - // If we got to this function, the actual type of the symbolic + if (Optional<RangeSet> RS = getRangeForNegatedSym(Sym)) + return *RS; + // If we've reached this line, the actual type of the symbolic // expression is not supported for advanced inference. // In this case, we simply backoff to the default "let's simply // infer the range from the expression's type". return infer(Sym->getType()); } + RangeSet VisitUnarySymExpr(const UnarySymExpr *USE) { + if (Optional<RangeSet> RS = getRangeForNegatedUnarySym(USE)) + return *RS; + return infer(USE->getType()); + } + RangeSet VisitSymIntExpr(const SymIntExpr *Sym) { return VisitBinaryOperator(Sym); } @@ -1228,14 +1236,25 @@ public: return VisitBinaryOperator(Sym); } - RangeSet VisitSymSymExpr(const SymSymExpr *Sym) { + RangeSet VisitSymSymExpr(const SymSymExpr *SSE) { return intersect( RangeFactory, + // If Sym is a difference of symbols A - B, then maybe we have range + // set stored for B - A. + // + // If we have range set stored for both A - B and B - A then + // calculate the effective range set by intersecting the range set + // for A - B and the negated range set of B - A. + getRangeForNegatedSymSym(SSE), + // If Sym is a comparison expression (except <=>), + // find any other comparisons with the same operands. + // See function description. + getRangeForComparisonSymbol(SSE), // If Sym is (dis)equality, we might have some information // on that in our equality classes data structure. - getRangeForEqualities(Sym), + getRangeForEqualities(SSE), // And we should always check what we can get from the operands. - VisitBinaryOperator(Sym)); + VisitBinaryOperator(SSE)); } private: @@ -1264,25 +1283,13 @@ private: } RangeSet infer(SymbolRef Sym) { - return intersect( - RangeFactory, - // Of course, we should take the constraint directly associated with - // this symbol into consideration. - getConstraint(State, Sym), - // If Sym is a difference of symbols A - B, then maybe we have range - // set stored for B - A. - // - // If we have range set stored for both A - B and B - A then - // calculate the effective range set by intersecting the range set - // for A - B and the negated range set of B - A. - getRangeForNegatedSub(Sym), - // If Sym is a comparison expression (except <=>), - // find any other comparisons with the same operands. - // See function description. - getRangeForComparisonSymbol(Sym), - // Apart from the Sym itself, we can infer quite a lot if we look - // into subexpressions of Sym. - Visit(Sym)); + return intersect(RangeFactory, + // Of course, we should take the constraint directly + // associated with this symbol into consideration. + getConstraint(State, Sym), + // Apart from the Sym itself, we can infer quite a lot if + // we look into subexpressions of Sym. + Visit(Sym)); } RangeSet infer(EquivalenceClass Class) { @@ -1443,38 +1450,53 @@ private: return RangeFactory.deletePoint(Domain, IntType.getZeroValue()); } - Optional<RangeSet> getRangeForNegatedSub(SymbolRef Sym) { + template <typename ProduceNegatedSymFunc> + Optional<RangeSet> getRangeForNegatedExpr(ProduceNegatedSymFunc F, + QualType T) { // Do not negate if the type cannot be meaningfully negated. - if (!Sym->getType()->isUnsignedIntegerOrEnumerationType() && - !Sym->getType()->isSignedIntegerOrEnumerationType()) + if (!T->isUnsignedIntegerOrEnumerationType() && + !T->isSignedIntegerOrEnumerationType()) return llvm::None; - const RangeSet *NegatedRange = nullptr; - SymbolManager &SymMgr = State->getSymbolManager(); - if (const auto *USE = dyn_cast<UnarySymExpr>(Sym)) { - if (USE->getOpcode() == UO_Minus) { - // Just get the operand when we negate a symbol that is already negated. - // -(-a) == a - NegatedRange = getConstraint(State, USE->getOperand()); - } - } else if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) { - if (SSE->getOpcode() == BO_Sub) { - QualType T = Sym->getType(); - SymbolRef NegatedSym = - SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T); - NegatedRange = getConstraint(State, NegatedSym); - } - } else { - SymbolRef NegatedSym = - SymMgr.getUnarySymExpr(Sym, UO_Minus, Sym->getType()); - NegatedRange = getConstraint(State, NegatedSym); - } + if (SymbolRef NegatedSym = F()) + if (const RangeSet *NegatedRange = getConstraint(State, NegatedSym)) + return RangeFactory.negate(*NegatedRange); - if (NegatedRange) - return RangeFactory.negate(*NegatedRange); return llvm::None; } + Optional<RangeSet> getRangeForNegatedUnarySym(const UnarySymExpr *USE) { + // Just get the operand when we negate a symbol that is already negated. + // -(-a) == a + return getRangeForNegatedExpr( + [USE]() -> SymbolRef { + if (USE->getOpcode() == UO_Minus) + return USE->getOperand(); + return nullptr; + }, + USE->getType()); + } + + Optional<RangeSet> getRangeForNegatedSymSym(const SymSymExpr *SSE) { + return getRangeForNegatedExpr( + [SSE, State = this->State]() -> SymbolRef { + if (SSE->getOpcode() == BO_Sub) + return State->getSymbolManager().getSymSymExpr( + SSE->getRHS(), BO_Sub, SSE->getLHS(), SSE->getType()); + return nullptr; + }, + SSE->getType()); + } + + Optional<RangeSet> getRangeForNegatedSym(SymbolRef Sym) { + return getRangeForNegatedExpr( + [Sym, State = this->State]() { + return State->getSymbolManager().getUnarySymExpr(Sym, UO_Minus, + Sym->getType()); + }, + Sym->getType()); + } + // Returns ranges only for binary comparison operators (except <=>) // when left and right operands are symbolic values. // Finds any other comparisons with the same operands. @@ -1485,11 +1507,7 @@ private: // It covers all possible combinations (see CmpOpTable description). // Note that `x` and `y` can also stand for subexpressions, // not only for actual symbols. - Optional<RangeSet> getRangeForComparisonSymbol(SymbolRef Sym) { - const auto *SSE = dyn_cast<SymSymExpr>(Sym); - if (!SSE) - return llvm::None; - + Optional<RangeSet> getRangeForComparisonSymbol(const SymSymExpr *SSE) { const BinaryOperatorKind CurrentOP = SSE->getOpcode(); // We currently do not support <=> (C++20). @@ -1801,6 +1819,8 @@ public: void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n", unsigned int Space = 0, bool IsDot = false) const override; + void printValue(raw_ostream &Out, ProgramStateRef State, + SymbolRef Sym) override; void printConstraints(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n", unsigned int Space = 0, bool IsDot = false) const; @@ -3154,6 +3174,13 @@ void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State, printDisequalities(Out, State, NL, Space, IsDot); } +void RangeConstraintManager::printValue(raw_ostream &Out, ProgramStateRef State, + SymbolRef Sym) { + const RangeSet RS = getRange(State, Sym); + Out << RS.getBitWidth() << (RS.isUnsigned() ? "u:" : "s:"); + RS.dump(Out); +} + static std::string toString(const SymbolRef &Sym) { std::string S; llvm::raw_string_ostream O(S); diff --git a/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp b/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp index cf3d13ffb7ba..d90e869196eb 100644 --- a/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp +++ b/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp @@ -19,15 +19,16 @@ #include "clang/AST/ExprObjC.h" #include "clang/AST/Stmt.h" #include "clang/AST/Type.h" -#include "clang/Basic/LLVM.h" #include "clang/Analysis/AnalysisDeclContext.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" +#include "clang/Basic/LLVM.h" #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" @@ -617,517 +618,478 @@ SVal SValBuilder::evalIntegralCast(ProgramStateRef state, SVal val, } //===----------------------------------------------------------------------===// -// Cast methods. -// `evalCast` is the main method -// `evalCastKind` and `evalCastSubKind` are helpers +// Cast method. +// `evalCast` and its helper `EvalCastVisitor` //===----------------------------------------------------------------------===// -/// Cast a given SVal to another SVal using given QualType's. -/// \param V -- SVal that should be casted. -/// \param CastTy -- QualType that V should be casted according to. -/// \param OriginalTy -- QualType which is associated to V. It provides -/// additional information about what type the cast performs from. -/// \returns the most appropriate casted SVal. -/// Note: Many cases don't use an exact OriginalTy. It can be extracted -/// from SVal or the cast can performs unconditionaly. Always pass OriginalTy! -/// It can be crucial in certain cases and generates different results. -/// FIXME: If `OriginalTy.isNull()` is true, then cast performs based on CastTy -/// only. This behavior is uncertain and should be improved. -SVal SValBuilder::evalCast(SVal V, QualType CastTy, QualType OriginalTy) { - if (CastTy.isNull()) - return V; - - CastTy = Context.getCanonicalType(CastTy); +namespace { +class EvalCastVisitor : public SValVisitor<EvalCastVisitor, SVal> { +private: + SValBuilder &VB; + ASTContext &Context; + QualType CastTy, OriginalTy; - const bool IsUnknownOriginalType = OriginalTy.isNull(); - if (!IsUnknownOriginalType) { - OriginalTy = Context.getCanonicalType(OriginalTy); +public: + EvalCastVisitor(SValBuilder &VB, QualType CastTy, QualType OriginalTy) + : VB(VB), Context(VB.getContext()), CastTy(CastTy), + OriginalTy(OriginalTy) {} - if (CastTy == OriginalTy) + SVal Visit(SVal V) { + if (CastTy.isNull()) return V; - // FIXME: Move this check to the most appropriate - // evalCastKind/evalCastSubKind function. For const casts, casts to void, - // just propagate the value. - if (!CastTy->isVariableArrayType() && !OriginalTy->isVariableArrayType()) - if (shouldBeModeledWithNoOp(Context, Context.getPointerType(CastTy), - Context.getPointerType(OriginalTy))) - return V; - } - - // Cast SVal according to kinds. - switch (V.getBaseKind()) { - case SVal::UndefinedValKind: - return evalCastKind(V.castAs<UndefinedVal>(), CastTy, OriginalTy); - case SVal::UnknownValKind: - return evalCastKind(V.castAs<UnknownVal>(), CastTy, OriginalTy); - case SVal::LocKind: - return evalCastKind(V.castAs<Loc>(), CastTy, OriginalTy); - case SVal::NonLocKind: - return evalCastKind(V.castAs<NonLoc>(), CastTy, OriginalTy); - } - - llvm_unreachable("Unknown SVal kind"); -} - -SVal SValBuilder::evalCastKind(UndefinedVal V, QualType CastTy, - QualType OriginalTy) { - return V; -} - -SVal SValBuilder::evalCastKind(UnknownVal V, QualType CastTy, - QualType OriginalTy) { - return V; -} - -SVal SValBuilder::evalCastKind(Loc V, QualType CastTy, QualType OriginalTy) { - switch (V.getSubKind()) { - case loc::ConcreteIntKind: - return evalCastSubKind(V.castAs<loc::ConcreteInt>(), CastTy, OriginalTy); - case loc::GotoLabelKind: - return evalCastSubKind(V.castAs<loc::GotoLabel>(), CastTy, OriginalTy); - case loc::MemRegionValKind: - return evalCastSubKind(V.castAs<loc::MemRegionVal>(), CastTy, OriginalTy); - } - - llvm_unreachable("Unknown SVal kind"); -} - -SVal SValBuilder::evalCastKind(NonLoc V, QualType CastTy, QualType OriginalTy) { - switch (V.getSubKind()) { - case nonloc::CompoundValKind: - return evalCastSubKind(V.castAs<nonloc::CompoundVal>(), CastTy, OriginalTy); - case nonloc::ConcreteIntKind: - return evalCastSubKind(V.castAs<nonloc::ConcreteInt>(), CastTy, OriginalTy); - case nonloc::LazyCompoundValKind: - return evalCastSubKind(V.castAs<nonloc::LazyCompoundVal>(), CastTy, - OriginalTy); - case nonloc::LocAsIntegerKind: - return evalCastSubKind(V.castAs<nonloc::LocAsInteger>(), CastTy, - OriginalTy); - case nonloc::SymbolValKind: - return evalCastSubKind(V.castAs<nonloc::SymbolVal>(), CastTy, OriginalTy); - case nonloc::PointerToMemberKind: - return evalCastSubKind(V.castAs<nonloc::PointerToMember>(), CastTy, - OriginalTy); - } + CastTy = Context.getCanonicalType(CastTy); - llvm_unreachable("Unknown SVal kind"); -} + const bool IsUnknownOriginalType = OriginalTy.isNull(); + if (!IsUnknownOriginalType) { + OriginalTy = Context.getCanonicalType(OriginalTy); -SVal SValBuilder::evalCastSubKind(loc::ConcreteInt V, QualType CastTy, - QualType OriginalTy) { - // Pointer to bool. - if (CastTy->isBooleanType()) - return makeTruthVal(V.getValue().getBoolValue(), CastTy); - - // Pointer to integer. - if (CastTy->isIntegralOrEnumerationType()) { - llvm::APSInt Value = V.getValue(); - BasicVals.getAPSIntType(CastTy).apply(Value); - return makeIntVal(Value); - } + if (CastTy == OriginalTy) + return V; - // Pointer to any pointer. - if (Loc::isLocType(CastTy)) { - llvm::APSInt Value = V.getValue(); - BasicVals.getAPSIntType(CastTy).apply(Value); - return loc::ConcreteInt(BasicVals.getValue(Value)); + // FIXME: Move this check to the most appropriate + // evalCastKind/evalCastSubKind function. For const casts, casts to void, + // just propagate the value. + if (!CastTy->isVariableArrayType() && !OriginalTy->isVariableArrayType()) + if (shouldBeModeledWithNoOp(Context, Context.getPointerType(CastTy), + Context.getPointerType(OriginalTy))) + return V; + } + return SValVisitor::Visit(V); } + SVal VisitUndefinedVal(UndefinedVal V) { return V; } + SVal VisitUnknownVal(UnknownVal V) { return V; } + SVal VisitLocConcreteInt(loc::ConcreteInt V) { + // Pointer to bool. + if (CastTy->isBooleanType()) + return VB.makeTruthVal(V.getValue().getBoolValue(), CastTy); + + // Pointer to integer. + if (CastTy->isIntegralOrEnumerationType()) { + llvm::APSInt Value = V.getValue(); + VB.getBasicValueFactory().getAPSIntType(CastTy).apply(Value); + return VB.makeIntVal(Value); + } - // Pointer to whatever else. - return UnknownVal(); -} - -SVal SValBuilder::evalCastSubKind(loc::GotoLabel V, QualType CastTy, - QualType OriginalTy) { - // Pointer to bool. - if (CastTy->isBooleanType()) - // Labels are always true. - return makeTruthVal(true, CastTy); - - // Pointer to integer. - if (CastTy->isIntegralOrEnumerationType()) { - const unsigned BitWidth = Context.getIntWidth(CastTy); - return makeLocAsInteger(V, BitWidth); - } + // Pointer to any pointer. + if (Loc::isLocType(CastTy)) { + llvm::APSInt Value = V.getValue(); + VB.getBasicValueFactory().getAPSIntType(CastTy).apply(Value); + return loc::ConcreteInt(VB.getBasicValueFactory().getValue(Value)); + } - const bool IsUnknownOriginalType = OriginalTy.isNull(); - if (!IsUnknownOriginalType) { - // Array to pointer. - if (isa<ArrayType>(OriginalTy)) - if (CastTy->isPointerType() || CastTy->isReferenceType()) - return UnknownVal(); + // Pointer to whatever else. + return UnknownVal(); } - - // Pointer to any pointer. - if (Loc::isLocType(CastTy)) - return V; - - // Pointer to whatever else. - return UnknownVal(); -} - -static bool hasSameUnqualifiedPointeeType(QualType ty1, QualType ty2) { - return ty1->getPointeeType().getCanonicalType().getTypePtr() == - ty2->getPointeeType().getCanonicalType().getTypePtr(); -} - -SVal SValBuilder::evalCastSubKind(loc::MemRegionVal V, QualType CastTy, - QualType OriginalTy) { - // Pointer to bool. - if (CastTy->isBooleanType()) { - const MemRegion *R = V.getRegion(); - if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(R)) - if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl())) - if (FD->isWeak()) - // FIXME: Currently we are using an extent symbol here, - // because there are no generic region address metadata - // symbols to use, only content metadata. - return nonloc::SymbolVal(SymMgr.getExtentSymbol(FTR)); - - if (const SymbolicRegion *SymR = R->getSymbolicBase()) { - SymbolRef Sym = SymR->getSymbol(); - QualType Ty = Sym->getType(); - // This change is needed for architectures with varying - // pointer widths. See the amdgcn opencl reproducer with - // this change as an example: solver-sym-simplification-ptr-bool.cl - if (!Ty->isReferenceType()) - return makeNonLoc(Sym, BO_NE, BasicVals.getZeroWithTypeSize(Ty), - CastTy); + SVal VisitLocGotoLabel(loc::GotoLabel V) { + // Pointer to bool. + if (CastTy->isBooleanType()) + // Labels are always true. + return VB.makeTruthVal(true, CastTy); + + // Pointer to integer. + if (CastTy->isIntegralOrEnumerationType()) { + const unsigned BitWidth = Context.getIntWidth(CastTy); + return VB.makeLocAsInteger(V, BitWidth); } - // Non-symbolic memory regions are always true. - return makeTruthVal(true, CastTy); - } - const bool IsUnknownOriginalType = OriginalTy.isNull(); - // Try to cast to array - const auto *ArrayTy = - IsUnknownOriginalType - ? nullptr - : dyn_cast<ArrayType>(OriginalTy.getCanonicalType()); - - // Pointer to integer. - if (CastTy->isIntegralOrEnumerationType()) { - SVal Val = V; - // Array to integer. - if (ArrayTy) { - // We will always decay to a pointer. - QualType ElemTy = ArrayTy->getElementType(); - Val = StateMgr.ArrayToPointer(V, ElemTy); - // FIXME: Keep these here for now in case we decide soon that we - // need the original decayed type. - // QualType elemTy = cast<ArrayType>(originalTy)->getElementType(); - // QualType pointerTy = C.getPointerType(elemTy); + const bool IsUnknownOriginalType = OriginalTy.isNull(); + if (!IsUnknownOriginalType) { + // Array to pointer. + if (isa<ArrayType>(OriginalTy)) + if (CastTy->isPointerType() || CastTy->isReferenceType()) + return UnknownVal(); } - const unsigned BitWidth = Context.getIntWidth(CastTy); - return makeLocAsInteger(Val.castAs<Loc>(), BitWidth); - } - // Pointer to pointer. - if (Loc::isLocType(CastTy)) { - - if (IsUnknownOriginalType) { - // When retrieving symbolic pointer and expecting a non-void pointer, - // wrap them into element regions of the expected type if necessary. - // It is necessary to make sure that the retrieved value makes sense, - // because there's no other cast in the AST that would tell us to cast - // it to the correct pointer type. We might need to do that for non-void - // pointers as well. - // FIXME: We really need a single good function to perform casts for us - // correctly every time we need it. + // Pointer to any pointer. + if (Loc::isLocType(CastTy)) + return V; + + // Pointer to whatever else. + return UnknownVal(); + } + SVal VisitLocMemRegionVal(loc::MemRegionVal V) { + // Pointer to bool. + if (CastTy->isBooleanType()) { const MemRegion *R = V.getRegion(); - if (CastTy->isPointerType() && !CastTy->isVoidPointerType()) { - if (const auto *SR = dyn_cast<SymbolicRegion>(R)) { - QualType SRTy = SR->getSymbol()->getType(); - if (!hasSameUnqualifiedPointeeType(SRTy, CastTy)) { - if (auto OptMemRegV = getCastedMemRegionVal(SR, CastTy)) - return *OptMemRegV; - } - } - } - // Next fixes pointer dereference using type different from its initial - // one. See PR37503 and PR49007 for details. - if (const auto *ER = dyn_cast<ElementRegion>(R)) { - if (auto OptMemRegV = getCastedMemRegionVal(ER, CastTy)) - return *OptMemRegV; + if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(R)) + if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl())) + if (FD->isWeak()) + // FIXME: Currently we are using an extent symbol here, + // because there are no generic region address metadata + // symbols to use, only content metadata. + return nonloc::SymbolVal( + VB.getSymbolManager().getExtentSymbol(FTR)); + + if (const SymbolicRegion *SymR = R->getSymbolicBase()) { + SymbolRef Sym = SymR->getSymbol(); + QualType Ty = Sym->getType(); + // This change is needed for architectures with varying + // pointer widths. See the amdgcn opencl reproducer with + // this change as an example: solver-sym-simplification-ptr-bool.cl + if (!Ty->isReferenceType()) + return VB.makeNonLoc( + Sym, BO_NE, VB.getBasicValueFactory().getZeroWithTypeSize(Ty), + CastTy); } - - return V; + // Non-symbolic memory regions are always true. + return VB.makeTruthVal(true, CastTy); } - if (OriginalTy->isIntegralOrEnumerationType() || - OriginalTy->isBlockPointerType() || OriginalTy->isFunctionPointerType()) - return V; - - // Array to pointer. - if (ArrayTy) { - // Are we casting from an array to a pointer? If so just pass on - // the decayed value. - if (CastTy->isPointerType() || CastTy->isReferenceType()) { + const bool IsUnknownOriginalType = OriginalTy.isNull(); + // Try to cast to array + const auto *ArrayTy = + IsUnknownOriginalType + ? nullptr + : dyn_cast<ArrayType>(OriginalTy.getCanonicalType()); + + // Pointer to integer. + if (CastTy->isIntegralOrEnumerationType()) { + SVal Val = V; + // Array to integer. + if (ArrayTy) { // We will always decay to a pointer. QualType ElemTy = ArrayTy->getElementType(); - return StateMgr.ArrayToPointer(V, ElemTy); + Val = VB.getStateManager().ArrayToPointer(V, ElemTy); + // FIXME: Keep these here for now in case we decide soon that we + // need the original decayed type. + // QualType elemTy = cast<ArrayType>(originalTy)->getElementType(); + // QualType pointerTy = C.getPointerType(elemTy); } - // Are we casting from an array to an integer? If so, cast the decayed - // pointer value to an integer. - assert(CastTy->isIntegralOrEnumerationType()); + const unsigned BitWidth = Context.getIntWidth(CastTy); + return VB.makeLocAsInteger(Val.castAs<Loc>(), BitWidth); } - // Other pointer to pointer. - assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() || - CastTy->isReferenceType()); + // Pointer to pointer. + if (Loc::isLocType(CastTy)) { - // We get a symbolic function pointer for a dereference of a function - // pointer, but it is of function type. Example: + if (IsUnknownOriginalType) { + // When retrieving symbolic pointer and expecting a non-void pointer, + // wrap them into element regions of the expected type if necessary. + // It is necessary to make sure that the retrieved value makes sense, + // because there's no other cast in the AST that would tell us to cast + // it to the correct pointer type. We might need to do that for non-void + // pointers as well. + // FIXME: We really need a single good function to perform casts for us + // correctly every time we need it. + const MemRegion *R = V.getRegion(); + if (CastTy->isPointerType() && !CastTy->isVoidPointerType()) { + if (const auto *SR = dyn_cast<SymbolicRegion>(R)) { + QualType SRTy = SR->getSymbol()->getType(); + + auto HasSameUnqualifiedPointeeType = [](QualType ty1, + QualType ty2) { + return ty1->getPointeeType().getCanonicalType().getTypePtr() == + ty2->getPointeeType().getCanonicalType().getTypePtr(); + }; + if (!HasSameUnqualifiedPointeeType(SRTy, CastTy)) { + if (auto OptMemRegV = VB.getCastedMemRegionVal(SR, CastTy)) + return *OptMemRegV; + } + } + } + // Next fixes pointer dereference using type different from its initial + // one. See PR37503 and PR49007 for details. + if (const auto *ER = dyn_cast<ElementRegion>(R)) { + if (auto OptMemRegV = VB.getCastedMemRegionVal(ER, CastTy)) + return *OptMemRegV; + } - // struct FPRec { - // void (*my_func)(int * x); - // }; - // - // int bar(int x); - // - // int f1_a(struct FPRec* foo) { - // int x; - // (*foo->my_func)(&x); - // return bar(x)+1; // no-warning - // } - - // Get the result of casting a region to a different type. - const MemRegion *R = V.getRegion(); - if (auto OptMemRegV = getCastedMemRegionVal(R, CastTy)) - return *OptMemRegV; - } + return V; + } - // Pointer to whatever else. - // FIXME: There can be gross cases where one casts the result of a - // function (that returns a pointer) to some other value that happens to - // fit within that pointer value. We currently have no good way to model - // such operations. When this happens, the underlying operation is that - // the caller is reasoning about bits. Conceptually we are layering a - // "view" of a location on top of those bits. Perhaps we need to be more - // lazy about mutual possible views, even on an SVal? This may be - // necessary for bit-level reasoning as well. - return UnknownVal(); -} + if (OriginalTy->isIntegralOrEnumerationType() || + OriginalTy->isBlockPointerType() || + OriginalTy->isFunctionPointerType()) + return V; -SVal SValBuilder::evalCastSubKind(nonloc::CompoundVal V, QualType CastTy, - QualType OriginalTy) { - // Compound to whatever. - return UnknownVal(); -} + // Array to pointer. + if (ArrayTy) { + // Are we casting from an array to a pointer? If so just pass on + // the decayed value. + if (CastTy->isPointerType() || CastTy->isReferenceType()) { + // We will always decay to a pointer. + QualType ElemTy = ArrayTy->getElementType(); + return VB.getStateManager().ArrayToPointer(V, ElemTy); + } + // Are we casting from an array to an integer? If so, cast the decayed + // pointer value to an integer. + assert(CastTy->isIntegralOrEnumerationType()); + } -SVal SValBuilder::evalCastSubKind(nonloc::ConcreteInt V, QualType CastTy, - QualType OriginalTy) { - auto CastedValue = [V, CastTy, this]() { - llvm::APSInt Value = V.getValue(); - BasicVals.getAPSIntType(CastTy).apply(Value); - return Value; - }; + // Other pointer to pointer. + assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() || + CastTy->isReferenceType()); - // Integer to bool. - if (CastTy->isBooleanType()) - return makeTruthVal(V.getValue().getBoolValue(), CastTy); + // We get a symbolic function pointer for a dereference of a function + // pointer, but it is of function type. Example: + + // struct FPRec { + // void (*my_func)(int * x); + // }; + // + // int bar(int x); + // + // int f1_a(struct FPRec* foo) { + // int x; + // (*foo->my_func)(&x); + // return bar(x)+1; // no-warning + // } + + // Get the result of casting a region to a different type. + const MemRegion *R = V.getRegion(); + if (auto OptMemRegV = VB.getCastedMemRegionVal(R, CastTy)) + return *OptMemRegV; + } - // Integer to pointer. - if (CastTy->isIntegralOrEnumerationType()) - return makeIntVal(CastedValue()); + // Pointer to whatever else. + // FIXME: There can be gross cases where one casts the result of a + // function (that returns a pointer) to some other value that happens to + // fit within that pointer value. We currently have no good way to model + // such operations. When this happens, the underlying operation is that + // the caller is reasoning about bits. Conceptually we are layering a + // "view" of a location on top of those bits. Perhaps we need to be more + // lazy about mutual possible views, even on an SVal? This may be + // necessary for bit-level reasoning as well. + return UnknownVal(); + } + SVal VisitNonLocCompoundVal(nonloc::CompoundVal V) { + // Compound to whatever. + return UnknownVal(); + } + SVal VisitNonLocConcreteInt(nonloc::ConcreteInt V) { + auto CastedValue = [V, this]() { + llvm::APSInt Value = V.getValue(); + VB.getBasicValueFactory().getAPSIntType(CastTy).apply(Value); + return Value; + }; - // Integer to pointer. - if (Loc::isLocType(CastTy)) - return makeIntLocVal(CastedValue()); + // Integer to bool. + if (CastTy->isBooleanType()) + return VB.makeTruthVal(V.getValue().getBoolValue(), CastTy); - // Pointer to whatever else. - return UnknownVal(); -} + // Integer to pointer. + if (CastTy->isIntegralOrEnumerationType()) + return VB.makeIntVal(CastedValue()); -SVal SValBuilder::evalCastSubKind(nonloc::LazyCompoundVal V, QualType CastTy, - QualType OriginalTy) { - // Compound to whatever. - return UnknownVal(); -} + // Integer to pointer. + if (Loc::isLocType(CastTy)) + return VB.makeIntLocVal(CastedValue()); -SVal SValBuilder::evalCastSubKind(nonloc::LocAsInteger V, QualType CastTy, - QualType OriginalTy) { - Loc L = V.getLoc(); - - // Pointer as integer to bool. - if (CastTy->isBooleanType()) - // Pass to Loc function. - return evalCastKind(L, CastTy, OriginalTy); - - const bool IsUnknownOriginalType = OriginalTy.isNull(); - // Pointer as integer to pointer. - if (!IsUnknownOriginalType && Loc::isLocType(CastTy) && - OriginalTy->isIntegralOrEnumerationType()) { - if (const MemRegion *R = L.getAsRegion()) - if (auto OptMemRegV = getCastedMemRegionVal(R, CastTy)) - return *OptMemRegV; - return L; + // Pointer to whatever else. + return UnknownVal(); } - - // Pointer as integer with region to integer/pointer. - const MemRegion *R = L.getAsRegion(); - if (!IsUnknownOriginalType && R) { - if (CastTy->isIntegralOrEnumerationType()) - return evalCastSubKind(loc::MemRegionVal(R), CastTy, OriginalTy); - - if (Loc::isLocType(CastTy)) { - assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() || - CastTy->isReferenceType()); - // Delegate to store manager to get the result of casting a region to a - // different type. If the MemRegion* returned is NULL, this expression - // Evaluates to UnknownVal. - if (auto OptMemRegV = getCastedMemRegionVal(R, CastTy)) - return *OptMemRegV; - } - } else { - if (Loc::isLocType(CastTy)) { - if (IsUnknownOriginalType) - return evalCastSubKind(loc::MemRegionVal(R), CastTy, OriginalTy); + SVal VisitNonLocLazyCompoundVal(nonloc::LazyCompoundVal V) { + // LazyCompound to whatever. + return UnknownVal(); + } + SVal VisitNonLocLocAsInteger(nonloc::LocAsInteger V) { + Loc L = V.getLoc(); + + // Pointer as integer to bool. + if (CastTy->isBooleanType()) + // Pass to Loc function. + return Visit(L); + + const bool IsUnknownOriginalType = OriginalTy.isNull(); + // Pointer as integer to pointer. + if (!IsUnknownOriginalType && Loc::isLocType(CastTy) && + OriginalTy->isIntegralOrEnumerationType()) { + if (const MemRegion *R = L.getAsRegion()) + if (auto OptMemRegV = VB.getCastedMemRegionVal(R, CastTy)) + return *OptMemRegV; return L; } - SymbolRef SE = nullptr; - if (R) { - if (const SymbolicRegion *SR = - dyn_cast<SymbolicRegion>(R->StripCasts())) { - SE = SR->getSymbol(); + // Pointer as integer with region to integer/pointer. + const MemRegion *R = L.getAsRegion(); + if (!IsUnknownOriginalType && R) { + if (CastTy->isIntegralOrEnumerationType()) + return VisitLocMemRegionVal(loc::MemRegionVal(R)); + + if (Loc::isLocType(CastTy)) { + assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() || + CastTy->isReferenceType()); + // Delegate to store manager to get the result of casting a region to a + // different type. If the MemRegion* returned is NULL, this expression + // Evaluates to UnknownVal. + if (auto OptMemRegV = VB.getCastedMemRegionVal(R, CastTy)) + return *OptMemRegV; + } + } else { + if (Loc::isLocType(CastTy)) { + if (IsUnknownOriginalType) + return VisitLocMemRegionVal(loc::MemRegionVal(R)); + return L; } - } - - if (!CastTy->isFloatingType() || !SE || SE->getType()->isFloatingType()) { - // FIXME: Correctly support promotions/truncations. - const unsigned CastSize = Context.getIntWidth(CastTy); - if (CastSize == V.getNumBits()) - return V; - return makeLocAsInteger(L, CastSize); - } - } + SymbolRef SE = nullptr; + if (R) { + if (const SymbolicRegion *SR = + dyn_cast<SymbolicRegion>(R->StripCasts())) { + SE = SR->getSymbol(); + } + } - // Pointer as integer to whatever else. - return UnknownVal(); -} + if (!CastTy->isFloatingType() || !SE || SE->getType()->isFloatingType()) { + // FIXME: Correctly support promotions/truncations. + const unsigned CastSize = Context.getIntWidth(CastTy); + if (CastSize == V.getNumBits()) + return V; -SVal SValBuilder::evalCastSubKind(nonloc::SymbolVal V, QualType CastTy, - QualType OriginalTy) { - SymbolRef SE = V.getSymbol(); - - const bool IsUnknownOriginalType = OriginalTy.isNull(); - // Symbol to bool. - if (!IsUnknownOriginalType && CastTy->isBooleanType()) { - // Non-float to bool. - if (Loc::isLocType(OriginalTy) || - OriginalTy->isIntegralOrEnumerationType() || - OriginalTy->isMemberPointerType()) { - BasicValueFactory &BVF = getBasicValueFactory(); - return makeNonLoc(SE, BO_NE, BVF.getValue(0, SE->getType()), CastTy); + return VB.makeLocAsInteger(L, CastSize); + } } - } else { - // Symbol to integer, float. - QualType T = Context.getCanonicalType(SE->getType()); - // Produce SymbolCast if CastTy and T are different integers. - // NOTE: In the end the type of SymbolCast shall be equal to CastTy. - if (T->isIntegralOrUnscopedEnumerationType() && - CastTy->isIntegralOrUnscopedEnumerationType()) { - AnalyzerOptions &Opts = - StateMgr.getOwningEngine().getAnalysisManager().getAnalyzerOptions(); - // If appropriate option is disabled, ignore the cast. - // NOTE: ShouldSupportSymbolicIntegerCasts is `false` by default. - if (!Opts.ShouldSupportSymbolicIntegerCasts) - return V; - return simplifySymbolCast(V, CastTy); + // Pointer as integer to whatever else. + return UnknownVal(); + } + SVal VisitNonLocSymbolVal(nonloc::SymbolVal V) { + SymbolRef SE = V.getSymbol(); + + const bool IsUnknownOriginalType = OriginalTy.isNull(); + // Symbol to bool. + if (!IsUnknownOriginalType && CastTy->isBooleanType()) { + // Non-float to bool. + if (Loc::isLocType(OriginalTy) || + OriginalTy->isIntegralOrEnumerationType() || + OriginalTy->isMemberPointerType()) { + BasicValueFactory &BVF = VB.getBasicValueFactory(); + return VB.makeNonLoc(SE, BO_NE, BVF.getValue(0, SE->getType()), CastTy); + } + } else { + // Symbol to integer, float. + QualType T = Context.getCanonicalType(SE->getType()); + + // Produce SymbolCast if CastTy and T are different integers. + // NOTE: In the end the type of SymbolCast shall be equal to CastTy. + if (T->isIntegralOrUnscopedEnumerationType() && + CastTy->isIntegralOrUnscopedEnumerationType()) { + AnalyzerOptions &Opts = VB.getStateManager() + .getOwningEngine() + .getAnalysisManager() + .getAnalyzerOptions(); + // If appropriate option is disabled, ignore the cast. + // NOTE: ShouldSupportSymbolicIntegerCasts is `false` by default. + if (!Opts.ShouldSupportSymbolicIntegerCasts) + return V; + return simplifySymbolCast(V, CastTy); + } + if (!Loc::isLocType(CastTy)) + if (!IsUnknownOriginalType || !CastTy->isFloatingType() || + T->isFloatingType()) + return VB.makeNonLoc(SE, T, CastTy); } - if (!Loc::isLocType(CastTy)) - if (!IsUnknownOriginalType || !CastTy->isFloatingType() || - T->isFloatingType()) - return makeNonLoc(SE, T, CastTy); + + // Symbol to pointer and whatever else. + return UnknownVal(); + } + SVal VisitNonLocPointerToMember(nonloc::PointerToMember V) { + // Member pointer to whatever. + return V; } - // Symbol to pointer and whatever else. - return UnknownVal(); -} + /// Reduce cast expression by removing redundant intermediate casts. + /// E.g. + /// - (char)(short)(int x) -> (char)(int x) + /// - (int)(int x) -> int x + /// + /// \param V -- SymbolVal, which pressumably contains SymbolCast or any symbol + /// that is applicable for cast operation. + /// \param CastTy -- QualType, which `V` shall be cast to. + /// \return SVal with simplified cast expression. + /// \note: Currently only support integral casts. + nonloc::SymbolVal simplifySymbolCast(nonloc::SymbolVal V, QualType CastTy) { + // We use seven conditions to recognize a simplification case. + // For the clarity let `CastTy` be `C`, SE->getType() - `T`, root type - + // `R`, prefix `u` for unsigned, `s` for signed, no prefix - any sign: E.g. + // (char)(short)(uint x) + // ( sC )( sT )( uR x) + // + // C === R (the same type) + // (char)(char x) -> (char x) + // (long)(long x) -> (long x) + // Note: Comparisons operators below are for bit width. + // C == T + // (short)(short)(int x) -> (short)(int x) + // (int)(long)(char x) -> (int)(char x) (sizeof(long) == sizeof(int)) + // (long)(ullong)(char x) -> (long)(char x) (sizeof(long) == + // sizeof(ullong)) + // C < T + // (short)(int)(char x) -> (short)(char x) + // (char)(int)(short x) -> (char)(short x) + // (short)(int)(short x) -> (short x) + // C > T > uR + // (int)(short)(uchar x) -> (int)(uchar x) + // (uint)(short)(uchar x) -> (uint)(uchar x) + // (int)(ushort)(uchar x) -> (int)(uchar x) + // C > sT > sR + // (int)(short)(char x) -> (int)(char x) + // (uint)(short)(char x) -> (uint)(char x) + // C > sT == sR + // (int)(char)(char x) -> (int)(char x) + // (uint)(short)(short x) -> (uint)(short x) + // C > uT == uR + // (int)(uchar)(uchar x) -> (int)(uchar x) + // (uint)(ushort)(ushort x) -> (uint)(ushort x) + // (llong)(ulong)(uint x) -> (llong)(uint x) (sizeof(ulong) == + // sizeof(uint)) + + SymbolRef SE = V.getSymbol(); + QualType T = Context.getCanonicalType(SE->getType()); -SVal SValBuilder::evalCastSubKind(nonloc::PointerToMember V, QualType CastTy, - QualType OriginalTy) { - // Member pointer to whatever. - return V; -} + if (T == CastTy) + return V; -nonloc::SymbolVal SValBuilder::simplifySymbolCast(nonloc::SymbolVal V, - QualType CastTy) { - // We use seven conditions to recognize a simplification case. - // For the clarity let `CastTy` be `C`, SE->getType() - `T`, root type - `R`, - // prefix `u` for unsigned, `s` for signed, no prefix - any sign: - // E.g. (char)(short)(uint x) - // ( sC )( sT )( uR x) - // - // C === R (the same type) - // (char)(char x) -> (char x) - // (long)(long x) -> (long x) - // Note: Comparisons operators below are for bit width. - // C == T - // (short)(short)(int x) -> (short)(int x) - // (int)(long)(char x) -> (int)(char x) (sizeof(long) == sizeof(int)) - // (long)(ullong)(char x) -> (long)(char x) (sizeof(long) == sizeof(ullong)) - // C < T - // (short)(int)(char x) -> (short)(char x) - // (char)(int)(short x) -> (char)(short x) - // (short)(int)(short x) -> (short x) - // C > T > uR - // (int)(short)(uchar x) -> (int)(uchar x) - // (uint)(short)(uchar x) -> (uint)(uchar x) - // (int)(ushort)(uchar x) -> (int)(uchar x) - // C > sT > sR - // (int)(short)(char x) -> (int)(char x) - // (uint)(short)(char x) -> (uint)(char x) - // C > sT == sR - // (int)(char)(char x) -> (int)(char x) - // (uint)(short)(short x) -> (uint)(short x) - // C > uT == uR - // (int)(uchar)(uchar x) -> (int)(uchar x) - // (uint)(ushort)(ushort x) -> (uint)(ushort x) - // (llong)(ulong)(uint x) -> (llong)(uint x) (sizeof(ulong) == sizeof(uint)) - - SymbolRef SE = V.getSymbol(); - QualType T = Context.getCanonicalType(SE->getType()); - - if (T == CastTy) - return V; + if (!isa<SymbolCast>(SE)) + return VB.makeNonLoc(SE, T, CastTy); - if (!isa<SymbolCast>(SE)) - return makeNonLoc(SE, T, CastTy); + SymbolRef RootSym = cast<SymbolCast>(SE)->getOperand(); + QualType RT = RootSym->getType().getCanonicalType(); - SymbolRef RootSym = cast<SymbolCast>(SE)->getOperand(); - QualType RT = RootSym->getType().getCanonicalType(); + // FIXME support simplification from non-integers. + if (!RT->isIntegralOrEnumerationType()) + return VB.makeNonLoc(SE, T, CastTy); - // FIXME support simplification from non-integers. - if (!RT->isIntegralOrEnumerationType()) - return makeNonLoc(SE, T, CastTy); + BasicValueFactory &BVF = VB.getBasicValueFactory(); + APSIntType CTy = BVF.getAPSIntType(CastTy); + APSIntType TTy = BVF.getAPSIntType(T); - BasicValueFactory &BVF = getBasicValueFactory(); - APSIntType CTy = BVF.getAPSIntType(CastTy); - APSIntType TTy = BVF.getAPSIntType(T); + const auto WC = CTy.getBitWidth(); + const auto WT = TTy.getBitWidth(); - const auto WC = CTy.getBitWidth(); - const auto WT = TTy.getBitWidth(); + if (WC <= WT) { + const bool isSameType = (RT == CastTy); + if (isSameType) + return nonloc::SymbolVal(RootSym); + return VB.makeNonLoc(RootSym, RT, CastTy); + } - if (WC <= WT) { - const bool isSameType = (RT == CastTy); - if (isSameType) - return nonloc::SymbolVal(RootSym); - return makeNonLoc(RootSym, RT, CastTy); - } + APSIntType RTy = BVF.getAPSIntType(RT); + const auto WR = RTy.getBitWidth(); + const bool UT = TTy.isUnsigned(); + const bool UR = RTy.isUnsigned(); - APSIntType RTy = BVF.getAPSIntType(RT); - const auto WR = RTy.getBitWidth(); - const bool UT = TTy.isUnsigned(); - const bool UR = RTy.isUnsigned(); + if (((WT > WR) && (UR || !UT)) || ((WT == WR) && (UT == UR))) + return VB.makeNonLoc(RootSym, RT, CastTy); - if (((WT > WR) && (UR || !UT)) || ((WT == WR) && (UT == UR))) - return makeNonLoc(RootSym, RT, CastTy); + return VB.makeNonLoc(SE, T, CastTy); + } +}; +} // end anonymous namespace - return makeNonLoc(SE, T, CastTy); +/// Cast a given SVal to another SVal using given QualType's. +/// \param V -- SVal that should be casted. +/// \param CastTy -- QualType that V should be casted according to. +/// \param OriginalTy -- QualType which is associated to V. It provides +/// additional information about what type the cast performs from. +/// \returns the most appropriate casted SVal. +/// Note: Many cases don't use an exact OriginalTy. It can be extracted +/// from SVal or the cast can performs unconditionaly. Always pass OriginalTy! +/// It can be crucial in certain cases and generates different results. +/// FIXME: If `OriginalTy.isNull()` is true, then cast performs based on CastTy +/// only. This behavior is uncertain and should be improved. +SVal SValBuilder::evalCast(SVal V, QualType CastTy, QualType OriginalTy) { + EvalCastVisitor TRV{*this, CastTy, OriginalTy}; + return TRV.Visit(V); } diff --git a/clang/lib/StaticAnalyzer/Core/SVals.cpp b/clang/lib/StaticAnalyzer/Core/SVals.cpp index 67913a55b3dc..31725926cd0d 100644 --- a/clang/lib/StaticAnalyzer/Core/SVals.cpp +++ b/clang/lib/StaticAnalyzer/Core/SVals.cpp @@ -109,6 +109,14 @@ SymbolRef SVal::getAsSymbol(bool IncludeBaseRegions) const { return getAsLocSymbol(IncludeBaseRegions); } +const llvm::APSInt *SVal::getAsInteger() const { + if (auto CI = getAs<nonloc::ConcreteInt>()) + return &CI->getValue(); + if (auto CI = getAs<loc::ConcreteInt>()) + return &CI->getValue(); + return nullptr; +} + const MemRegion *SVal::getAsRegion() const { if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>()) return X->getRegion(); @@ -136,6 +144,8 @@ public: } template <class ConcreteInt> QualType VisitConcreteInt(ConcreteInt CI) { const llvm::APSInt &Value = CI.getValue(); + if (1 == Value.getBitWidth()) + return Context.BoolTy; return Context.getIntTypeForBitwidth(Value.getBitWidth(), Value.isSigned()); } QualType VisitLocConcreteInt(loc::ConcreteInt CI) { |