1153 lines · cpp
1//=-- ExprEngineC.cpp - ExprEngine support for C expressions ----*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines ExprEngine's support for C expressions.10//11//===----------------------------------------------------------------------===//12 13#include "clang/AST/DeclCXX.h"14#include "clang/AST/ExprCXX.h"15#include "clang/StaticAnalyzer/Core/CheckerManager.h"16#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"17#include <optional>18 19using namespace clang;20using namespace ento;21using llvm::APSInt;22 23/// Optionally conjure and return a symbol for offset when processing24/// \p Elem.25/// If \p Other is a location, conjure a symbol for \p Symbol26/// (offset) if it is unknown so that memory arithmetic always27/// results in an ElementRegion.28/// \p Count The number of times the current basic block was visited.29static SVal conjureOffsetSymbolOnLocation(SVal Symbol, SVal Other,30 ConstCFGElementRef Elem, QualType Ty,31 SValBuilder &svalBuilder,32 unsigned Count,33 const LocationContext *LCtx) {34 if (isa<Loc>(Other) && Ty->isIntegralOrEnumerationType() &&35 Symbol.isUnknown()) {36 return svalBuilder.conjureSymbolVal(Elem, LCtx, Ty, Count);37 }38 return Symbol;39}40 41void ExprEngine::VisitBinaryOperator(const BinaryOperator* B,42 ExplodedNode *Pred,43 ExplodedNodeSet &Dst) {44 45 Expr *LHS = B->getLHS()->IgnoreParens();46 Expr *RHS = B->getRHS()->IgnoreParens();47 48 // FIXME: Prechecks eventually go in ::Visit().49 ExplodedNodeSet CheckedSet;50 ExplodedNodeSet Tmp2;51 getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, B, *this);52 53 // With both the LHS and RHS evaluated, process the operation itself.54 for (ExplodedNodeSet::iterator it=CheckedSet.begin(), ei=CheckedSet.end();55 it != ei; ++it) {56 57 ProgramStateRef state = (*it)->getState();58 const LocationContext *LCtx = (*it)->getLocationContext();59 SVal LeftV = state->getSVal(LHS, LCtx);60 SVal RightV = state->getSVal(RHS, LCtx);61 62 BinaryOperator::Opcode Op = B->getOpcode();63 64 if (Op == BO_Assign) {65 // EXPERIMENTAL: "Conjured" symbols.66 // FIXME: Handle structs.67 if (RightV.isUnknown()) {68 unsigned Count = currBldrCtx->blockCount();69 RightV = svalBuilder.conjureSymbolVal(nullptr, getCFGElementRef(), LCtx,70 Count);71 }72 // Simulate the effects of a "store": bind the value of the RHS73 // to the L-Value represented by the LHS.74 SVal ExprVal = B->isGLValue() ? LeftV : RightV;75 evalStore(Tmp2, B, LHS, *it, state->BindExpr(B, LCtx, ExprVal),76 LeftV, RightV);77 continue;78 }79 80 if (!B->isAssignmentOp()) {81 StmtNodeBuilder Bldr(*it, Tmp2, *currBldrCtx);82 83 if (B->isAdditiveOp()) {84 // TODO: This can be removed after we enable history tracking with85 // SymSymExpr.86 unsigned Count = currBldrCtx->blockCount();87 RightV = conjureOffsetSymbolOnLocation(88 RightV, LeftV, getCFGElementRef(), RHS->getType(), svalBuilder,89 Count, LCtx);90 LeftV = conjureOffsetSymbolOnLocation(LeftV, RightV, getCFGElementRef(),91 LHS->getType(), svalBuilder,92 Count, LCtx);93 }94 95 // Although we don't yet model pointers-to-members, we do need to make96 // sure that the members of temporaries have a valid 'this' pointer for97 // other checks.98 if (B->getOpcode() == BO_PtrMemD)99 state = createTemporaryRegionIfNeeded(state, LCtx, LHS);100 101 // Process non-assignments except commas or short-circuited102 // logical expressions (LAnd and LOr).103 SVal Result = evalBinOp(state, Op, LeftV, RightV, B->getType());104 if (!Result.isUnknown()) {105 state = state->BindExpr(B, LCtx, Result);106 } else {107 // If we cannot evaluate the operation escape the operands.108 state = escapeValues(state, LeftV, PSK_EscapeOther);109 state = escapeValues(state, RightV, PSK_EscapeOther);110 }111 112 Bldr.generateNode(B, *it, state);113 continue;114 }115 116 assert (B->isCompoundAssignmentOp());117 118 switch (Op) {119 default:120 llvm_unreachable("Invalid opcode for compound assignment.");121 case BO_MulAssign: Op = BO_Mul; break;122 case BO_DivAssign: Op = BO_Div; break;123 case BO_RemAssign: Op = BO_Rem; break;124 case BO_AddAssign: Op = BO_Add; break;125 case BO_SubAssign: Op = BO_Sub; break;126 case BO_ShlAssign: Op = BO_Shl; break;127 case BO_ShrAssign: Op = BO_Shr; break;128 case BO_AndAssign: Op = BO_And; break;129 case BO_XorAssign: Op = BO_Xor; break;130 case BO_OrAssign: Op = BO_Or; break;131 }132 133 // Perform a load (the LHS). This performs the checks for134 // null dereferences, and so on.135 ExplodedNodeSet Tmp;136 SVal location = LeftV;137 evalLoad(Tmp, B, LHS, *it, state, location);138 139 for (ExplodedNode *N : Tmp) {140 state = N->getState();141 const LocationContext *LCtx = N->getLocationContext();142 SVal V = state->getSVal(LHS, LCtx);143 144 // Get the computation type.145 QualType CTy =146 cast<CompoundAssignOperator>(B)->getComputationResultType();147 CTy = getContext().getCanonicalType(CTy);148 149 QualType CLHSTy =150 cast<CompoundAssignOperator>(B)->getComputationLHSType();151 CLHSTy = getContext().getCanonicalType(CLHSTy);152 153 QualType LTy = getContext().getCanonicalType(LHS->getType());154 155 // Promote LHS.156 V = svalBuilder.evalCast(V, CLHSTy, LTy);157 158 // Compute the result of the operation.159 SVal Result = svalBuilder.evalCast(evalBinOp(state, Op, V, RightV, CTy),160 B->getType(), CTy);161 162 // EXPERIMENTAL: "Conjured" symbols.163 // FIXME: Handle structs.164 165 SVal LHSVal;166 167 if (Result.isUnknown()) {168 // The symbolic value is actually for the type of the left-hand side169 // expression, not the computation type, as this is the value the170 // LValue on the LHS will bind to.171 LHSVal = svalBuilder.conjureSymbolVal(/*symbolTag=*/nullptr,172 getCFGElementRef(), LCtx, LTy,173 currBldrCtx->blockCount());174 // However, we need to convert the symbol to the computation type.175 Result = svalBuilder.evalCast(LHSVal, CTy, LTy);176 } else {177 // The left-hand side may bind to a different value then the178 // computation type.179 LHSVal = svalBuilder.evalCast(Result, LTy, CTy);180 }181 182 // In C++, assignment and compound assignment operators return an183 // lvalue.184 if (B->isGLValue())185 state = state->BindExpr(B, LCtx, location);186 else187 state = state->BindExpr(B, LCtx, Result);188 189 evalStore(Tmp2, B, LHS, N, state, location, LHSVal);190 }191 }192 193 // FIXME: postvisits eventually go in ::Visit()194 getCheckerManager().runCheckersForPostStmt(Dst, Tmp2, B, *this);195}196 197void ExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,198 ExplodedNodeSet &Dst) {199 200 CanQualType T = getContext().getCanonicalType(BE->getType());201 202 const BlockDecl *BD = BE->getBlockDecl();203 // Get the value of the block itself.204 SVal V = svalBuilder.getBlockPointer(BD, T,205 Pred->getLocationContext(),206 currBldrCtx->blockCount());207 208 ProgramStateRef State = Pred->getState();209 210 // If we created a new MemRegion for the block, we should explicitly bind211 // the captured variables.212 if (const BlockDataRegion *BDR =213 dyn_cast_or_null<BlockDataRegion>(V.getAsRegion())) {214 215 auto ReferencedVars = BDR->referenced_vars();216 auto CI = BD->capture_begin();217 auto CE = BD->capture_end();218 for (auto Var : ReferencedVars) {219 const VarRegion *capturedR = Var.getCapturedRegion();220 const TypedValueRegion *originalR = Var.getOriginalRegion();221 222 // If the capture had a copy expression, use the result of evaluating223 // that expression, otherwise use the original value.224 // We rely on the invariant that the block declaration's capture variables225 // are a prefix of the BlockDataRegion's referenced vars (which may include226 // referenced globals, etc.) to enable fast lookup of the capture for a227 // given referenced var.228 const Expr *copyExpr = nullptr;229 if (CI != CE) {230 assert(CI->getVariable() == capturedR->getDecl());231 copyExpr = CI->getCopyExpr();232 CI++;233 }234 235 if (capturedR != originalR) {236 SVal originalV;237 const LocationContext *LCtx = Pred->getLocationContext();238 if (copyExpr) {239 originalV = State->getSVal(copyExpr, LCtx);240 } else {241 originalV = State->getSVal(loc::MemRegionVal(originalR));242 }243 State = State->bindLoc(loc::MemRegionVal(capturedR), originalV, LCtx);244 }245 }246 }247 248 ExplodedNodeSet Tmp;249 StmtNodeBuilder Bldr(Pred, Tmp, *currBldrCtx);250 Bldr.generateNode(BE, Pred,251 State->BindExpr(BE, Pred->getLocationContext(), V),252 nullptr, ProgramPoint::PostLValueKind);253 254 // FIXME: Move all post/pre visits to ::Visit().255 getCheckerManager().runCheckersForPostStmt(Dst, Tmp, BE, *this);256}257 258ProgramStateRef ExprEngine::handleLValueBitCast(259 ProgramStateRef state, const Expr* Ex, const LocationContext* LCtx,260 QualType T, QualType ExTy, const CastExpr* CastE, StmtNodeBuilder& Bldr,261 ExplodedNode* Pred) {262 if (T->isLValueReferenceType()) {263 assert(!CastE->getType()->isLValueReferenceType());264 ExTy = getContext().getLValueReferenceType(ExTy);265 } else if (T->isRValueReferenceType()) {266 assert(!CastE->getType()->isRValueReferenceType());267 ExTy = getContext().getRValueReferenceType(ExTy);268 }269 // Delegate to SValBuilder to process.270 SVal OrigV = state->getSVal(Ex, LCtx);271 SVal SimplifiedOrigV = svalBuilder.simplifySVal(state, OrigV);272 SVal V = svalBuilder.evalCast(SimplifiedOrigV, T, ExTy);273 // Negate the result if we're treating the boolean as a signed i1274 if (CastE->getCastKind() == CK_BooleanToSignedIntegral && V.isValid())275 V = svalBuilder.evalMinus(V.castAs<NonLoc>());276 277 state = state->BindExpr(CastE, LCtx, V);278 if (V.isUnknown() && !OrigV.isUnknown()) {279 state = escapeValues(state, OrigV, PSK_EscapeOther);280 }281 Bldr.generateNode(CastE, Pred, state);282 283 return state;284}285 286void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex,287 ExplodedNode *Pred, ExplodedNodeSet &Dst) {288 289 ExplodedNodeSet DstPreStmt;290 getCheckerManager().runCheckersForPreStmt(DstPreStmt, Pred, CastE, *this);291 292 if (CastE->getCastKind() == CK_LValueToRValue) {293 for (ExplodedNode *Node : DstPreStmt) {294 ProgramStateRef State = Node->getState();295 const LocationContext *LCtx = Node->getLocationContext();296 evalLoad(Dst, CastE, CastE, Node, State, State->getSVal(Ex, LCtx));297 }298 return;299 }300 if (CastE->getCastKind() == CK_LValueToRValueBitCast) {301 // Handle `__builtin_bit_cast`:302 ExplodedNodeSet DstEvalLoc;303 304 // Simulate the lvalue-to-rvalue conversion on `Ex`:305 for (ExplodedNode *Node : DstPreStmt) {306 ProgramStateRef State = Node->getState();307 const LocationContext *LCtx = Node->getLocationContext();308 evalLocation(DstEvalLoc, CastE, Ex, Node, State, State->getSVal(Ex, LCtx),309 true);310 }311 // Simulate the operation that actually casts the original value to a new312 // value of the destination type :313 StmtNodeBuilder Bldr(DstEvalLoc, Dst, *currBldrCtx);314 315 for (ExplodedNode *Node : DstEvalLoc) {316 ProgramStateRef State = Node->getState();317 const LocationContext *LCtx = Node->getLocationContext();318 // Although `Ex` is an lvalue, it could have `Loc::ConcreteInt` kind319 // (e.g., `(int *)123456`). In such cases, there is no MemRegion320 // available and we can't get the value to be casted.321 SVal CastedV = UnknownVal();322 323 if (const MemRegion *MR = State->getSVal(Ex, LCtx).getAsRegion()) {324 SVal OrigV = State->getSVal(MR);325 CastedV = svalBuilder.evalCast(svalBuilder.simplifySVal(State, OrigV),326 CastE->getType(), Ex->getType());327 }328 State = State->BindExpr(CastE, LCtx, CastedV);329 Bldr.generateNode(CastE, Node, State);330 }331 return;332 }333 334 // All other casts.335 QualType T = CastE->getType();336 QualType ExTy = Ex->getType();337 338 if (const ExplicitCastExpr *ExCast=dyn_cast_or_null<ExplicitCastExpr>(CastE))339 T = ExCast->getTypeAsWritten();340 341 StmtNodeBuilder Bldr(DstPreStmt, Dst, *currBldrCtx);342 for (ExplodedNode *Pred : DstPreStmt) {343 ProgramStateRef state = Pred->getState();344 const LocationContext *LCtx = Pred->getLocationContext();345 346 switch (CastE->getCastKind()) {347 case CK_LValueToRValue:348 case CK_LValueToRValueBitCast:349 llvm_unreachable("LValueToRValue casts handled earlier.");350 case CK_ToVoid:351 continue;352 // The analyzer doesn't do anything special with these casts,353 // since it understands retain/release semantics already.354 case CK_ARCProduceObject:355 case CK_ARCConsumeObject:356 case CK_ARCReclaimReturnedObject:357 case CK_ARCExtendBlockObject: // Fall-through.358 case CK_CopyAndAutoreleaseBlockObject:359 // The analyser can ignore atomic casts for now, although some future360 // checkers may want to make certain that you're not modifying the same361 // value through atomic and nonatomic pointers.362 case CK_AtomicToNonAtomic:363 case CK_NonAtomicToAtomic:364 // True no-ops.365 case CK_NoOp:366 case CK_ConstructorConversion:367 case CK_UserDefinedConversion:368 case CK_FunctionToPointerDecay:369 case CK_BuiltinFnToFnPtr:370 case CK_HLSLArrayRValue: {371 // Copy the SVal of Ex to CastE.372 ProgramStateRef state = Pred->getState();373 const LocationContext *LCtx = Pred->getLocationContext();374 SVal V = state->getSVal(Ex, LCtx);375 state = state->BindExpr(CastE, LCtx, V);376 Bldr.generateNode(CastE, Pred, state);377 continue;378 }379 case CK_MemberPointerToBoolean:380 case CK_PointerToBoolean: {381 SVal V = state->getSVal(Ex, LCtx);382 auto PTMSV = V.getAs<nonloc::PointerToMember>();383 if (PTMSV)384 V = svalBuilder.makeTruthVal(!PTMSV->isNullMemberPointer(), ExTy);385 if (V.isUndef() || PTMSV) {386 state = state->BindExpr(CastE, LCtx, V);387 Bldr.generateNode(CastE, Pred, state);388 continue;389 }390 // Explicitly proceed with default handler for this case cascade.391 state =392 handleLValueBitCast(state, Ex, LCtx, T, ExTy, CastE, Bldr, Pred);393 continue;394 }395 case CK_Dependent:396 case CK_ArrayToPointerDecay:397 case CK_BitCast:398 case CK_AddressSpaceConversion:399 case CK_BooleanToSignedIntegral:400 case CK_IntegralToPointer:401 case CK_PointerToIntegral: {402 SVal V = state->getSVal(Ex, LCtx);403 if (isa<nonloc::PointerToMember>(V)) {404 state = state->BindExpr(CastE, LCtx, UnknownVal());405 Bldr.generateNode(CastE, Pred, state);406 continue;407 }408 // Explicitly proceed with default handler for this case cascade.409 state =410 handleLValueBitCast(state, Ex, LCtx, T, ExTy, CastE, Bldr, Pred);411 continue;412 }413 case CK_IntegralToBoolean:414 case CK_IntegralToFloating:415 case CK_FloatingToIntegral:416 case CK_FloatingToBoolean:417 case CK_FloatingCast:418 case CK_FloatingRealToComplex:419 case CK_FloatingComplexToReal:420 case CK_FloatingComplexToBoolean:421 case CK_FloatingComplexCast:422 case CK_FloatingComplexToIntegralComplex:423 case CK_IntegralRealToComplex:424 case CK_IntegralComplexToReal:425 case CK_IntegralComplexToBoolean:426 case CK_IntegralComplexCast:427 case CK_IntegralComplexToFloatingComplex:428 case CK_CPointerToObjCPointerCast:429 case CK_BlockPointerToObjCPointerCast:430 case CK_AnyPointerToBlockPointerCast:431 case CK_ObjCObjectLValueCast:432 case CK_ZeroToOCLOpaqueType:433 case CK_IntToOCLSampler:434 case CK_LValueBitCast:435 case CK_FloatingToFixedPoint:436 case CK_FixedPointToFloating:437 case CK_FixedPointCast:438 case CK_FixedPointToBoolean:439 case CK_FixedPointToIntegral:440 case CK_IntegralToFixedPoint: {441 state =442 handleLValueBitCast(state, Ex, LCtx, T, ExTy, CastE, Bldr, Pred);443 continue;444 }445 case CK_IntegralCast: {446 // Delegate to SValBuilder to process.447 SVal V = state->getSVal(Ex, LCtx);448 if (AMgr.options.ShouldSupportSymbolicIntegerCasts)449 V = svalBuilder.evalCast(V, T, ExTy);450 else451 V = svalBuilder.evalIntegralCast(state, V, T, ExTy);452 state = state->BindExpr(CastE, LCtx, V);453 Bldr.generateNode(CastE, Pred, state);454 continue;455 }456 case CK_DerivedToBase:457 case CK_UncheckedDerivedToBase: {458 // For DerivedToBase cast, delegate to the store manager.459 SVal val = state->getSVal(Ex, LCtx);460 val = getStoreManager().evalDerivedToBase(val, CastE);461 state = state->BindExpr(CastE, LCtx, val);462 Bldr.generateNode(CastE, Pred, state);463 continue;464 }465 // Handle C++ dyn_cast.466 case CK_Dynamic: {467 SVal val = state->getSVal(Ex, LCtx);468 469 // Compute the type of the result.470 QualType resultType = CastE->getType();471 if (CastE->isGLValue())472 resultType = getContext().getPointerType(resultType);473 474 bool Failed = true;475 476 // Check if the value being cast does not evaluates to 0.477 if (!val.isZeroConstant())478 if (std::optional<SVal> V =479 StateMgr.getStoreManager().evalBaseToDerived(val, T)) {480 val = *V;481 Failed = false;482 }483 484 if (Failed) {485 if (T->isReferenceType()) {486 // A bad_cast exception is thrown if input value is a reference.487 // Currently, we model this, by generating a sink.488 Bldr.generateSink(CastE, Pred, state);489 continue;490 } else {491 // If the cast fails on a pointer, bind to 0.492 state = state->BindExpr(CastE, LCtx,493 svalBuilder.makeNullWithType(resultType));494 }495 } else {496 // If we don't know if the cast succeeded, conjure a new symbol.497 if (val.isUnknown()) {498 DefinedOrUnknownSVal NewSym = svalBuilder.conjureSymbolVal(499 /*symbolTag=*/nullptr, getCFGElementRef(), LCtx, resultType,500 currBldrCtx->blockCount());501 state = state->BindExpr(CastE, LCtx, NewSym);502 } else503 // Else, bind to the derived region value.504 state = state->BindExpr(CastE, LCtx, val);505 }506 Bldr.generateNode(CastE, Pred, state);507 continue;508 }509 case CK_BaseToDerived: {510 SVal val = state->getSVal(Ex, LCtx);511 QualType resultType = CastE->getType();512 if (CastE->isGLValue())513 resultType = getContext().getPointerType(resultType);514 515 if (!val.isConstant()) {516 std::optional<SVal> V = getStoreManager().evalBaseToDerived(val, T);517 val = V ? *V : UnknownVal();518 }519 520 // Failed to cast or the result is unknown, fall back to conservative.521 if (val.isUnknown()) {522 val = svalBuilder.conjureSymbolVal(523 /*symbolTag=*/nullptr, getCFGElementRef(), LCtx, resultType,524 currBldrCtx->blockCount());525 }526 state = state->BindExpr(CastE, LCtx, val);527 Bldr.generateNode(CastE, Pred, state);528 continue;529 }530 case CK_NullToPointer: {531 SVal V = svalBuilder.makeNullWithType(CastE->getType());532 state = state->BindExpr(CastE, LCtx, V);533 Bldr.generateNode(CastE, Pred, state);534 continue;535 }536 case CK_NullToMemberPointer: {537 SVal V = svalBuilder.getMemberPointer(nullptr);538 state = state->BindExpr(CastE, LCtx, V);539 Bldr.generateNode(CastE, Pred, state);540 continue;541 }542 case CK_DerivedToBaseMemberPointer:543 case CK_BaseToDerivedMemberPointer:544 case CK_ReinterpretMemberPointer: {545 SVal V = state->getSVal(Ex, LCtx);546 if (auto PTMSV = V.getAs<nonloc::PointerToMember>()) {547 SVal CastedPTMSV =548 svalBuilder.makePointerToMember(getBasicVals().accumCXXBase(549 CastE->path(), *PTMSV, CastE->getCastKind()));550 state = state->BindExpr(CastE, LCtx, CastedPTMSV);551 Bldr.generateNode(CastE, Pred, state);552 continue;553 }554 // Explicitly proceed with default handler for this case cascade.555 }556 [[fallthrough]];557 // Various C++ casts that are not handled yet.558 case CK_ToUnion:559 case CK_MatrixCast:560 case CK_VectorSplat:561 case CK_HLSLElementwiseCast:562 case CK_HLSLAggregateSplatCast:563 case CK_HLSLVectorTruncation: {564 QualType resultType = CastE->getType();565 if (CastE->isGLValue())566 resultType = getContext().getPointerType(resultType);567 SVal result = svalBuilder.conjureSymbolVal(568 /*symbolTag=*/nullptr, getCFGElementRef(), LCtx, resultType,569 currBldrCtx->blockCount());570 state = state->BindExpr(CastE, LCtx, result);571 Bldr.generateNode(CastE, Pred, state);572 continue;573 }574 }575 }576}577 578void ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL,579 ExplodedNode *Pred,580 ExplodedNodeSet &Dst) {581 StmtNodeBuilder B(Pred, Dst, *currBldrCtx);582 583 ProgramStateRef State = Pred->getState();584 const LocationContext *LCtx = Pred->getLocationContext();585 586 const Expr *Init = CL->getInitializer();587 SVal V = State->getSVal(CL->getInitializer(), LCtx);588 589 if (isa<CXXConstructExpr, CXXStdInitializerListExpr>(Init)) {590 // No work needed. Just pass the value up to this expression.591 } else {592 assert(isa<InitListExpr>(Init));593 Loc CLLoc = State->getLValue(CL, LCtx);594 State = State->bindLoc(CLLoc, V, LCtx);595 596 if (CL->isGLValue())597 V = CLLoc;598 }599 600 B.generateNode(CL, Pred, State->BindExpr(CL, LCtx, V));601}602 603void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred,604 ExplodedNodeSet &Dst) {605 if (isa<TypedefNameDecl>(*DS->decl_begin())) {606 // C99 6.7.7 "Any array size expressions associated with variable length607 // array declarators are evaluated each time the declaration of the typedef608 // name is reached in the order of execution."609 // The checkers should know about typedef to be able to handle VLA size610 // expressions.611 ExplodedNodeSet DstPre;612 getCheckerManager().runCheckersForPreStmt(DstPre, Pred, DS, *this);613 getCheckerManager().runCheckersForPostStmt(Dst, DstPre, DS, *this);614 return;615 }616 617 // Assumption: The CFG has one DeclStmt per Decl.618 const VarDecl *VD = dyn_cast_or_null<VarDecl>(*DS->decl_begin());619 620 if (!VD) {621 //TODO:AZ: remove explicit insertion after refactoring is done.622 Dst.insert(Pred);623 return;624 }625 626 // FIXME: all pre/post visits should eventually be handled by ::Visit().627 ExplodedNodeSet dstPreVisit;628 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, DS, *this);629 630 ExplodedNodeSet dstEvaluated;631 StmtNodeBuilder B(dstPreVisit, dstEvaluated, *currBldrCtx);632 for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end();633 I!=E; ++I) {634 ExplodedNode *N = *I;635 ProgramStateRef state = N->getState();636 const LocationContext *LC = N->getLocationContext();637 638 // Decls without InitExpr are not initialized explicitly.639 if (const Expr *InitEx = VD->getInit()) {640 641 // Note in the state that the initialization has occurred.642 ExplodedNode *UpdatedN = N;643 SVal InitVal = state->getSVal(InitEx, LC);644 645 assert(DS->isSingleDecl());646 if (getObjectUnderConstruction(state, DS, LC)) {647 state = finishObjectConstruction(state, DS, LC);648 // We constructed the object directly in the variable.649 // No need to bind anything.650 B.generateNode(DS, UpdatedN, state);651 } else {652 // Recover some path-sensitivity if a scalar value evaluated to653 // UnknownVal.654 if (InitVal.isUnknown()) {655 QualType Ty = InitEx->getType();656 if (InitEx->isGLValue()) {657 Ty = getContext().getPointerType(Ty);658 }659 660 InitVal = svalBuilder.conjureSymbolVal(661 /*symbolTag=*/nullptr, getCFGElementRef(), LC, Ty,662 currBldrCtx->blockCount());663 }664 665 666 B.takeNodes(UpdatedN);667 ExplodedNodeSet Dst2;668 evalBind(Dst2, DS, UpdatedN, state->getLValue(VD, LC), InitVal, true);669 B.addNodes(Dst2);670 }671 }672 else {673 B.generateNode(DS, N, state);674 }675 }676 677 getCheckerManager().runCheckersForPostStmt(Dst, B.getResults(), DS, *this);678}679 680void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred,681 ExplodedNodeSet &Dst) {682 // This method acts upon CFG elements for logical operators && and ||683 // and attaches the value (true or false) to them as expressions.684 // It doesn't produce any state splits.685 // If we made it that far, we're past the point when we modeled the short686 // circuit. It means that we should have precise knowledge about whether687 // we've short-circuited. If we did, we already know the value we need to688 // bind. If we didn't, the value of the RHS (casted to the boolean type)689 // is the answer.690 // Currently this method tries to figure out whether we've short-circuited691 // by looking at the ExplodedGraph. This method is imperfect because there692 // could inevitably have been merges that would have resulted in multiple693 // potential path traversal histories. We bail out when we fail.694 // Due to this ambiguity, a more reliable solution would have been to695 // track the short circuit operation history path-sensitively until696 // we evaluate the respective logical operator.697 assert(B->getOpcode() == BO_LAnd ||698 B->getOpcode() == BO_LOr);699 700 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);701 ProgramStateRef state = Pred->getState();702 703 if (B->getType()->isVectorType()) {704 // FIXME: We do not model vector arithmetic yet. When adding support for705 // that, note that the CFG-based reasoning below does not apply, because706 // logical operators on vectors are not short-circuit. Currently they are707 // modeled as short-circuit in Clang CFG but this is incorrect.708 // Do not set the value for the expression. It'd be UnknownVal by default.709 Bldr.generateNode(B, Pred, state);710 return;711 }712 713 ExplodedNode *N = Pred;714 while (!N->getLocation().getAs<BlockEdge>()) {715 ProgramPoint P = N->getLocation();716 assert(P.getAs<PreStmt>() || P.getAs<PreStmtPurgeDeadSymbols>() ||717 P.getAs<BlockEntrance>());718 (void) P;719 if (N->pred_size() != 1) {720 // We failed to track back where we came from.721 Bldr.generateNode(B, Pred, state);722 return;723 }724 N = *N->pred_begin();725 }726 727 if (N->pred_size() != 1) {728 // We failed to track back where we came from.729 Bldr.generateNode(B, Pred, state);730 return;731 }732 733 BlockEdge BE = N->getLocation().castAs<BlockEdge>();734 SVal X;735 736 // Determine the value of the expression by introspecting how we737 // got this location in the CFG. This requires looking at the previous738 // block we were in and what kind of control-flow transfer was involved.739 const CFGBlock *SrcBlock = BE.getSrc();740 // The only terminator (if there is one) that makes sense is a logical op.741 CFGTerminator T = SrcBlock->getTerminator();742 if (const BinaryOperator *Term = cast_or_null<BinaryOperator>(T.getStmt())) {743 (void) Term;744 assert(Term->isLogicalOp());745 assert(SrcBlock->succ_size() == 2);746 // Did we take the true or false branch?747 unsigned constant = (*SrcBlock->succ_begin() == BE.getDst()) ? 1 : 0;748 X = svalBuilder.makeIntVal(constant, B->getType());749 }750 else {751 // If there is no terminator, by construction the last statement752 // in SrcBlock is the value of the enclosing expression.753 // However, we still need to constrain that value to be 0 or 1.754 assert(!SrcBlock->empty());755 CFGStmt Elem = SrcBlock->rbegin()->castAs<CFGStmt>();756 const Expr *RHS = cast<Expr>(Elem.getStmt());757 SVal RHSVal = N->getState()->getSVal(RHS, Pred->getLocationContext());758 759 if (RHSVal.isUndef()) {760 X = RHSVal;761 } else {762 // We evaluate "RHSVal != 0" expression which result in 0 if the value is763 // known to be false, 1 if the value is known to be true and a new symbol764 // when the assumption is unknown.765 nonloc::ConcreteInt Zero(getBasicVals().getValue(0, B->getType()));766 X = evalBinOp(N->getState(), BO_NE,767 svalBuilder.evalCast(RHSVal, B->getType(), RHS->getType()),768 Zero, B->getType());769 }770 }771 Bldr.generateNode(B, Pred, state->BindExpr(B, Pred->getLocationContext(), X));772}773 774void ExprEngine::VisitGuardedExpr(const Expr *Ex,775 const Expr *L,776 const Expr *R,777 ExplodedNode *Pred,778 ExplodedNodeSet &Dst) {779 assert(L && R);780 781 StmtNodeBuilder B(Pred, Dst, *currBldrCtx);782 ProgramStateRef state = Pred->getState();783 const LocationContext *LCtx = Pred->getLocationContext();784 const CFGBlock *SrcBlock = nullptr;785 786 // Find the predecessor block.787 ProgramStateRef SrcState = state;788 for (const ExplodedNode *N = Pred ; N ; N = *N->pred_begin()) {789 auto Edge = N->getLocationAs<BlockEdge>();790 if (!Edge.has_value()) {791 // If the state N has multiple predecessors P, it means that successors792 // of P are all equivalent.793 // In turn, that means that all nodes at P are equivalent in terms794 // of observable behavior at N, and we can follow any of them.795 // FIXME: a more robust solution which does not walk up the tree.796 continue;797 }798 SrcBlock = Edge->getSrc();799 SrcState = N->getState();800 break;801 }802 803 assert(SrcBlock && "missing function entry");804 805 // Find the last expression in the predecessor block. That is the806 // expression that is used for the value of the ternary expression.807 bool hasValue = false;808 SVal V;809 810 for (CFGElement CE : llvm::reverse(*SrcBlock)) {811 if (std::optional<CFGStmt> CS = CE.getAs<CFGStmt>()) {812 const Expr *ValEx = cast<Expr>(CS->getStmt());813 ValEx = ValEx->IgnoreParens();814 815 // For GNU extension '?:' operator, the left hand side will be an816 // OpaqueValueExpr, so get the underlying expression.817 if (const OpaqueValueExpr *OpaqueEx = dyn_cast<OpaqueValueExpr>(L))818 L = OpaqueEx->getSourceExpr();819 820 // If the last expression in the predecessor block matches true or false821 // subexpression, get its the value.822 if (ValEx == L->IgnoreParens() || ValEx == R->IgnoreParens()) {823 hasValue = true;824 V = SrcState->getSVal(ValEx, LCtx);825 }826 break;827 }828 }829 830 if (!hasValue)831 V = svalBuilder.conjureSymbolVal(nullptr, getCFGElementRef(), LCtx,832 currBldrCtx->blockCount());833 834 // Generate a new node with the binding from the appropriate path.835 B.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V, true));836}837 838void ExprEngine::839VisitOffsetOfExpr(const OffsetOfExpr *OOE,840 ExplodedNode *Pred, ExplodedNodeSet &Dst) {841 StmtNodeBuilder B(Pred, Dst, *currBldrCtx);842 Expr::EvalResult Result;843 if (OOE->EvaluateAsInt(Result, getContext())) {844 APSInt IV = Result.Val.getInt();845 assert(IV.getBitWidth() == getContext().getTypeSize(OOE->getType()));846 assert(OOE->getType()->castAs<BuiltinType>()->isInteger());847 assert(IV.isSigned() == OOE->getType()->isSignedIntegerType());848 SVal X = svalBuilder.makeIntVal(IV);849 B.generateNode(OOE, Pred,850 Pred->getState()->BindExpr(OOE, Pred->getLocationContext(),851 X));852 }853 // FIXME: Handle the case where __builtin_offsetof is not a constant.854}855 856 857void ExprEngine::858VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex,859 ExplodedNode *Pred,860 ExplodedNodeSet &Dst) {861 // FIXME: Prechecks eventually go in ::Visit().862 ExplodedNodeSet CheckedSet;863 getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, Ex, *this);864 865 ExplodedNodeSet EvalSet;866 StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx);867 868 QualType T = Ex->getTypeOfArgument();869 870 for (ExplodedNode *N : CheckedSet) {871 if (Ex->getKind() == UETT_SizeOf || Ex->getKind() == UETT_DataSizeOf ||872 Ex->getKind() == UETT_CountOf) {873 if (!T->isIncompleteType() && !T->isConstantSizeType()) {874 assert(T->isVariableArrayType() && "Unknown non-constant-sized type.");875 876 // FIXME: Add support for VLA type arguments and VLA expressions.877 // When that happens, we should probably refactor VLASizeChecker's code.878 continue;879 } else if (T->getAs<ObjCObjectType>()) {880 // Some code tries to take the sizeof an ObjCObjectType, relying that881 // the compiler has laid out its representation. Just report Unknown882 // for these.883 continue;884 }885 }886 887 APSInt Value = Ex->EvaluateKnownConstInt(getContext());888 CharUnits amt = CharUnits::fromQuantity(Value.getZExtValue());889 890 ProgramStateRef state = N->getState();891 state = state->BindExpr(892 Ex, N->getLocationContext(),893 svalBuilder.makeIntVal(amt.getQuantity(), Ex->getType()));894 Bldr.generateNode(Ex, N, state);895 }896 897 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, Ex, *this);898}899 900void ExprEngine::handleUOExtension(ExplodedNode *N, const UnaryOperator *U,901 StmtNodeBuilder &Bldr) {902 // FIXME: We can probably just have some magic in Environment::getSVal()903 // that propagates values, instead of creating a new node here.904 //905 // Unary "+" is a no-op, similar to a parentheses. We still have places906 // where it may be a block-level expression, so we need to907 // generate an extra node that just propagates the value of the908 // subexpression.909 const Expr *Ex = U->getSubExpr()->IgnoreParens();910 ProgramStateRef state = N->getState();911 const LocationContext *LCtx = N->getLocationContext();912 Bldr.generateNode(U, N, state->BindExpr(U, LCtx, state->getSVal(Ex, LCtx)));913}914 915void ExprEngine::VisitUnaryOperator(const UnaryOperator* U, ExplodedNode *Pred,916 ExplodedNodeSet &Dst) {917 // FIXME: Prechecks eventually go in ::Visit().918 ExplodedNodeSet CheckedSet;919 getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, U, *this);920 921 ExplodedNodeSet EvalSet;922 StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx);923 924 for (ExplodedNode *N : CheckedSet) {925 switch (U->getOpcode()) {926 default: {927 Bldr.takeNodes(N);928 ExplodedNodeSet Tmp;929 VisitIncrementDecrementOperator(U, N, Tmp);930 Bldr.addNodes(Tmp);931 break;932 }933 case UO_Real: {934 const Expr *Ex = U->getSubExpr()->IgnoreParens();935 936 // FIXME: We don't have complex SValues yet.937 if (Ex->getType()->isAnyComplexType()) {938 // Just report "Unknown."939 break;940 }941 942 // For all other types, UO_Real is an identity operation.943 assert (U->getType() == Ex->getType());944 ProgramStateRef state = N->getState();945 const LocationContext *LCtx = N->getLocationContext();946 Bldr.generateNode(U, N,947 state->BindExpr(U, LCtx, state->getSVal(Ex, LCtx)));948 break;949 }950 951 case UO_Imag: {952 const Expr *Ex = U->getSubExpr()->IgnoreParens();953 // FIXME: We don't have complex SValues yet.954 if (Ex->getType()->isAnyComplexType()) {955 // Just report "Unknown."956 break;957 }958 // For all other types, UO_Imag returns 0.959 ProgramStateRef state = N->getState();960 const LocationContext *LCtx = N->getLocationContext();961 SVal X = svalBuilder.makeZeroVal(Ex->getType());962 Bldr.generateNode(U, N, state->BindExpr(U, LCtx, X));963 break;964 }965 966 case UO_AddrOf: {967 // Process pointer-to-member address operation.968 const Expr *Ex = U->getSubExpr()->IgnoreParens();969 if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Ex)) {970 const ValueDecl *VD = DRE->getDecl();971 972 if (isa<CXXMethodDecl, FieldDecl, IndirectFieldDecl>(VD)) {973 ProgramStateRef State = N->getState();974 const LocationContext *LCtx = N->getLocationContext();975 SVal SV = svalBuilder.getMemberPointer(cast<NamedDecl>(VD));976 Bldr.generateNode(U, N, State->BindExpr(U, LCtx, SV));977 break;978 }979 }980 // Explicitly proceed with default handler for this case cascade.981 handleUOExtension(N, U, Bldr);982 break;983 }984 case UO_Plus:985 assert(!U->isGLValue());986 [[fallthrough]];987 case UO_Deref:988 case UO_Extension: {989 handleUOExtension(N, U, Bldr);990 break;991 }992 993 case UO_LNot:994 case UO_Minus:995 case UO_Not: {996 assert (!U->isGLValue());997 const Expr *Ex = U->getSubExpr()->IgnoreParens();998 ProgramStateRef state = N->getState();999 const LocationContext *LCtx = N->getLocationContext();1000 1001 // Get the value of the subexpression.1002 SVal V = state->getSVal(Ex, LCtx);1003 1004 if (V.isUnknownOrUndef()) {1005 Bldr.generateNode(U, N, state->BindExpr(U, LCtx, V));1006 break;1007 }1008 1009 switch (U->getOpcode()) {1010 default:1011 llvm_unreachable("Invalid Opcode.");1012 case UO_Not:1013 // FIXME: Do we need to handle promotions?1014 state = state->BindExpr(1015 U, LCtx, svalBuilder.evalComplement(V.castAs<NonLoc>()));1016 break;1017 case UO_Minus:1018 // FIXME: Do we need to handle promotions?1019 state = state->BindExpr(U, LCtx,1020 svalBuilder.evalMinus(V.castAs<NonLoc>()));1021 break;1022 case UO_LNot:1023 // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."1024 //1025 // Note: technically we do "E == 0", but this is the same in the1026 // transfer functions as "0 == E".1027 SVal Result;1028 if (std::optional<Loc> LV = V.getAs<Loc>()) {1029 Loc X = svalBuilder.makeNullWithType(Ex->getType());1030 Result = evalBinOp(state, BO_EQ, *LV, X, U->getType());1031 } else if (Ex->getType()->isFloatingType()) {1032 // FIXME: handle floating point types.1033 Result = UnknownVal();1034 } else {1035 nonloc::ConcreteInt X(getBasicVals().getValue(0, Ex->getType()));1036 Result = evalBinOp(state, BO_EQ, V.castAs<NonLoc>(), X, U->getType());1037 }1038 1039 state = state->BindExpr(U, LCtx, Result);1040 break;1041 }1042 Bldr.generateNode(U, N, state);1043 break;1044 }1045 }1046 }1047 1048 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, U, *this);1049}1050 1051void ExprEngine::VisitIncrementDecrementOperator(const UnaryOperator* U,1052 ExplodedNode *Pred,1053 ExplodedNodeSet &Dst) {1054 // Handle ++ and -- (both pre- and post-increment).1055 assert (U->isIncrementDecrementOp());1056 const Expr *Ex = U->getSubExpr()->IgnoreParens();1057 1058 const LocationContext *LCtx = Pred->getLocationContext();1059 ProgramStateRef state = Pred->getState();1060 SVal loc = state->getSVal(Ex, LCtx);1061 1062 // Perform a load.1063 ExplodedNodeSet Tmp;1064 evalLoad(Tmp, U, Ex, Pred, state, loc);1065 1066 ExplodedNodeSet Dst2;1067 StmtNodeBuilder Bldr(Tmp, Dst2, *currBldrCtx);1068 for (ExplodedNode *N : Tmp) {1069 state = N->getState();1070 assert(LCtx == N->getLocationContext());1071 SVal V2_untested = state->getSVal(Ex, LCtx);1072 1073 // Propagate unknown and undefined values.1074 if (V2_untested.isUnknownOrUndef()) {1075 state = state->BindExpr(U, LCtx, V2_untested);1076 1077 // Perform the store, so that the uninitialized value detection happens.1078 Bldr.takeNodes(N);1079 ExplodedNodeSet Dst3;1080 evalStore(Dst3, U, Ex, N, state, loc, V2_untested);1081 Bldr.addNodes(Dst3);1082 1083 continue;1084 }1085 DefinedSVal V2 = V2_untested.castAs<DefinedSVal>();1086 1087 // Handle all other values.1088 BinaryOperator::Opcode Op = U->isIncrementOp() ? BO_Add : BO_Sub;1089 1090 // If the UnaryOperator has non-location type, use its type to create the1091 // constant value. If the UnaryOperator has location type, create the1092 // constant with int type and pointer width.1093 SVal RHS;1094 SVal Result;1095 1096 if (U->getType()->isAnyPointerType())1097 RHS = svalBuilder.makeArrayIndex(1);1098 else if (U->getType()->isIntegralOrEnumerationType())1099 RHS = svalBuilder.makeIntVal(1, U->getType());1100 else1101 RHS = UnknownVal();1102 1103 // The use of an operand of type bool with the ++ operators is deprecated1104 // but valid until C++17. And if the operand of the ++ operator is of type1105 // bool, it is set to true until C++17. Note that for '_Bool', it is also1106 // set to true when it encounters ++ operator.1107 if (U->getType()->isBooleanType() && U->isIncrementOp())1108 Result = svalBuilder.makeTruthVal(true, U->getType());1109 else1110 Result = evalBinOp(state, Op, V2, RHS, U->getType());1111 1112 // Conjure a new symbol if necessary to recover precision.1113 if (Result.isUnknown()){1114 DefinedOrUnknownSVal SymVal = svalBuilder.conjureSymbolVal(1115 /*symbolTag=*/nullptr, getCFGElementRef(), LCtx,1116 currBldrCtx->blockCount());1117 Result = SymVal;1118 1119 // If the value is a location, ++/-- should always preserve1120 // non-nullness. Check if the original value was non-null, and if so1121 // propagate that constraint.1122 if (Loc::isLocType(U->getType())) {1123 DefinedOrUnknownSVal Constraint =1124 svalBuilder.evalEQ(state, V2,svalBuilder.makeZeroVal(U->getType()));1125 1126 if (!state->assume(Constraint, true)) {1127 // It isn't feasible for the original value to be null.1128 // Propagate this constraint.1129 Constraint = svalBuilder.evalEQ(state, SymVal,1130 svalBuilder.makeZeroVal(U->getType()));1131 1132 state = state->assume(Constraint, false);1133 assert(state);1134 }1135 }1136 }1137 1138 // Since the lvalue-to-rvalue conversion is explicit in the AST,1139 // we bind an l-value if the operator is prefix and an lvalue (in C++).1140 if (U->isGLValue())1141 state = state->BindExpr(U, LCtx, loc);1142 else1143 state = state->BindExpr(U, LCtx, U->isPostfix() ? V2 : Result);1144 1145 // Perform the store.1146 Bldr.takeNodes(N);1147 ExplodedNodeSet Dst3;1148 evalStore(Dst3, U, Ex, N, state, loc, Result);1149 Bldr.addNodes(Dst3);1150 }1151 Dst.insert(Dst2);1152}1153