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