63 #include "llvm/ADT/APSInt.h"
64 #include "llvm/ADT/DenseMap.h"
65 #include "llvm/ADT/ImmutableMap.h"
66 #include "llvm/ADT/ImmutableSet.h"
67 #include "llvm/ADT/Optional.h"
68 #include "llvm/ADT/SmallVector.h"
69 #include "llvm/ADT/Statistic.h"
70 #include "llvm/Support/Casting.h"
71 #include "llvm/Support/Compiler.h"
72 #include "llvm/Support/DOTGraphTraits.h"
73 #include "llvm/Support/ErrorHandling.h"
74 #include "llvm/Support/GraphWriter.h"
75 #include "llvm/Support/SaveAndRestore.h"
76 #include "llvm/Support/raw_ostream.h"
85 using namespace clang;
88 #define DEBUG_TYPE "ExprEngine"
91 "The # of times RemoveDeadBindings is called");
93 "The # of aborted paths due to reaching the maximum block count in "
94 "a top level function");
95 STATISTIC(NumMaxBlockCountReachedInInlined,
96 "The # of aborted paths due to reaching the maximum block count in "
97 "an inlined function");
99 "The # of times we re-evaluated a call without inlining");
120 class ConstructedObjectKey {
121 using ConstructedObjectKeyImpl =
122 std::pair<ConstructionContextItem, const LocationContext *>;
123 const ConstructedObjectKeyImpl Impl;
131 const LocationContext *getLocationContext()
const {
return Impl.second; }
134 return getLocationContext()->getDecl()->getASTContext();
137 void printJson(llvm::raw_ostream &Out,
PrinterHelper *Helper,
139 const Stmt *S = getItem().getStmtOrNull();
142 I = getItem().getCXXCtorInitializer();
145 Out <<
"\"stmt_id\": " << S->getID(getASTContext());
147 Out <<
"\"init_id\": " << I->
getID(getASTContext());
150 Out <<
", \"kind\": \"" << getItem().getKindAsString()
151 <<
"\", \"argument_index\": ";
154 Out << getItem().getIndex();
159 Out <<
", \"pretty\": ";
162 S->printJson(Out, Helper, PP,
true);
168 void Profile(llvm::FoldingSetNodeID &
ID)
const {
170 ID.AddPointer(Impl.second);
173 bool operator==(
const ConstructedObjectKey &RHS)
const {
174 return Impl == RHS.Impl;
177 bool operator<(
const ConstructedObjectKey &RHS)
const {
178 return Impl < RHS.Impl;
183 typedef llvm::ImmutableMap<ConstructedObjectKey, SVal>
192 static const char* TagProviderName =
"ExprEngine";
197 : CTU(CTU), IsCTUEnabled(mgr.getAnalyzerOptions().IsNaiveCTUEnabled),
198 AMgr(mgr), AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),
199 Engine(*this, FS, mgr.getAnalyzerOptions()), G(Engine.getGraph()),
200 StateMgr(getContext(), mgr.getStoreManagerCreator(),
201 mgr.getConstraintManagerCreator(), G.getAllocator(), this),
202 SymMgr(StateMgr.getSymbolManager()), MRMgr(StateMgr.getRegionManager()),
203 svalBuilder(StateMgr.getSValBuilder()), ObjCNoRet(mgr.getASTContext()),
204 BR(mgr, *this), VisitedCallees(VisitedCalleesIn),
205 HowToInline(HowToInlineIn) {
206 unsigned TrimInterval = mgr.
options.GraphTrimInterval;
207 if (TrimInterval != 0) {
225 if (
const auto *FD = dyn_cast<FunctionDecl>(D)) {
229 if (!II || !(II->
getName() ==
"main" && FD->getNumParams() > 0))
234 const auto *BT = dyn_cast<BuiltinType>(T);
235 if (!BT || !BT->isInteger())
260 if (
const auto *MD = dyn_cast<ObjCMethodDecl>(D)) {
270 assert(
state &&
"'self' cannot be null");
274 if (
const auto *MD = dyn_cast<CXXMethodDecl>(D)) {
275 if (!MD->isStatic()) {
285 assert(
state &&
"'this' cannot be null");
296 const Expr *InitWithAdjustments,
const Expr *Result,
297 const SubRegion **OutRegionWithAdjustments) {
303 SVal InitValWithAdjustments =
State->getSVal(InitWithAdjustments, LC);
307 if (!isa<NonLoc>(InitValWithAdjustments)) {
308 if (OutRegionWithAdjustments)
309 *OutRegionWithAdjustments =
nullptr;
312 Result = InitWithAdjustments;
316 assert(!isa<Loc>(InitValWithAdjustments) ||
318 Result->getType()->isMemberPointerType());
321 ProgramStateManager &StateMgr =
State->getStateManager();
322 MemRegionManager &MRMgr = StateMgr.getRegionManager();
323 StoreManager &StoreMgr = StateMgr.getStoreManager();
350 CommaLHSs, Adjustments);
357 const TypedValueRegion *TR =
nullptr;
358 if (
const auto *MT = dyn_cast<MaterializeTemporaryExpr>(Result)) {
360 State = finishObjectConstruction(
State, MT, LC);
368 TR = MRMgr.getCXXStaticTempObjectRegion(Init);
370 TR = MRMgr.getCXXTempObjectRegion(Init, LC);
374 TR = MRMgr.getCXXTempObjectRegion(Init, LC);
377 SVal Reg = loc::MemRegionVal(TR);
384 Reg = StoreMgr.evalDerivedToBase(Reg, Adj.DerivedToBase.BasePath);
387 Reg = StoreMgr.getLValueField(Adj.Field, Reg);
391 State =
State->invalidateRegions(Reg, InitWithAdjustments,
393 nullptr,
nullptr,
nullptr);
406 SVal InitVal =
State->getSVal(Init, LC);
407 if (InitVal.isUnknown()) {
410 State =
State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC,
false);
414 if (InitValWithAdjustments.
isUnknown()) {
418 Result, LC, InitWithAdjustments->
getType(),
422 State->bindLoc(Reg.castAs<Loc>(), InitValWithAdjustments, LC,
false);
424 State =
State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC,
false);
430 if (Result->isGLValue()) {
433 State =
State->BindExpr(Result, LC, InitValWithAdjustments);
439 if (OutRegionWithAdjustments)
440 *OutRegionWithAdjustments = cast<SubRegion>(Reg.getAsRegion());
451 assert(!
State->get<ObjectsUnderConstruction>(Key) ||
452 Key.getItem().getKind() ==
454 return State->set<ObjectsUnderConstruction>(Key,
V);
470 assert(
State->contains<ObjectsUnderConstruction>(Key));
471 return State->remove<ObjectsUnderConstruction>(Key);
477 ConstructedObjectKey Key({BTE,
true}, LC);
480 return State->set<ObjectsUnderConstruction>(Key, UnknownVal());
487 ConstructedObjectKey Key({BTE,
true}, LC);
488 assert(
State->contains<ObjectsUnderConstruction>(Key));
489 return State->remove<ObjectsUnderConstruction>(Key);
495 ConstructedObjectKey Key({BTE,
true}, LC);
496 return State->contains<ObjectsUnderConstruction>(Key);
504 assert(LC &&
"ToLC must be a parent of FromLC!");
505 for (
auto I :
State->get<ObjectsUnderConstruction>())
506 if (I.first.getLocationContext() == LC)
522 SVal cond,
bool assumption) {
541 unsigned int Space = 0,
bool IsDot =
false) {
546 bool HasItem =
false;
549 const ConstructedObjectKey *LastKey =
nullptr;
550 for (
const auto &I :
State->get<ObjectsUnderConstruction>()) {
551 const ConstructedObjectKey &Key = I.first;
552 if (Key.getLocationContext() != LCtx)
563 for (
const auto &I :
State->get<ObjectsUnderConstruction>()) {
564 const ConstructedObjectKey &Key = I.first;
565 SVal
Value = I.second;
566 if (Key.getLocationContext() != LCtx)
569 Indent(Out, Space, IsDot) <<
"{ ";
570 Key.printJson(Out,
nullptr, PP);
571 Out <<
", \"value\": \"" <<
Value <<
"\" }";
579 Indent(Out, --Space, IsDot) <<
']';
587 unsigned int Space,
bool IsDot)
const {
588 Indent(Out, Space, IsDot) <<
"\"constructing_objects\": ";
590 if (LCtx && !
State->get<ObjectsUnderConstruction>().isEmpty()) {
598 Indent(Out, Space, IsDot) <<
"]," << NL;
600 Out <<
"null," << NL;
616 currStmtIdx = StmtIdx;
651 const ExplodedNode *Pred,
654 if (AMgr.options.AnalysisPurgeOpt == PurgeNone)
676 const Stmt *ReferenceStmt,
678 const Stmt *DiagnosticStmt,
681 ReferenceStmt ==
nullptr || isa<ReturnStmt>(ReferenceStmt))
682 &&
"PostStmt is not generally supported by the SymbolReaper yet");
683 assert(LC &&
"Must pass the current (or expiring) LocationContext");
685 if (!DiagnosticStmt) {
686 DiagnosticStmt = ReferenceStmt;
687 assert(DiagnosticStmt &&
"Required for clearing a LocationContext");
690 NumRemoveDeadBindings++;
696 if (!ReferenceStmt) {
698 "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext");
705 for (
auto I : CleanedState->get<ObjectsUnderConstruction>()) {
706 if (
SymbolRef Sym = I.second.getAsSymbol())
708 if (
const MemRegion *MR = I.second.getAsRegion())
717 CleanedState = StateMgr.removeDeadBindingsFromEnvironmentAndStore(
718 CleanedState, SFC, SymReaper);
727 DiagnosticStmt, *
this, K);
733 for (
const auto I : CheckedSet) {
740 assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->
getState()) &&
741 "Checkers are not allowed to modify the Environment as a part of "
742 "checkDeadSymbols processing.");
743 assert(StateMgr.haveEqualStores(CheckerState, Pred->
getState()) &&
744 "Checkers are not allowed to modify the Store as a part of "
745 "checkDeadSymbols processing.");
750 StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState);
751 Bldr.
generateNode(DiagnosticStmt, I, CleanedCheckerSt, &cleanupTag, K);
761 "Error evaluating statement");
770 CleanedStates.
Add(Pred);
774 for (
const auto I : CleanedStates) {
777 Visit(currStmt, I, DstI);
788 "Error evaluating end of the loop");
794 if(AMgr.
options.ShouldUnrollLoops)
811 "Error evaluating initializer");
815 const auto *
decl = cast<CXXConstructorDecl>(stackFrame->getDecl());
830 State = finishObjectConstruction(
State, BMI, LC);
832 PostStore PS(Init, LC,
nullptr,
nullptr);
845 if (Init->getType()->isArrayType()) {
849 while ((ASE = dyn_cast<ArraySubscriptExpr>(Init)))
852 SVal LValue =
State->getSVal(Init, stackFrame);
853 if (!Field->getType()->isReferenceType())
855 InitVal =
State->getSVal(*LValueLoc);
869 evalBind(Tmp, Init, Pred, FieldLoc, InitVal,
true, &PP);
882 for (
const auto I : Tmp) {
911 llvm_unreachable(
"Unexpected dtor kind.");
926 if (Opts.MayInlineCXXAllocator)
948 const MemRegion *ValueRegion =
state->getSVal(Region).getAsRegion();
957 varType = cast<TypedValueRegion>(Region)->getValueType();
968 false, Pred, Dst, CallOpts);
983 if (
State->isNull(ArgVal).isConstrainedTrue()) {
1002 while (
const auto *AT =
getContext().getAsArrayType(DTy))
1003 DTy = AT->getElementType();
1015 const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->
getDecl());
1028 true, Pred, Dst, CallOpts);
1038 const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->
getDecl());
1039 Loc ThisStorageLoc =
1041 Loc ThisLoc =
State->getSVal(ThisStorageLoc).castAs<
Loc>();
1048 FieldVal = makeZeroElementRegion(
State, FieldVal, T,
1052 false, Pred, Dst, CallOpts);
1071 MR =
V->getAsRegion();
1076 if (isDestructorElided(
State, BTE, LC)) {
1077 State = cleanupElidedDestructor(
State, BTE, LC);
1093 assert(CleanDtorState.
size() <= 1);
1095 CleanDtorState.
empty() ? Pred : *CleanDtorState.
begin();
1104 T = AT->getElementType();
1113 false, CleanPred, Dst, CallOpts);
1165 class CollectReachableSymbolsCallback final :
public SymbolVisitor {
1170 : Symbols(Symbols) {}
1174 bool VisitSymbol(
SymbolRef Sym)
override {
1175 Symbols.insert(Sym);
1180 CollectReachableSymbolsCallback CallBack(Symbols);
1182 State->scanReachableSymbols(
V, CallBack);
1185 State, CallBack.getSymbols(), Call, K,
nullptr);
1191 S->getBeginLoc(),
"Error evaluating statement");
1195 assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens());
1197 switch (S->getStmtClass()) {
1199 case Stmt::CXXDependentScopeMemberExprClass:
1200 case Stmt::CXXTryStmtClass:
1201 case Stmt::CXXTypeidExprClass:
1202 case Stmt::CXXUuidofExprClass:
1203 case Stmt::CXXFoldExprClass:
1204 case Stmt::MSPropertyRefExprClass:
1205 case Stmt::MSPropertySubscriptExprClass:
1206 case Stmt::CXXUnresolvedConstructExprClass:
1207 case Stmt::DependentScopeDeclRefExprClass:
1208 case Stmt::ArrayTypeTraitExprClass:
1209 case Stmt::ExpressionTraitExprClass:
1210 case Stmt::UnresolvedLookupExprClass:
1211 case Stmt::UnresolvedMemberExprClass:
1212 case Stmt::TypoExprClass:
1213 case Stmt::RecoveryExprClass:
1214 case Stmt::CXXNoexceptExprClass:
1215 case Stmt::PackExpansionExprClass:
1216 case Stmt::SubstNonTypeTemplateParmPackExprClass:
1217 case Stmt::FunctionParmPackExprClass:
1218 case Stmt::CoroutineBodyStmtClass:
1219 case Stmt::CoawaitExprClass:
1220 case Stmt::DependentCoawaitExprClass:
1221 case Stmt::CoreturnStmtClass:
1222 case Stmt::CoyieldExprClass:
1223 case Stmt::SEHTryStmtClass:
1224 case Stmt::SEHExceptStmtClass:
1225 case Stmt::SEHLeaveStmtClass:
1226 case Stmt::SEHFinallyStmtClass:
1227 case Stmt::OMPCanonicalLoopClass:
1228 case Stmt::OMPParallelDirectiveClass:
1229 case Stmt::OMPSimdDirectiveClass:
1230 case Stmt::OMPForDirectiveClass:
1231 case Stmt::OMPForSimdDirectiveClass:
1232 case Stmt::OMPSectionsDirectiveClass:
1233 case Stmt::OMPSectionDirectiveClass:
1234 case Stmt::OMPSingleDirectiveClass:
1235 case Stmt::OMPMasterDirectiveClass:
1236 case Stmt::OMPCriticalDirectiveClass:
1237 case Stmt::OMPParallelForDirectiveClass:
1238 case Stmt::OMPParallelForSimdDirectiveClass:
1239 case Stmt::OMPParallelSectionsDirectiveClass:
1240 case Stmt::OMPParallelMasterDirectiveClass:
1241 case Stmt::OMPParallelMaskedDirectiveClass:
1242 case Stmt::OMPTaskDirectiveClass:
1243 case Stmt::OMPTaskyieldDirectiveClass:
1244 case Stmt::OMPBarrierDirectiveClass:
1245 case Stmt::OMPTaskwaitDirectiveClass:
1246 case Stmt::OMPTaskgroupDirectiveClass:
1247 case Stmt::OMPFlushDirectiveClass:
1248 case Stmt::OMPDepobjDirectiveClass:
1249 case Stmt::OMPScanDirectiveClass:
1250 case Stmt::OMPOrderedDirectiveClass:
1251 case Stmt::OMPAtomicDirectiveClass:
1252 case Stmt::OMPTargetDirectiveClass:
1253 case Stmt::OMPTargetDataDirectiveClass:
1254 case Stmt::OMPTargetEnterDataDirectiveClass:
1255 case Stmt::OMPTargetExitDataDirectiveClass:
1256 case Stmt::OMPTargetParallelDirectiveClass:
1257 case Stmt::OMPTargetParallelForDirectiveClass:
1258 case Stmt::OMPTargetUpdateDirectiveClass:
1259 case Stmt::OMPTeamsDirectiveClass:
1260 case Stmt::OMPCancellationPointDirectiveClass:
1261 case Stmt::OMPCancelDirectiveClass:
1262 case Stmt::OMPTaskLoopDirectiveClass:
1263 case Stmt::OMPTaskLoopSimdDirectiveClass:
1264 case Stmt::OMPMasterTaskLoopDirectiveClass:
1265 case Stmt::OMPMasterTaskLoopSimdDirectiveClass:
1266 case Stmt::OMPParallelMasterTaskLoopDirectiveClass:
1267 case Stmt::OMPParallelMasterTaskLoopSimdDirectiveClass:
1268 case Stmt::OMPDistributeDirectiveClass:
1269 case Stmt::OMPDistributeParallelForDirectiveClass:
1270 case Stmt::OMPDistributeParallelForSimdDirectiveClass:
1271 case Stmt::OMPDistributeSimdDirectiveClass:
1272 case Stmt::OMPTargetParallelForSimdDirectiveClass:
1273 case Stmt::OMPTargetSimdDirectiveClass:
1274 case Stmt::OMPTeamsDistributeDirectiveClass:
1275 case Stmt::OMPTeamsDistributeSimdDirectiveClass:
1276 case Stmt::OMPTeamsDistributeParallelForSimdDirectiveClass:
1277 case Stmt::OMPTeamsDistributeParallelForDirectiveClass:
1278 case Stmt::OMPTargetTeamsDirectiveClass:
1279 case Stmt::OMPTargetTeamsDistributeDirectiveClass:
1280 case Stmt::OMPTargetTeamsDistributeParallelForDirectiveClass:
1281 case Stmt::OMPTargetTeamsDistributeParallelForSimdDirectiveClass:
1282 case Stmt::OMPTargetTeamsDistributeSimdDirectiveClass:
1283 case Stmt::OMPTileDirectiveClass:
1284 case Stmt::OMPInteropDirectiveClass:
1285 case Stmt::OMPDispatchDirectiveClass:
1286 case Stmt::OMPMaskedDirectiveClass:
1287 case Stmt::OMPGenericLoopDirectiveClass:
1288 case Stmt::OMPTeamsGenericLoopDirectiveClass:
1289 case Stmt::OMPTargetTeamsGenericLoopDirectiveClass:
1290 case Stmt::OMPParallelGenericLoopDirectiveClass:
1291 case Stmt::OMPTargetParallelGenericLoopDirectiveClass:
1292 case Stmt::CapturedStmtClass:
1293 case Stmt::OMPUnrollDirectiveClass:
1294 case Stmt::OMPMetaDirectiveClass: {
1300 case Stmt::ParenExprClass:
1301 llvm_unreachable(
"ParenExprs already handled.");
1302 case Stmt::GenericSelectionExprClass:
1303 llvm_unreachable(
"GenericSelectionExprs already handled.");
1306 case Stmt::BreakStmtClass:
1307 case Stmt::CaseStmtClass:
1308 case Stmt::CompoundStmtClass:
1309 case Stmt::ContinueStmtClass:
1310 case Stmt::CXXForRangeStmtClass:
1311 case Stmt::DefaultStmtClass:
1312 case Stmt::DoStmtClass:
1313 case Stmt::ForStmtClass:
1314 case Stmt::GotoStmtClass:
1315 case Stmt::IfStmtClass:
1316 case Stmt::IndirectGotoStmtClass:
1317 case Stmt::LabelStmtClass:
1319 case Stmt::NullStmtClass:
1320 case Stmt::SwitchStmtClass:
1321 case Stmt::WhileStmtClass:
1322 case Expr::MSDependentExistsStmtClass:
1323 llvm_unreachable(
"Stmt should not be in analyzer evaluation loop");
1324 case Stmt::ImplicitValueInitExprClass:
1328 llvm_unreachable(
"Should be pruned from CFG");
1330 case Stmt::ObjCSubscriptRefExprClass:
1331 case Stmt::ObjCPropertyRefExprClass:
1332 llvm_unreachable(
"These are handled by PseudoObjectExpr");
1334 case Stmt::GNUNullExprClass: {
1344 case Stmt::ObjCAtSynchronizedStmtClass:
1350 case Expr::ConstantExprClass:
1351 case Stmt::ExprWithCleanupsClass:
1355 case Stmt::CXXBindTemporaryExprClass: {
1366 case Stmt::ArrayInitLoopExprClass:
1372 case Stmt::DesignatedInitExprClass:
1373 case Stmt::DesignatedInitUpdateExprClass:
1374 case Stmt::ArrayInitIndexExprClass:
1375 case Stmt::ExtVectorElementExprClass:
1376 case Stmt::ImaginaryLiteralClass:
1377 case Stmt::ObjCAtCatchStmtClass:
1378 case Stmt::ObjCAtFinallyStmtClass:
1379 case Stmt::ObjCAtTryStmtClass:
1380 case Stmt::ObjCAutoreleasePoolStmtClass:
1381 case Stmt::ObjCEncodeExprClass:
1382 case Stmt::ObjCIsaExprClass:
1383 case Stmt::ObjCProtocolExprClass:
1384 case Stmt::ObjCSelectorExprClass:
1385 case Stmt::ParenListExprClass:
1386 case Stmt::ShuffleVectorExprClass:
1387 case Stmt::ConvertVectorExprClass:
1388 case Stmt::VAArgExprClass:
1389 case Stmt::CUDAKernelCallExprClass:
1390 case Stmt::OpaqueValueExprClass:
1391 case Stmt::AsTypeExprClass:
1392 case Stmt::ConceptSpecializationExprClass:
1393 case Stmt::CXXRewrittenBinaryOperatorClass:
1394 case Stmt::RequiresExprClass:
1399 case Stmt::PredefinedExprClass:
1400 case Stmt::AddrLabelExprClass:
1401 case Stmt::AttributedStmtClass:
1402 case Stmt::IntegerLiteralClass:
1403 case Stmt::FixedPointLiteralClass:
1404 case Stmt::CharacterLiteralClass:
1405 case Stmt::CXXScalarValueInitExprClass:
1406 case Stmt::CXXBoolLiteralExprClass:
1407 case Stmt::ObjCBoolLiteralExprClass:
1408 case Stmt::ObjCAvailabilityCheckExprClass:
1409 case Stmt::FloatingLiteralClass:
1410 case Stmt::NoInitExprClass:
1411 case Stmt::SizeOfPackExprClass:
1412 case Stmt::StringLiteralClass:
1413 case Stmt::SourceLocExprClass:
1414 case Stmt::ObjCStringLiteralClass:
1415 case Stmt::CXXPseudoDestructorExprClass:
1416 case Stmt::SubstNonTypeTemplateParmExprClass:
1417 case Stmt::CXXNullPtrLiteralExprClass:
1418 case Stmt::OMPArraySectionExprClass:
1419 case Stmt::OMPArrayShapingExprClass:
1420 case Stmt::OMPIteratorExprClass:
1421 case Stmt::SYCLUniqueStableNameExprClass:
1422 case Stmt::TypeTraitExprClass: {
1431 case Stmt::CXXDefaultArgExprClass:
1432 case Stmt::CXXDefaultInitExprClass: {
1441 if (
const auto *DefE = dyn_cast<CXXDefaultArgExpr>(S))
1442 ArgE = DefE->getExpr();
1443 else if (
const auto *DefE = dyn_cast<CXXDefaultInitExpr>(S))
1444 ArgE = DefE->getExpr();
1446 llvm_unreachable(
"unknown constant wrapper kind");
1448 bool IsTemporary =
false;
1449 if (
const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(ArgE)) {
1450 ArgE = MTE->getSubExpr();
1459 for (
const auto I : PreVisit) {
1461 State =
State->BindExpr(S, LCtx, *ConstantVal);
1463 State = createTemporaryRegionIfNeeded(
State, LCtx,
1475 case Stmt::CXXStdInitializerListExprClass:
1476 case Expr::ObjCArrayLiteralClass:
1477 case Expr::ObjCDictionaryLiteralClass:
1478 case Expr::ObjCBoxedExprClass: {
1487 const auto *Ex = cast<Expr>(S);
1488 QualType resultType = Ex->getType();
1490 for (
const auto N : preVisit) {
1499 if (!(isa<ObjCBoxedExpr>(Ex) &&
1500 !cast<ObjCBoxedExpr>(Ex)->getSubExpr()
1502 for (
auto Child : Ex->children()) {
1516 case Stmt::ArraySubscriptExprClass:
1522 case Stmt::MatrixSubscriptExprClass:
1523 llvm_unreachable(
"Support for MatrixSubscriptExpr is not implemented.");
1526 case Stmt::GCCAsmStmtClass:
1532 case Stmt::MSAsmStmtClass:
1538 case Stmt::BlockExprClass:
1544 case Stmt::LambdaExprClass:
1545 if (AMgr.
options.ShouldInlineLambdas) {
1555 case Stmt::BinaryOperatorClass: {
1556 const auto *B = cast<BinaryOperator>(S);
1557 if (B->isLogicalOp()) {
1563 else if (B->getOpcode() == BO_Comma) {
1567 state->getSVal(B->getRHS(),
1574 if (AMgr.
options.ShouldEagerlyAssume &&
1575 (B->isRelationalOp() || B->isEqualityOp())) {
1587 case Stmt::CXXOperatorCallExprClass: {
1588 const auto *OCE = cast<CXXOperatorCallExpr>(S);
1592 const Decl *Callee = OCE->getCalleeDecl();
1593 if (
const auto *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) {
1594 if (MD->isInstance()) {
1598 createTemporaryRegionIfNeeded(
State, LCtx, OCE->getArg(0));
1599 if (NewState !=
State) {
1612 case Stmt::CallExprClass:
1613 case Stmt::CXXMemberCallExprClass:
1614 case Stmt::UserDefinedLiteralClass:
1620 case Stmt::CXXCatchStmtClass:
1626 case Stmt::CXXTemporaryObjectExprClass:
1627 case Stmt::CXXConstructExprClass:
1633 case Stmt::CXXInheritedCtorInitExprClass:
1640 case Stmt::CXXNewExprClass: {
1647 for (
const auto i : PreVisit)
1655 case Stmt::CXXDeleteExprClass: {
1658 const auto *CDE = cast<CXXDeleteExpr>(S);
1663 for (
const auto i : PostVisit)
1672 case Stmt::ChooseExprClass: {
1674 const auto *C = cast<ChooseExpr>(S);
1680 case Stmt::CompoundAssignOperatorClass:
1686 case Stmt::CompoundLiteralExprClass:
1692 case Stmt::BinaryConditionalOperatorClass:
1693 case Stmt::ConditionalOperatorClass: {
1695 const auto *C = cast<AbstractConditionalOperator>(S);
1701 case Stmt::CXXThisExprClass:
1707 case Stmt::DeclRefExprClass: {
1709 const auto *DE = cast<DeclRefExpr>(S);
1715 case Stmt::DeclStmtClass:
1721 case Stmt::ImplicitCastExprClass:
1722 case Stmt::CStyleCastExprClass:
1723 case Stmt::CXXStaticCastExprClass:
1724 case Stmt::CXXDynamicCastExprClass:
1725 case Stmt::CXXReinterpretCastExprClass:
1726 case Stmt::CXXConstCastExprClass:
1727 case Stmt::CXXFunctionalCastExprClass:
1728 case Stmt::BuiltinBitCastExprClass:
1729 case Stmt::ObjCBridgedCastExprClass:
1730 case Stmt::CXXAddrspaceCastExprClass: {
1732 const auto *C = cast<CastExpr>(S);
1734 VisitCast(C, C->getSubExpr(), Pred, dstExpr);
1742 case Expr::MaterializeTemporaryExprClass: {
1744 const auto *MTE = cast<MaterializeTemporaryExpr>(S);
1748 for (
const auto i : dstPrevisit)
1755 case Stmt::InitListExprClass:
1761 case Stmt::MemberExprClass:
1767 case Stmt::AtomicExprClass:
1773 case Stmt::ObjCIvarRefExprClass:
1779 case Stmt::ObjCForCollectionStmtClass:
1785 case Stmt::ObjCMessageExprClass:
1791 case Stmt::ObjCAtThrowStmtClass:
1792 case Stmt::CXXThrowExprClass:
1798 case Stmt::ReturnStmtClass:
1804 case Stmt::OffsetOfExprClass: {
1810 for (
const auto Node : PreVisit)
1818 case Stmt::UnaryExprOrTypeTraitExprClass:
1825 case Stmt::StmtExprClass: {
1826 const auto *SE = cast<StmtExpr>(S);
1828 if (SE->getSubStmt()->body_empty()) {
1831 &&
"Empty statement expression must have void type.");
1835 if (
const auto *LastExpr =
1836 dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
1840 state->getSVal(LastExpr,
1846 case Stmt::UnaryOperatorClass: {
1848 const auto *
U = cast<UnaryOperator>(S);
1849 if (AMgr.
options.ShouldEagerlyAssume && (
U->getOpcode() == UO_LNot)) {
1860 case Stmt::PseudoObjectExprClass: {
1863 const auto *PE = cast<PseudoObjectExpr>(S);
1864 if (
const Expr *Result = PE->getResultExpr()) {
1878 case Expr::ObjCIndirectCopyRestoreExprClass: {
1884 const auto *OIE = cast<ObjCIndirectCopyRestoreExpr>(S);
1885 const Expr *E = OIE->getSubExpr();
1895 bool ExprEngine::replayWithoutInlining(
ExplodedNode *N,
1899 assert(CalleeSF && CallerSF);
1906 BeforeProcessingCall = N;
1921 if (SP->getStmt() == CE)
1926 if (!BeforeProcessingCall)
1939 NewNodeState->set<ReplayWithoutInlining>(
const_cast<Stmt *
>(CE));
1943 ExplodedNode *NewNode = G.
getNode(NewNodeLoc, NewNodeState,
false, &IsNew);
1954 NumTimesRetriedWithoutInlining++;
1965 if(AMgr.
options.ShouldUnrollLoops) {
1970 Pred, maxBlockVisitOnPath);
1971 if (NewState != Pred->
getState()) {
1987 AMgr.
options.ShouldWidenLoops) {
1989 if (!isa_and_nonnull<ForStmt, WhileStmt, DoStmt>(Term))
2010 (*G.
roots_begin())->getLocation().getLocationContext();
2019 replayWithoutInlining(Pred, CalleeLC)))
2021 NumMaxBlockCountReachedInInlined++;
2023 NumMaxBlockCountReached++;
2026 Engine.blocksExhausted.push_back(std::make_pair(L, Sink));
2040 const Stmt *Condition,
2044 const auto *Ex = dyn_cast<Expr>(
Condition);
2046 return UnknownVal();
2049 bool bitsInit =
false;
2051 while (
const auto *CE = dyn_cast<CastExpr>(Ex)) {
2055 return UnknownVal();
2058 if (!bitsInit || newBits < bits) {
2063 Ex = CE->getSubExpr();
2071 return UnknownVal();
2073 return state->getSVal(Ex, LCtx);
2079 const auto *BO = dyn_cast<BinaryOperator>(
Condition);
2080 if (!BO || !BO->isLogicalOp()) {
2083 Condition = BO->getRHS()->IgnoreParens();
2105 if (
const auto *Ex = dyn_cast<Expr>(
Condition))
2108 const auto *BO = dyn_cast<BinaryOperator>(
Condition);
2109 if (!BO || !BO->isLogicalOp())
2113 "Other kinds of branches are handled separately!");
2124 for (; I != E; ++I) {
2129 const Stmt *LastStmt = CS->getStmt();
2133 llvm_unreachable(
"could not resolve condition");
2137 std::pair<const ObjCForCollectionStmt *, const LocationContext *>;
2144 assert(!
State->contains<ObjCForHasMoreIterations>({O, LC}));
2145 return State->set<ObjCForHasMoreIterations>({O, LC}, HasMoreIteraton);
2152 assert(
State->contains<ObjCForHasMoreIterations>({O, LC}));
2153 return State->remove<ObjCForHasMoreIterations>({O, LC});
2159 assert(
State->contains<ObjCForHasMoreIterations>({O, LC}));
2160 return *
State->get<ObjCForHasMoreIterations>({O, LC});
2169 if (
const auto *ObjCFor = dyn_cast<ObjCForCollectionStmt>(
Condition)) {
2170 bool HasMoreIteraton =
2176 N->getLocationContext());
2177 if (HasMoreIteraton)
2178 return std::pair<ProgramStateRef, ProgramStateRef>{
State,
nullptr};
2180 return std::pair<ProgramStateRef, ProgramStateRef>{
nullptr,
State};
2184 if (
X.isUnknownOrUndef()) {
2186 if (
const auto *Ex = dyn_cast<Expr>(
Condition)) {
2187 if (Ex->getType()->isIntegralOrEnumerationType()) {
2194 N->getState()->getStateManager().getContext());
2196 if (!recovered.isUnknown()) {
2204 if (
X.isUnknownOrUndef())
2207 DefinedSVal
V =
X.castAs<DefinedSVal>();
2220 "CXXBindTemporaryExprs are handled by processBindTemporary.");
2223 currBldrCtx = &BldCtx;
2233 if (
const auto *Ex = dyn_cast<Expr>(
Condition))
2239 "Error evaluating branch");
2245 if (CheckersOutSet.
empty())
2250 if (PredN->isSink())
2257 std::tie(StTrue, StFalse) = *KnownCondValueAssumption;
2259 assert(!isa<ObjCForCollectionStmt>(
Condition));
2264 if (StTrue && StFalse)
2265 assert(!isa<ObjCForCollectionStmt>(
Condition));
2283 currBldrCtx =
nullptr;
2289 llvm::ImmutableSet<const VarDecl *>)
2292 NodeBuilderContext &BuilderCtx,
2294 ExplodedNodeSet &Dst,
2297 PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
2298 currBldrCtx = &BuilderCtx;
2302 bool initHasRun =
state->contains<InitializedGlobalsSet>(VD);
2303 BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF);
2306 state =
state->add<InitializedGlobalsSet>(VD);
2309 builder.generateNode(
state, initHasRun, Pred);
2310 builder.markInfeasible(!initHasRun);
2312 currBldrCtx =
nullptr;
2333 for (iterator I = builder.
begin(), E = builder.
end(); I != E; ++I) {
2334 if (I.getLabel() == L) {
2340 llvm_unreachable(
"No block with label.");
2343 if (isa<UndefinedVal, loc::ConcreteInt>(
V)) {
2354 for (iterator I = builder.
begin(), E = builder.
end(); I != E; ++I)
2374 State = finishArgumentConstruction(
2389 while (LC != ToLC) {
2390 assert(LC &&
"ToLC must be a parent of FromLC!");
2391 for (
auto I :
State->get<ObjectsUnderConstruction>())
2392 if (I.first.getLocationContext() == LC) {
2396 assert(I.first.getItem().getKind() ==
2398 I.first.getItem().getKind() ==
2400 State =
State->remove<ObjectsUnderConstruction>(I.first);
2418 assert(areAllObjectsFullyConstructed(Pred->
getState(),
2431 for (
const auto I : AfterRemovedDead)
2449 if (CondV_untested.
isUndef()) {
2460 iterator I = builder.
begin(), EI = builder.
end();
2461 bool defaultIsFeasible = I == EI;
2463 for ( ; I != EI; ++I) {
2468 const CaseStmt *Case = I.getCase();
2483 std::tie(StateCase, DefaultSt) =
2484 DefaultSt->assumeInclusiveRange(*NL, V1, V2);
2486 StateCase = DefaultSt;
2494 defaultIsFeasible =
true;
2496 defaultIsFeasible =
false;
2501 if (!defaultIsFeasible)
2533 if (
const auto *VD = dyn_cast<VarDecl>(D)) {
2536 assert(Ex->
isGLValue() || VD->getType()->isVoidType());
2539 const auto *MD = dyn_cast_or_null<CXXMethodDecl>(D);
2540 const auto *DeclRefEx = dyn_cast<DeclRefExpr>(Ex);
2543 if (AMgr.
options.ShouldInlineLambdas && DeclRefEx &&
2544 DeclRefEx->refersToEnclosingVariableOrCapture() && MD &&
2545 MD->getParent()->isLambda()) {
2548 llvm::DenseMap<const VarDecl *, FieldDecl *> LambdaCaptureFields;
2554 if (
const FieldDecl *FD = LambdaCaptureFields[VD]) {
2557 SVal CXXThisVal =
state->getSVal(CXXThis);
2558 VInfo = std::make_pair(
state->getLValue(FD, CXXThisVal), FD->getType());
2563 VInfo = std::make_pair(
state->getLValue(VD, LocCtxt), VD->getType());
2565 SVal V = VInfo->first;
2566 bool IsReference = VInfo->second->isReferenceType();
2581 if (
const auto *ED = dyn_cast<EnumConstantDecl>(D)) {
2587 if (
const auto *FD = dyn_cast<FunctionDecl>(D)) {
2593 if (isa<FieldDecl, IndirectFieldDecl>(D)) {
2598 if (
const auto *BD = dyn_cast<BindingDecl>(D)) {
2599 const auto *DD = cast<DecompositionDecl>(BD->getDecomposedDecl());
2602 if (DD->getType()->isReferenceType()) {
2609 if (
const auto *ME = dyn_cast<MemberExpr>(BD->getBinding())) {
2610 const auto *Field = cast<FieldDecl>(ME->getMemberDecl());
2614 else if (
const auto *ASE = dyn_cast<ArraySubscriptExpr>(BD->getBinding())) {
2615 SVal Idx =
state->getSVal(ASE->getIdx(), LCtx);
2620 assert(Idx.
isConstant() &&
"BindingDecl array index is not a constant!");
2622 V =
state->getLValue(BD->getType(), Idx,
Base);
2625 else if (BD->getHoldingVar()) {
2629 llvm_unreachable(
"An unknown case of structured binding encountered!");
2637 llvm_unreachable(
"Support for this Decl not implemented.");
2652 for (
auto *
Node : CheckerPreStmt) {
2692 if (
const auto *ME = dyn_cast<MemberExpr>(Arr)) {
2693 Expr *MEBase = ME->getBase();
2696 if (
auto CXXSCE = dyn_cast<CXXStaticCastExpr>(MEBase)) {
2697 MEBase = CXXSCE->getSubExpr();
2700 auto ObjDeclExpr = cast<DeclRefExpr>(MEBase);
2701 SVal Obj =
state->getLValue(cast<VarDecl>(ObjDeclExpr->getDecl()), LCtx);
2703 Base =
state->getLValue(cast<FieldDecl>(ME->getMemberDecl()), Obj);
2718 if (
const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Arr))
2719 Base =
state->getLValue(cast<VarDecl>(DRE->getDecl()), LCtx);
2754 for (
auto *
Node : CheckerPreStmt) {
2758 if (IsGLValueLike) {
2768 state->getSVal(Idx, LCtx),
2772 }
else if (IsVectorType) {
2776 llvm_unreachable(
"Array subscript should be an lValue when not \
2777 a vector and not a forbidden lvalue type");
2796 if (isa<VarDecl, EnumConstantDecl>(
Member)) {
2797 for (
const auto I : CheckedSet)
2803 for (
const auto I : CheckedSet) {
2809 if (
const auto *MD = dyn_cast<CXXMethodDecl>(
Member)) {
2810 if (MD->isInstance())
2811 state = createTemporaryRegionIfNeeded(
state, LCtx, BaseExpr);
2822 state = createTemporaryRegionIfNeeded(
state, LCtx, BaseExpr,
2828 const auto *field = cast<FieldDecl>(
Member);
2829 SVal L =
state->getLValue(field, baseExprVal);
2839 dyn_cast<ImplicitCastExpr>(I->getParentMap().getParentIgnoreParens(M));
2840 if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) {
2841 llvm_unreachable(
"should always be wrapped in ArrayToPointerDecay");
2845 if (field->getType()->isReferenceType()) {
2847 L =
state->getSVal(R);
2876 for (
const auto I : AfterPreSet) {
2881 for (
unsigned SI = 0, Count = AE->
getNumSubExprs(); SI != Count; SI++) {
2883 SVal SubExprVal =
State->getSVal(SubExpr, LCtx);
2884 ValuesToInvalidate.push_back(SubExprVal);
2887 State =
State->invalidateRegions(ValuesToInvalidate, AE,
2894 State =
State->BindExpr(AE, LCtx, ResultVal);
2914 for (
const std::pair<SVal, SVal> &LocAndVal : LocAndVals) {
2916 const MemRegion *MR = LocAndVal.first.getAsRegion();
2918 Escaped.push_back(LocAndVal.second);
2923 if (
const auto *VR = dyn_cast<VarRegion>(MR->
getBaseRegion()))
2924 if (VR->hasStackParametersStorage() && VR->getStackFrame()->inTopFrame())
2925 if (
const auto *RD = VR->getValueType()->getAsCXXRecordDecl())
2926 if (!RD->hasTrivialDestructor()) {
2927 Escaped.push_back(LocAndVal.second);
2937 if (StoredVal != LocAndVal.second)
2940 Escaped.push_back(LocAndVal.second);
2943 if (Escaped.empty())
2946 return escapeValues(
State, Escaped,
Kind, Call);
2952 std::pair<SVal, SVal> LocAndVal(
Loc, Val);
2963 if (!Invalidated || Invalidated->empty())
2976 for (
const auto I : ExplicitRegions) {
2978 SymbolsDirectlyInvalidated.insert(R->getSymbol());
2982 for (
const auto &sym : *Invalidated) {
2983 if (SymbolsDirectlyInvalidated.count(sym))
2985 SymbolsIndirectlyInvalidated.insert(sym);
2988 if (!SymbolsDirectlyInvalidated.empty())
2993 if (!SymbolsIndirectlyInvalidated.empty())
3014 StoreE, *
this, *PP);
3020 if (!isa<Loc>(location)) {
3025 Bldr.generateNode(L,
state, Pred);
3029 for (
const auto PredI : CheckedSet) {
3038 Val, LC, !atDeclInit);
3040 const MemRegion *LocReg =
nullptr;
3042 location.
getAs<loc::MemRegionVal>()) {
3043 LocReg = LocRegVal->getRegion();
3047 Bldr.generateNode(L,
state, PredI);
3060 const Expr *LocationE,
3066 const Expr *StoreE = AssignE ? AssignE : LocationE;
3070 evalLocation(Tmp, AssignE, LocationE, Pred,
state, location,
false);
3078 for (
const auto I : Tmp)
3079 evalBind(Dst, StoreE, I, location, Val,
false);
3084 const Expr *BoundEx,
3090 assert(!isa<NonLoc>(location) &&
"location cannot be a NonLoc.");
3095 evalLocation(Tmp, NodeEx, BoundEx, Pred,
state, location,
true);
3104 for (
const auto I : Tmp) {
3105 state = I->getState();
3122 const Stmt *BoundEx,
3133 ExplodedNodeSet Src;
3134 BldrTop.takeNodes(Pred);
3135 StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx);
3147 Bldr.generateNode(NodeEx, Pred,
state, &tag);
3149 ExplodedNodeSet Tmp;
3151 NodeEx, BoundEx, *
this);
3152 BldrTop.addNodes(Tmp);
3155 std::pair<const ProgramPointTag *, const ProgramPointTag*>
3158 eagerlyAssumeBinOpBifurcationTrue(TagProviderName,
3159 "Eagerly Assume True"),
3160 eagerlyAssumeBinOpBifurcationFalse(TagProviderName,
3161 "Eagerly Assume False");
3162 return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue,
3163 &eagerlyAssumeBinOpBifurcationFalse);
3171 for (
const auto Pred : Src) {
3183 if (SEV && SEV->isExpression()) {
3184 const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags =
3188 std::tie(StateTrue, StateFalse) =
state->assume(*SEV);
3221 assert(!isa<NonLoc>(
X));
3247 BugReporter &BR =
static_cast<ExprEngine &
>(
3248 N->getState()->getStateManager().getOwningEngine()).getBugReporter();
3250 const auto EQClasses =
3251 llvm::make_range(BR.EQClasses_begin(), BR.EQClasses_end());
3253 for (
const auto &
EQ : EQClasses) {
3254 for (
const auto &I :
EQ.getReports()) {
3255 const auto *PR = dyn_cast<PathSensitiveBugReport>(I.get());
3258 const ExplodedNode *EN = PR->getErrorNode();
3259 if (EN->getState() == N->getState() &&
3260 EN->getLocation() == N->getLocation())
3272 const ExplodedNode *N,
3273 llvm::function_ref<
void(
const ExplodedNode *)> PreCallback,
3274 llvm::function_ref<
void(
const ExplodedNode *)> PostCallback,
3275 llvm::function_ref<
bool(
const ExplodedNode *)> Stop) {
3281 if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc(),
nullptr))
3285 N = N->getFirstSucc();
3291 return N->isTrivial();
3296 llvm::raw_string_ostream Out(Buf);
3298 const bool IsDot =
true;
3299 const unsigned int Space = 1;
3302 Out <<
"{ \"state_id\": " <<
State->getID()
3305 Indent(Out, Space, IsDot) <<
"\"program_points\": [\\l";
3308 traverseHiddenNodes(
3310 [&](
const ExplodedNode *OtherNode) {
3311 Indent(Out, Space + 1, IsDot) <<
"{ ";
3312 OtherNode->getLocation().printJson(Out,
"\\l");
3313 Out <<
", \"tag\": ";
3315 Out <<
'\"' << Tag->getTagDescription() <<
"\"";
3318 Out <<
", \"node_id\": " << OtherNode->getID() <<
3319 ", \"is_sink\": " << OtherNode->isSink() <<
3320 ", \"has_report\": " << nodeHasBugReport(OtherNode) <<
" }";
3323 [&](
const ExplodedNode *) { Out <<
",\\l"; },
3324 [&](
const ExplodedNode *) {
return false; });
3327 Indent(Out, Space, IsDot) <<
"],\\l";
3329 State->printDOT(Out, N->getLocationContext(), Space);
3340 llvm::DisplayGraph(
Filename,
false, llvm::GraphProgram::DOT);
3345 llvm::DisplayGraph(
Filename,
false, llvm::GraphProgram::DOT);
3350 std::vector<const ExplodedNode *> Src;
3356 dyn_cast<PathSensitiveBugReport>(EI->getReports()[0].get());
3359 const auto *N =
const_cast<ExplodedNode *
>(R->getErrorNode());
3365 return llvm::WriteGraph(&G,
"ExprEngine",
false,
3372 std::unique_ptr<ExplodedGraph> TrimmedG(G.
trim(
Nodes));
3374 if (!TrimmedG.get()) {
3375 llvm::errs() <<
"warning: Trimmed ExplodedGraph is empty.\n";
3379 return llvm::WriteGraph(TrimmedG.get(),
"TrimmedExprEngine",
3381 "Trimmed Exploded Graph",
3386 static int index = 0;
3390 void ExprEngine::anchor() { }