1 //===- SValBuilder.cpp - Basic class for all SValBuilder implementations --===//
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-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines SValBuilder, the base class for all (complete) SValBuilder
10 // implementations.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
15 #include "clang/AST/ASTContext.h"
16 #include "clang/AST/Decl.h"
17 #include "clang/AST/DeclCXX.h"
18 #include "clang/AST/ExprCXX.h"
19 #include "clang/AST/ExprObjC.h"
20 #include "clang/AST/Stmt.h"
21 #include "clang/AST/Type.h"
22 #include "clang/Basic/LLVM.h"
23 #include "clang/Analysis/AnalysisDeclContext.h"
24 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
25 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
26 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
27 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
28 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
29 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
30 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
31 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
32 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
33 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
34 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
35 #include "llvm/ADT/APSInt.h"
36 #include "llvm/ADT/None.h"
37 #include "llvm/ADT/Optional.h"
38 #include "llvm/Support/Casting.h"
39 #include "llvm/Support/Compiler.h"
40 #include <cassert>
41 #include <tuple>
42
43 using namespace clang;
44 using namespace ento;
45
46 //===----------------------------------------------------------------------===//
47 // Basic SVal creation.
48 //===----------------------------------------------------------------------===//
49
anchor()50 void SValBuilder::anchor() {}
51
makeZeroVal(QualType type)52 DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType type) {
53 if (Loc::isLocType(type))
54 return makeNull();
55
56 if (type->isIntegralOrEnumerationType())
57 return makeIntVal(0, type);
58
59 if (type->isArrayType() || type->isRecordType() || type->isVectorType() ||
60 type->isAnyComplexType())
61 return makeCompoundVal(type, BasicVals.getEmptySValList());
62
63 // FIXME: Handle floats.
64 return UnknownVal();
65 }
66
makeNonLoc(const SymExpr * lhs,BinaryOperator::Opcode op,const llvm::APSInt & rhs,QualType type)67 NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
68 const llvm::APSInt& rhs, QualType type) {
69 // The Environment ensures we always get a persistent APSInt in
70 // BasicValueFactory, so we don't need to get the APSInt from
71 // BasicValueFactory again.
72 assert(lhs);
73 assert(!Loc::isLocType(type));
74 return nonloc::SymbolVal(SymMgr.getSymIntExpr(lhs, op, rhs, type));
75 }
76
makeNonLoc(const llvm::APSInt & lhs,BinaryOperator::Opcode op,const SymExpr * rhs,QualType type)77 NonLoc SValBuilder::makeNonLoc(const llvm::APSInt& lhs,
78 BinaryOperator::Opcode op, const SymExpr *rhs,
79 QualType type) {
80 assert(rhs);
81 assert(!Loc::isLocType(type));
82 return nonloc::SymbolVal(SymMgr.getIntSymExpr(lhs, op, rhs, type));
83 }
84
makeNonLoc(const SymExpr * lhs,BinaryOperator::Opcode op,const SymExpr * rhs,QualType type)85 NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
86 const SymExpr *rhs, QualType type) {
87 assert(lhs && rhs);
88 assert(!Loc::isLocType(type));
89 return nonloc::SymbolVal(SymMgr.getSymSymExpr(lhs, op, rhs, type));
90 }
91
makeNonLoc(const SymExpr * operand,QualType fromTy,QualType toTy)92 NonLoc SValBuilder::makeNonLoc(const SymExpr *operand,
93 QualType fromTy, QualType toTy) {
94 assert(operand);
95 assert(!Loc::isLocType(toTy));
96 return nonloc::SymbolVal(SymMgr.getCastSymbol(operand, fromTy, toTy));
97 }
98
convertToArrayIndex(SVal val)99 SVal SValBuilder::convertToArrayIndex(SVal val) {
100 if (val.isUnknownOrUndef())
101 return val;
102
103 // Common case: we have an appropriately sized integer.
104 if (Optional<nonloc::ConcreteInt> CI = val.getAs<nonloc::ConcreteInt>()) {
105 const llvm::APSInt& I = CI->getValue();
106 if (I.getBitWidth() == ArrayIndexWidth && I.isSigned())
107 return val;
108 }
109
110 return evalCast(val, ArrayIndexTy, QualType{});
111 }
112
makeBoolVal(const CXXBoolLiteralExpr * boolean)113 nonloc::ConcreteInt SValBuilder::makeBoolVal(const CXXBoolLiteralExpr *boolean){
114 return makeTruthVal(boolean->getValue());
115 }
116
117 DefinedOrUnknownSVal
getRegionValueSymbolVal(const TypedValueRegion * region)118 SValBuilder::getRegionValueSymbolVal(const TypedValueRegion *region) {
119 QualType T = region->getValueType();
120
121 if (T->isNullPtrType())
122 return makeZeroVal(T);
123
124 if (!SymbolManager::canSymbolicate(T))
125 return UnknownVal();
126
127 SymbolRef sym = SymMgr.getRegionValueSymbol(region);
128
129 if (Loc::isLocType(T))
130 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
131
132 return nonloc::SymbolVal(sym);
133 }
134
conjureSymbolVal(const void * SymbolTag,const Expr * Ex,const LocationContext * LCtx,unsigned Count)135 DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *SymbolTag,
136 const Expr *Ex,
137 const LocationContext *LCtx,
138 unsigned Count) {
139 QualType T = Ex->getType();
140
141 if (T->isNullPtrType())
142 return makeZeroVal(T);
143
144 // Compute the type of the result. If the expression is not an R-value, the
145 // result should be a location.
146 QualType ExType = Ex->getType();
147 if (Ex->isGLValue())
148 T = LCtx->getAnalysisDeclContext()->getASTContext().getPointerType(ExType);
149
150 return conjureSymbolVal(SymbolTag, Ex, LCtx, T, Count);
151 }
152
conjureSymbolVal(const void * symbolTag,const Expr * expr,const LocationContext * LCtx,QualType type,unsigned count)153 DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *symbolTag,
154 const Expr *expr,
155 const LocationContext *LCtx,
156 QualType type,
157 unsigned count) {
158 if (type->isNullPtrType())
159 return makeZeroVal(type);
160
161 if (!SymbolManager::canSymbolicate(type))
162 return UnknownVal();
163
164 SymbolRef sym = SymMgr.conjureSymbol(expr, LCtx, type, count, symbolTag);
165
166 if (Loc::isLocType(type))
167 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
168
169 return nonloc::SymbolVal(sym);
170 }
171
conjureSymbolVal(const Stmt * stmt,const LocationContext * LCtx,QualType type,unsigned visitCount)172 DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const Stmt *stmt,
173 const LocationContext *LCtx,
174 QualType type,
175 unsigned visitCount) {
176 if (type->isNullPtrType())
177 return makeZeroVal(type);
178
179 if (!SymbolManager::canSymbolicate(type))
180 return UnknownVal();
181
182 SymbolRef sym = SymMgr.conjureSymbol(stmt, LCtx, type, visitCount);
183
184 if (Loc::isLocType(type))
185 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
186
187 return nonloc::SymbolVal(sym);
188 }
189
190 DefinedOrUnknownSVal
getConjuredHeapSymbolVal(const Expr * E,const LocationContext * LCtx,unsigned VisitCount)191 SValBuilder::getConjuredHeapSymbolVal(const Expr *E,
192 const LocationContext *LCtx,
193 unsigned VisitCount) {
194 QualType T = E->getType();
195 assert(Loc::isLocType(T));
196 assert(SymbolManager::canSymbolicate(T));
197 if (T->isNullPtrType())
198 return makeZeroVal(T);
199
200 SymbolRef sym = SymMgr.conjureSymbol(E, LCtx, T, VisitCount);
201 return loc::MemRegionVal(MemMgr.getSymbolicHeapRegion(sym));
202 }
203
getMetadataSymbolVal(const void * symbolTag,const MemRegion * region,const Expr * expr,QualType type,const LocationContext * LCtx,unsigned count)204 DefinedSVal SValBuilder::getMetadataSymbolVal(const void *symbolTag,
205 const MemRegion *region,
206 const Expr *expr, QualType type,
207 const LocationContext *LCtx,
208 unsigned count) {
209 assert(SymbolManager::canSymbolicate(type) && "Invalid metadata symbol type");
210
211 SymbolRef sym =
212 SymMgr.getMetadataSymbol(region, expr, type, LCtx, count, symbolTag);
213
214 if (Loc::isLocType(type))
215 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
216
217 return nonloc::SymbolVal(sym);
218 }
219
220 DefinedOrUnknownSVal
getDerivedRegionValueSymbolVal(SymbolRef parentSymbol,const TypedValueRegion * region)221 SValBuilder::getDerivedRegionValueSymbolVal(SymbolRef parentSymbol,
222 const TypedValueRegion *region) {
223 QualType T = region->getValueType();
224
225 if (T->isNullPtrType())
226 return makeZeroVal(T);
227
228 if (!SymbolManager::canSymbolicate(T))
229 return UnknownVal();
230
231 SymbolRef sym = SymMgr.getDerivedSymbol(parentSymbol, region);
232
233 if (Loc::isLocType(T))
234 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
235
236 return nonloc::SymbolVal(sym);
237 }
238
getMemberPointer(const NamedDecl * ND)239 DefinedSVal SValBuilder::getMemberPointer(const NamedDecl *ND) {
240 assert(!ND || isa<CXXMethodDecl>(ND) || isa<FieldDecl>(ND) ||
241 isa<IndirectFieldDecl>(ND));
242
243 if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(ND)) {
244 // Sema treats pointers to static member functions as have function pointer
245 // type, so return a function pointer for the method.
246 // We don't need to play a similar trick for static member fields
247 // because these are represented as plain VarDecls and not FieldDecls
248 // in the AST.
249 if (MD->isStatic())
250 return getFunctionPointer(MD);
251 }
252
253 return nonloc::PointerToMember(ND);
254 }
255
getFunctionPointer(const FunctionDecl * func)256 DefinedSVal SValBuilder::getFunctionPointer(const FunctionDecl *func) {
257 return loc::MemRegionVal(MemMgr.getFunctionCodeRegion(func));
258 }
259
getBlockPointer(const BlockDecl * block,CanQualType locTy,const LocationContext * locContext,unsigned blockCount)260 DefinedSVal SValBuilder::getBlockPointer(const BlockDecl *block,
261 CanQualType locTy,
262 const LocationContext *locContext,
263 unsigned blockCount) {
264 const BlockCodeRegion *BC =
265 MemMgr.getBlockCodeRegion(block, locTy, locContext->getAnalysisDeclContext());
266 const BlockDataRegion *BD = MemMgr.getBlockDataRegion(BC, locContext,
267 blockCount);
268 return loc::MemRegionVal(BD);
269 }
270
271 /// Return a memory region for the 'this' object reference.
getCXXThis(const CXXMethodDecl * D,const StackFrameContext * SFC)272 loc::MemRegionVal SValBuilder::getCXXThis(const CXXMethodDecl *D,
273 const StackFrameContext *SFC) {
274 return loc::MemRegionVal(
275 getRegionManager().getCXXThisRegion(D->getThisType(), SFC));
276 }
277
278 /// Return a memory region for the 'this' object reference.
getCXXThis(const CXXRecordDecl * D,const StackFrameContext * SFC)279 loc::MemRegionVal SValBuilder::getCXXThis(const CXXRecordDecl *D,
280 const StackFrameContext *SFC) {
281 const Type *T = D->getTypeForDecl();
282 QualType PT = getContext().getPointerType(QualType(T, 0));
283 return loc::MemRegionVal(getRegionManager().getCXXThisRegion(PT, SFC));
284 }
285
getConstantVal(const Expr * E)286 Optional<SVal> SValBuilder::getConstantVal(const Expr *E) {
287 E = E->IgnoreParens();
288
289 switch (E->getStmtClass()) {
290 // Handle expressions that we treat differently from the AST's constant
291 // evaluator.
292 case Stmt::AddrLabelExprClass:
293 return makeLoc(cast<AddrLabelExpr>(E));
294
295 case Stmt::CXXScalarValueInitExprClass:
296 case Stmt::ImplicitValueInitExprClass:
297 return makeZeroVal(E->getType());
298
299 case Stmt::ObjCStringLiteralClass: {
300 const auto *SL = cast<ObjCStringLiteral>(E);
301 return makeLoc(getRegionManager().getObjCStringRegion(SL));
302 }
303
304 case Stmt::StringLiteralClass: {
305 const auto *SL = cast<StringLiteral>(E);
306 return makeLoc(getRegionManager().getStringRegion(SL));
307 }
308
309 case Stmt::PredefinedExprClass: {
310 const auto *PE = cast<PredefinedExpr>(E);
311 assert(PE->getFunctionName() &&
312 "Since we analyze only instantiated functions, PredefinedExpr "
313 "should have a function name.");
314 return makeLoc(getRegionManager().getStringRegion(PE->getFunctionName()));
315 }
316
317 // Fast-path some expressions to avoid the overhead of going through the AST's
318 // constant evaluator
319 case Stmt::CharacterLiteralClass: {
320 const auto *C = cast<CharacterLiteral>(E);
321 return makeIntVal(C->getValue(), C->getType());
322 }
323
324 case Stmt::CXXBoolLiteralExprClass:
325 return makeBoolVal(cast<CXXBoolLiteralExpr>(E));
326
327 case Stmt::TypeTraitExprClass: {
328 const auto *TE = cast<TypeTraitExpr>(E);
329 return makeTruthVal(TE->getValue(), TE->getType());
330 }
331
332 case Stmt::IntegerLiteralClass:
333 return makeIntVal(cast<IntegerLiteral>(E));
334
335 case Stmt::ObjCBoolLiteralExprClass:
336 return makeBoolVal(cast<ObjCBoolLiteralExpr>(E));
337
338 case Stmt::CXXNullPtrLiteralExprClass:
339 return makeNull();
340
341 case Stmt::CStyleCastExprClass:
342 case Stmt::CXXFunctionalCastExprClass:
343 case Stmt::CXXConstCastExprClass:
344 case Stmt::CXXReinterpretCastExprClass:
345 case Stmt::CXXStaticCastExprClass:
346 case Stmt::ImplicitCastExprClass: {
347 const auto *CE = cast<CastExpr>(E);
348 switch (CE->getCastKind()) {
349 default:
350 break;
351 case CK_ArrayToPointerDecay:
352 case CK_IntegralToPointer:
353 case CK_NoOp:
354 case CK_BitCast: {
355 const Expr *SE = CE->getSubExpr();
356 Optional<SVal> Val = getConstantVal(SE);
357 if (!Val)
358 return None;
359 return evalCast(*Val, CE->getType(), SE->getType());
360 }
361 }
362 // FALLTHROUGH
363 LLVM_FALLTHROUGH;
364 }
365
366 // If we don't have a special case, fall back to the AST's constant evaluator.
367 default: {
368 // Don't try to come up with a value for materialized temporaries.
369 if (E->isGLValue())
370 return None;
371
372 ASTContext &Ctx = getContext();
373 Expr::EvalResult Result;
374 if (E->EvaluateAsInt(Result, Ctx))
375 return makeIntVal(Result.Val.getInt());
376
377 if (Loc::isLocType(E->getType()))
378 if (E->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNotNull))
379 return makeNull();
380
381 return None;
382 }
383 }
384 }
385
makeSymExprValNN(BinaryOperator::Opcode Op,NonLoc LHS,NonLoc RHS,QualType ResultTy)386 SVal SValBuilder::makeSymExprValNN(BinaryOperator::Opcode Op,
387 NonLoc LHS, NonLoc RHS,
388 QualType ResultTy) {
389 SymbolRef symLHS = LHS.getAsSymbol();
390 SymbolRef symRHS = RHS.getAsSymbol();
391
392 // TODO: When the Max Complexity is reached, we should conjure a symbol
393 // instead of generating an Unknown value and propagate the taint info to it.
394 const unsigned MaxComp = StateMgr.getOwningEngine()
395 .getAnalysisManager()
396 .options.MaxSymbolComplexity;
397
398 if (symLHS && symRHS &&
399 (symLHS->computeComplexity() + symRHS->computeComplexity()) < MaxComp)
400 return makeNonLoc(symLHS, Op, symRHS, ResultTy);
401
402 if (symLHS && symLHS->computeComplexity() < MaxComp)
403 if (Optional<nonloc::ConcreteInt> rInt = RHS.getAs<nonloc::ConcreteInt>())
404 return makeNonLoc(symLHS, Op, rInt->getValue(), ResultTy);
405
406 if (symRHS && symRHS->computeComplexity() < MaxComp)
407 if (Optional<nonloc::ConcreteInt> lInt = LHS.getAs<nonloc::ConcreteInt>())
408 return makeNonLoc(lInt->getValue(), Op, symRHS, ResultTy);
409
410 return UnknownVal();
411 }
412
evalBinOp(ProgramStateRef state,BinaryOperator::Opcode op,SVal lhs,SVal rhs,QualType type)413 SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
414 SVal lhs, SVal rhs, QualType type) {
415 if (lhs.isUndef() || rhs.isUndef())
416 return UndefinedVal();
417
418 if (lhs.isUnknown() || rhs.isUnknown())
419 return UnknownVal();
420
421 if (lhs.getAs<nonloc::LazyCompoundVal>() ||
422 rhs.getAs<nonloc::LazyCompoundVal>()) {
423 return UnknownVal();
424 }
425
426 if (op == BinaryOperatorKind::BO_Cmp) {
427 // We can't reason about C++20 spaceship operator yet.
428 //
429 // FIXME: Support C++20 spaceship operator.
430 // The main problem here is that the result is not integer.
431 return UnknownVal();
432 }
433
434 if (Optional<Loc> LV = lhs.getAs<Loc>()) {
435 if (Optional<Loc> RV = rhs.getAs<Loc>())
436 return evalBinOpLL(state, op, *LV, *RV, type);
437
438 return evalBinOpLN(state, op, *LV, rhs.castAs<NonLoc>(), type);
439 }
440
441 if (Optional<Loc> RV = rhs.getAs<Loc>()) {
442 // Support pointer arithmetic where the addend is on the left
443 // and the pointer on the right.
444 assert(op == BO_Add);
445
446 // Commute the operands.
447 return evalBinOpLN(state, op, *RV, lhs.castAs<NonLoc>(), type);
448 }
449
450 return evalBinOpNN(state, op, lhs.castAs<NonLoc>(), rhs.castAs<NonLoc>(),
451 type);
452 }
453
areEqual(ProgramStateRef state,SVal lhs,SVal rhs)454 ConditionTruthVal SValBuilder::areEqual(ProgramStateRef state, SVal lhs,
455 SVal rhs) {
456 return state->isNonNull(evalEQ(state, lhs, rhs));
457 }
458
evalEQ(ProgramStateRef state,SVal lhs,SVal rhs)459 SVal SValBuilder::evalEQ(ProgramStateRef state, SVal lhs, SVal rhs) {
460 return evalBinOp(state, BO_EQ, lhs, rhs, getConditionType());
461 }
462
evalEQ(ProgramStateRef state,DefinedOrUnknownSVal lhs,DefinedOrUnknownSVal rhs)463 DefinedOrUnknownSVal SValBuilder::evalEQ(ProgramStateRef state,
464 DefinedOrUnknownSVal lhs,
465 DefinedOrUnknownSVal rhs) {
466 return evalEQ(state, static_cast<SVal>(lhs), static_cast<SVal>(rhs))
467 .castAs<DefinedOrUnknownSVal>();
468 }
469
470 /// Recursively check if the pointer types are equal modulo const, volatile,
471 /// and restrict qualifiers. Also, assume that all types are similar to 'void'.
472 /// Assumes the input types are canonical.
shouldBeModeledWithNoOp(ASTContext & Context,QualType ToTy,QualType FromTy)473 static bool shouldBeModeledWithNoOp(ASTContext &Context, QualType ToTy,
474 QualType FromTy) {
475 while (Context.UnwrapSimilarTypes(ToTy, FromTy)) {
476 Qualifiers Quals1, Quals2;
477 ToTy = Context.getUnqualifiedArrayType(ToTy, Quals1);
478 FromTy = Context.getUnqualifiedArrayType(FromTy, Quals2);
479
480 // Make sure that non-cvr-qualifiers the other qualifiers (e.g., address
481 // spaces) are identical.
482 Quals1.removeCVRQualifiers();
483 Quals2.removeCVRQualifiers();
484 if (Quals1 != Quals2)
485 return false;
486 }
487
488 // If we are casting to void, the 'From' value can be used to represent the
489 // 'To' value.
490 //
491 // FIXME: Doing this after unwrapping the types doesn't make any sense. A
492 // cast from 'int**' to 'void**' is not special in the way that a cast from
493 // 'int*' to 'void*' is.
494 if (ToTy->isVoidType())
495 return true;
496
497 if (ToTy != FromTy)
498 return false;
499
500 return true;
501 }
502
503 // Handles casts of type CK_IntegralCast.
504 // At the moment, this function will redirect to evalCast, except when the range
505 // of the original value is known to be greater than the max of the target type.
evalIntegralCast(ProgramStateRef state,SVal val,QualType castTy,QualType originalTy)506 SVal SValBuilder::evalIntegralCast(ProgramStateRef state, SVal val,
507 QualType castTy, QualType originalTy) {
508 // No truncations if target type is big enough.
509 if (getContext().getTypeSize(castTy) >= getContext().getTypeSize(originalTy))
510 return evalCast(val, castTy, originalTy);
511
512 SymbolRef se = val.getAsSymbol();
513 if (!se) // Let evalCast handle non symbolic expressions.
514 return evalCast(val, castTy, originalTy);
515
516 // Find the maximum value of the target type.
517 APSIntType ToType(getContext().getTypeSize(castTy),
518 castTy->isUnsignedIntegerType());
519 llvm::APSInt ToTypeMax = ToType.getMaxValue();
520 NonLoc ToTypeMaxVal =
521 makeIntVal(ToTypeMax.isUnsigned() ? ToTypeMax.getZExtValue()
522 : ToTypeMax.getSExtValue(),
523 castTy)
524 .castAs<NonLoc>();
525 // Check the range of the symbol being casted against the maximum value of the
526 // target type.
527 NonLoc FromVal = val.castAs<NonLoc>();
528 QualType CmpTy = getConditionType();
529 NonLoc CompVal =
530 evalBinOpNN(state, BO_LE, FromVal, ToTypeMaxVal, CmpTy).castAs<NonLoc>();
531 ProgramStateRef IsNotTruncated, IsTruncated;
532 std::tie(IsNotTruncated, IsTruncated) = state->assume(CompVal);
533 if (!IsNotTruncated && IsTruncated) {
534 // Symbol is truncated so we evaluate it as a cast.
535 NonLoc CastVal = makeNonLoc(se, originalTy, castTy);
536 return CastVal;
537 }
538 return evalCast(val, castTy, originalTy);
539 }
540
541 //===----------------------------------------------------------------------===//
542 // Cast methods.
543 // `evalCast` is the main method
544 // `evalCastKind` and `evalCastSubKind` are helpers
545 //===----------------------------------------------------------------------===//
546
547 /// Cast a given SVal to another SVal using given QualType's.
548 /// \param V -- SVal that should be casted.
549 /// \param CastTy -- QualType that V should be casted according to.
550 /// \param OriginalTy -- QualType which is associated to V. It provides
551 /// additional information about what type the cast performs from.
552 /// \returns the most appropriate casted SVal.
553 /// Note: Many cases don't use an exact OriginalTy. It can be extracted
554 /// from SVal or the cast can performs unconditionaly. Always pass OriginalTy!
555 /// It can be crucial in certain cases and generates different results.
556 /// FIXME: If `OriginalTy.isNull()` is true, then cast performs based on CastTy
557 /// only. This behavior is uncertain and should be improved.
evalCast(SVal V,QualType CastTy,QualType OriginalTy)558 SVal SValBuilder::evalCast(SVal V, QualType CastTy, QualType OriginalTy) {
559 if (CastTy.isNull())
560 return V;
561
562 CastTy = Context.getCanonicalType(CastTy);
563
564 const bool IsUnknownOriginalType = OriginalTy.isNull();
565 if (!IsUnknownOriginalType) {
566 OriginalTy = Context.getCanonicalType(OriginalTy);
567
568 if (CastTy == OriginalTy)
569 return V;
570
571 // FIXME: Move this check to the most appropriate
572 // evalCastKind/evalCastSubKind function. For const casts, casts to void,
573 // just propagate the value.
574 if (!CastTy->isVariableArrayType() && !OriginalTy->isVariableArrayType())
575 if (shouldBeModeledWithNoOp(Context, Context.getPointerType(CastTy),
576 Context.getPointerType(OriginalTy)))
577 return V;
578 }
579
580 // Cast SVal according to kinds.
581 switch (V.getBaseKind()) {
582 case SVal::UndefinedValKind:
583 return evalCastKind(V.castAs<UndefinedVal>(), CastTy, OriginalTy);
584 case SVal::UnknownValKind:
585 return evalCastKind(V.castAs<UnknownVal>(), CastTy, OriginalTy);
586 case SVal::LocKind:
587 return evalCastKind(V.castAs<Loc>(), CastTy, OriginalTy);
588 case SVal::NonLocKind:
589 return evalCastKind(V.castAs<NonLoc>(), CastTy, OriginalTy);
590 }
591
592 llvm_unreachable("Unknown SVal kind");
593 }
594
evalCastKind(UndefinedVal V,QualType CastTy,QualType OriginalTy)595 SVal SValBuilder::evalCastKind(UndefinedVal V, QualType CastTy,
596 QualType OriginalTy) {
597 return V;
598 }
599
evalCastKind(UnknownVal V,QualType CastTy,QualType OriginalTy)600 SVal SValBuilder::evalCastKind(UnknownVal V, QualType CastTy,
601 QualType OriginalTy) {
602 return V;
603 }
604
evalCastKind(Loc V,QualType CastTy,QualType OriginalTy)605 SVal SValBuilder::evalCastKind(Loc V, QualType CastTy, QualType OriginalTy) {
606 switch (V.getSubKind()) {
607 case loc::ConcreteIntKind:
608 return evalCastSubKind(V.castAs<loc::ConcreteInt>(), CastTy, OriginalTy);
609 case loc::GotoLabelKind:
610 return evalCastSubKind(V.castAs<loc::GotoLabel>(), CastTy, OriginalTy);
611 case loc::MemRegionValKind:
612 return evalCastSubKind(V.castAs<loc::MemRegionVal>(), CastTy, OriginalTy);
613 }
614
615 llvm_unreachable("Unknown SVal kind");
616 }
617
evalCastKind(NonLoc V,QualType CastTy,QualType OriginalTy)618 SVal SValBuilder::evalCastKind(NonLoc V, QualType CastTy, QualType OriginalTy) {
619 switch (V.getSubKind()) {
620 case nonloc::CompoundValKind:
621 return evalCastSubKind(V.castAs<nonloc::CompoundVal>(), CastTy, OriginalTy);
622 case nonloc::ConcreteIntKind:
623 return evalCastSubKind(V.castAs<nonloc::ConcreteInt>(), CastTy, OriginalTy);
624 case nonloc::LazyCompoundValKind:
625 return evalCastSubKind(V.castAs<nonloc::LazyCompoundVal>(), CastTy,
626 OriginalTy);
627 case nonloc::LocAsIntegerKind:
628 return evalCastSubKind(V.castAs<nonloc::LocAsInteger>(), CastTy,
629 OriginalTy);
630 case nonloc::SymbolValKind:
631 return evalCastSubKind(V.castAs<nonloc::SymbolVal>(), CastTy, OriginalTy);
632 case nonloc::PointerToMemberKind:
633 return evalCastSubKind(V.castAs<nonloc::PointerToMember>(), CastTy,
634 OriginalTy);
635 }
636
637 llvm_unreachable("Unknown SVal kind");
638 }
639
evalCastSubKind(loc::ConcreteInt V,QualType CastTy,QualType OriginalTy)640 SVal SValBuilder::evalCastSubKind(loc::ConcreteInt V, QualType CastTy,
641 QualType OriginalTy) {
642 // Pointer to bool.
643 if (CastTy->isBooleanType())
644 return makeTruthVal(V.getValue().getBoolValue(), CastTy);
645
646 // Pointer to integer.
647 if (CastTy->isIntegralOrEnumerationType()) {
648 llvm::APSInt Value = V.getValue();
649 BasicVals.getAPSIntType(CastTy).apply(Value);
650 return makeIntVal(Value);
651 }
652
653 // Pointer to any pointer.
654 if (Loc::isLocType(CastTy))
655 return V;
656
657 // Pointer to whatever else.
658 return UnknownVal();
659 }
660
evalCastSubKind(loc::GotoLabel V,QualType CastTy,QualType OriginalTy)661 SVal SValBuilder::evalCastSubKind(loc::GotoLabel V, QualType CastTy,
662 QualType OriginalTy) {
663 // Pointer to bool.
664 if (CastTy->isBooleanType())
665 // Labels are always true.
666 return makeTruthVal(true, CastTy);
667
668 // Pointer to integer.
669 if (CastTy->isIntegralOrEnumerationType()) {
670 const unsigned BitWidth = Context.getIntWidth(CastTy);
671 return makeLocAsInteger(V, BitWidth);
672 }
673
674 const bool IsUnknownOriginalType = OriginalTy.isNull();
675 if (!IsUnknownOriginalType) {
676 // Array to pointer.
677 if (isa<ArrayType>(OriginalTy))
678 if (CastTy->isPointerType() || CastTy->isReferenceType())
679 return UnknownVal();
680 }
681
682 // Pointer to any pointer.
683 if (Loc::isLocType(CastTy))
684 return V;
685
686 // Pointer to whatever else.
687 return UnknownVal();
688 }
689
hasSameUnqualifiedPointeeType(QualType ty1,QualType ty2)690 static bool hasSameUnqualifiedPointeeType(QualType ty1, QualType ty2) {
691 return ty1->getPointeeType().getCanonicalType().getTypePtr() ==
692 ty2->getPointeeType().getCanonicalType().getTypePtr();
693 }
694
evalCastSubKind(loc::MemRegionVal V,QualType CastTy,QualType OriginalTy)695 SVal SValBuilder::evalCastSubKind(loc::MemRegionVal V, QualType CastTy,
696 QualType OriginalTy) {
697 // Pointer to bool.
698 if (CastTy->isBooleanType()) {
699 const MemRegion *R = V.getRegion();
700 if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(R))
701 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl()))
702 if (FD->isWeak())
703 // FIXME: Currently we are using an extent symbol here,
704 // because there are no generic region address metadata
705 // symbols to use, only content metadata.
706 return nonloc::SymbolVal(SymMgr.getExtentSymbol(FTR));
707
708 if (const SymbolicRegion *SymR = R->getSymbolicBase())
709 return makeNonLoc(SymR->getSymbol(), BO_NE,
710 BasicVals.getZeroWithPtrWidth(), CastTy);
711 // Non-symbolic memory regions are always true.
712 return makeTruthVal(true, CastTy);
713 }
714
715 const bool IsUnknownOriginalType = OriginalTy.isNull();
716 // Try to cast to array
717 const auto *ArrayTy =
718 IsUnknownOriginalType
719 ? nullptr
720 : dyn_cast<ArrayType>(OriginalTy.getCanonicalType());
721
722 // Pointer to integer.
723 if (CastTy->isIntegralOrEnumerationType()) {
724 SVal Val = V;
725 // Array to integer.
726 if (ArrayTy) {
727 // We will always decay to a pointer.
728 QualType ElemTy = ArrayTy->getElementType();
729 Val = StateMgr.ArrayToPointer(V, ElemTy);
730 // FIXME: Keep these here for now in case we decide soon that we
731 // need the original decayed type.
732 // QualType elemTy = cast<ArrayType>(originalTy)->getElementType();
733 // QualType pointerTy = C.getPointerType(elemTy);
734 }
735 const unsigned BitWidth = Context.getIntWidth(CastTy);
736 return makeLocAsInteger(Val.castAs<Loc>(), BitWidth);
737 }
738
739 // Pointer to pointer.
740 if (Loc::isLocType(CastTy)) {
741
742 if (IsUnknownOriginalType) {
743 // When retrieving symbolic pointer and expecting a non-void pointer,
744 // wrap them into element regions of the expected type if necessary.
745 // It is necessary to make sure that the retrieved value makes sense,
746 // because there's no other cast in the AST that would tell us to cast
747 // it to the correct pointer type. We might need to do that for non-void
748 // pointers as well.
749 // FIXME: We really need a single good function to perform casts for us
750 // correctly every time we need it.
751 const MemRegion *R = V.getRegion();
752 if (CastTy->isPointerType() && !CastTy->isVoidPointerType()) {
753 if (const auto *SR = dyn_cast<SymbolicRegion>(R)) {
754 QualType SRTy = SR->getSymbol()->getType();
755 if (!hasSameUnqualifiedPointeeType(SRTy, CastTy)) {
756 R = StateMgr.getStoreManager().castRegion(SR, CastTy);
757 return loc::MemRegionVal(R);
758 }
759 }
760 }
761 // Next fixes pointer dereference using type different from its initial
762 // one. See PR37503 and PR49007 for details.
763 if (const auto *ER = dyn_cast<ElementRegion>(R)) {
764 if ((R = StateMgr.getStoreManager().castRegion(ER, CastTy)))
765 return loc::MemRegionVal(R);
766 }
767
768 return V;
769 }
770
771 if (OriginalTy->isIntegralOrEnumerationType() ||
772 OriginalTy->isBlockPointerType() || OriginalTy->isFunctionPointerType())
773 return V;
774
775 // Array to pointer.
776 if (ArrayTy) {
777 // Are we casting from an array to a pointer? If so just pass on
778 // the decayed value.
779 if (CastTy->isPointerType() || CastTy->isReferenceType()) {
780 // We will always decay to a pointer.
781 QualType ElemTy = ArrayTy->getElementType();
782 return StateMgr.ArrayToPointer(V, ElemTy);
783 }
784 // Are we casting from an array to an integer? If so, cast the decayed
785 // pointer value to an integer.
786 assert(CastTy->isIntegralOrEnumerationType());
787 }
788
789 // Other pointer to pointer.
790 assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() ||
791 CastTy->isReferenceType());
792
793 // We get a symbolic function pointer for a dereference of a function
794 // pointer, but it is of function type. Example:
795
796 // struct FPRec {
797 // void (*my_func)(int * x);
798 // };
799 //
800 // int bar(int x);
801 //
802 // int f1_a(struct FPRec* foo) {
803 // int x;
804 // (*foo->my_func)(&x);
805 // return bar(x)+1; // no-warning
806 // }
807
808 // Get the result of casting a region to a different type.
809 const MemRegion *R = V.getRegion();
810 if ((R = StateMgr.getStoreManager().castRegion(R, CastTy)))
811 return loc::MemRegionVal(R);
812 }
813
814 // Pointer to whatever else.
815 // FIXME: There can be gross cases where one casts the result of a
816 // function (that returns a pointer) to some other value that happens to
817 // fit within that pointer value. We currently have no good way to model
818 // such operations. When this happens, the underlying operation is that
819 // the caller is reasoning about bits. Conceptually we are layering a
820 // "view" of a location on top of those bits. Perhaps we need to be more
821 // lazy about mutual possible views, even on an SVal? This may be
822 // necessary for bit-level reasoning as well.
823 return UnknownVal();
824 }
825
evalCastSubKind(nonloc::CompoundVal V,QualType CastTy,QualType OriginalTy)826 SVal SValBuilder::evalCastSubKind(nonloc::CompoundVal V, QualType CastTy,
827 QualType OriginalTy) {
828 // Compound to whatever.
829 return UnknownVal();
830 }
831
evalCastSubKind(nonloc::ConcreteInt V,QualType CastTy,QualType OriginalTy)832 SVal SValBuilder::evalCastSubKind(nonloc::ConcreteInt V, QualType CastTy,
833 QualType OriginalTy) {
834 auto CastedValue = [V, CastTy, this]() {
835 llvm::APSInt Value = V.getValue();
836 BasicVals.getAPSIntType(CastTy).apply(Value);
837 return Value;
838 };
839
840 // Integer to bool.
841 if (CastTy->isBooleanType())
842 return makeTruthVal(V.getValue().getBoolValue(), CastTy);
843
844 // Integer to pointer.
845 if (CastTy->isIntegralOrEnumerationType())
846 return makeIntVal(CastedValue());
847
848 // Integer to pointer.
849 if (Loc::isLocType(CastTy))
850 return makeIntLocVal(CastedValue());
851
852 // Pointer to whatever else.
853 return UnknownVal();
854 }
855
evalCastSubKind(nonloc::LazyCompoundVal V,QualType CastTy,QualType OriginalTy)856 SVal SValBuilder::evalCastSubKind(nonloc::LazyCompoundVal V, QualType CastTy,
857 QualType OriginalTy) {
858 // Compound to whatever.
859 return UnknownVal();
860 }
861
evalCastSubKind(nonloc::LocAsInteger V,QualType CastTy,QualType OriginalTy)862 SVal SValBuilder::evalCastSubKind(nonloc::LocAsInteger V, QualType CastTy,
863 QualType OriginalTy) {
864 Loc L = V.getLoc();
865
866 // Pointer as integer to bool.
867 if (CastTy->isBooleanType())
868 // Pass to Loc function.
869 return evalCastKind(L, CastTy, OriginalTy);
870
871 const bool IsUnknownOriginalType = OriginalTy.isNull();
872 // Pointer as integer to pointer.
873 if (!IsUnknownOriginalType && Loc::isLocType(CastTy) &&
874 OriginalTy->isIntegralOrEnumerationType()) {
875 if (const MemRegion *R = L.getAsRegion())
876 if ((R = StateMgr.getStoreManager().castRegion(R, CastTy)))
877 return loc::MemRegionVal(R);
878 return L;
879 }
880
881 // Pointer as integer with region to integer/pointer.
882 const MemRegion *R = L.getAsRegion();
883 if (!IsUnknownOriginalType && R) {
884 if (CastTy->isIntegralOrEnumerationType())
885 return evalCastSubKind(loc::MemRegionVal(R), CastTy, OriginalTy);
886
887 if (Loc::isLocType(CastTy)) {
888 assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() ||
889 CastTy->isReferenceType());
890 // Delegate to store manager to get the result of casting a region to a
891 // different type. If the MemRegion* returned is NULL, this expression
892 // Evaluates to UnknownVal.
893 if ((R = StateMgr.getStoreManager().castRegion(R, CastTy)))
894 return loc::MemRegionVal(R);
895 }
896 } else {
897 if (Loc::isLocType(CastTy)) {
898 if (IsUnknownOriginalType)
899 return evalCastSubKind(loc::MemRegionVal(R), CastTy, OriginalTy);
900 return L;
901 }
902
903 SymbolRef SE = nullptr;
904 if (R) {
905 if (const SymbolicRegion *SR =
906 dyn_cast<SymbolicRegion>(R->StripCasts())) {
907 SE = SR->getSymbol();
908 }
909 }
910
911 if (!CastTy->isFloatingType() || !SE || SE->getType()->isFloatingType()) {
912 // FIXME: Correctly support promotions/truncations.
913 const unsigned CastSize = Context.getIntWidth(CastTy);
914 if (CastSize == V.getNumBits())
915 return V;
916
917 return makeLocAsInteger(L, CastSize);
918 }
919 }
920
921 // Pointer as integer to whatever else.
922 return UnknownVal();
923 }
924
evalCastSubKind(nonloc::SymbolVal V,QualType CastTy,QualType OriginalTy)925 SVal SValBuilder::evalCastSubKind(nonloc::SymbolVal V, QualType CastTy,
926 QualType OriginalTy) {
927 SymbolRef SE = V.getSymbol();
928
929 const bool IsUnknownOriginalType = OriginalTy.isNull();
930 // Symbol to bool.
931 if (!IsUnknownOriginalType && CastTy->isBooleanType()) {
932 // Non-float to bool.
933 if (Loc::isLocType(OriginalTy) ||
934 OriginalTy->isIntegralOrEnumerationType() ||
935 OriginalTy->isMemberPointerType()) {
936 BasicValueFactory &BVF = getBasicValueFactory();
937 return makeNonLoc(SE, BO_NE, BVF.getValue(0, SE->getType()), CastTy);
938 }
939 } else {
940 // Symbol to integer, float.
941 QualType T = Context.getCanonicalType(SE->getType());
942 // If types are the same or both are integers, ignore the cast.
943 // FIXME: Remove this hack when we support symbolic truncation/extension.
944 // HACK: If both castTy and T are integers, ignore the cast. This is
945 // not a permanent solution. Eventually we want to precisely handle
946 // extension/truncation of symbolic integers. This prevents us from losing
947 // precision when we assign 'x = y' and 'y' is symbolic and x and y are
948 // different integer types.
949 if (haveSameType(T, CastTy))
950 return V;
951 if (!Loc::isLocType(CastTy))
952 if (!IsUnknownOriginalType || !CastTy->isFloatingType() ||
953 T->isFloatingType())
954 return makeNonLoc(SE, T, CastTy);
955 }
956
957 // Symbol to pointer and whatever else.
958 return UnknownVal();
959 }
960
evalCastSubKind(nonloc::PointerToMember V,QualType CastTy,QualType OriginalTy)961 SVal SValBuilder::evalCastSubKind(nonloc::PointerToMember V, QualType CastTy,
962 QualType OriginalTy) {
963 // Member pointer to whatever.
964 return V;
965 }
966