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/Analysis/AnalysisDeclContext.h"
23#include "clang/Basic/LLVM.h"
24#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
25#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
26#include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
27#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
28#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
29#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
30#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
31#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
32#include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
33#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
34#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
35#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
36#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
37#include "llvm/ADT/APSInt.h"
38#include "llvm/Support/Compiler.h"
39#include <cassert>
40#include <optional>
41#include <tuple>
42
43using namespace clang;
44using namespace ento;
45
46//===----------------------------------------------------------------------===//
47// Basic SVal creation.
48//===----------------------------------------------------------------------===//
49
50void SValBuilder::anchor() {}
51
52SValBuilder::SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
53 ProgramStateManager &stateMgr)
54 : Context(context), BasicVals(context, alloc),
55 SymMgr(context, BasicVals, alloc), MemMgr(context, alloc),
56 StateMgr(stateMgr),
57 AnOpts(
58 stateMgr.getOwningEngine().getAnalysisManager().getAnalyzerOptions()),
59 ArrayIndexTy(context.LongLongTy),
60 ArrayIndexWidth(context.getTypeSize(T: ArrayIndexTy)) {}
61
62DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType type) {
63 if (Loc::isLocType(T: type))
64 return makeNullWithType(type);
65
66 if (type->isIntegralOrEnumerationType())
67 return makeIntVal(integer: 0, type);
68
69 if (type->isArrayType() || type->isRecordType() || type->isVectorType() ||
70 type->isAnyComplexType())
71 return makeCompoundVal(type, vals: BasicVals.getEmptySValList());
72
73 // FIXME: Handle floats.
74 return UnknownVal();
75}
76
77nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *lhs,
78 BinaryOperator::Opcode op,
79 APSIntPtr rhs, QualType type) {
80 assert(lhs);
81 assert(!Loc::isLocType(type));
82 return nonloc::SymbolVal(SymMgr.acquire<SymIntExpr>(args&: lhs, args&: op, args&: rhs, args&: type));
83}
84
85nonloc::SymbolVal SValBuilder::makeNonLoc(APSIntPtr lhs,
86 BinaryOperator::Opcode op,
87 const SymExpr *rhs, QualType type) {
88 assert(rhs);
89 assert(!Loc::isLocType(type));
90 return nonloc::SymbolVal(SymMgr.acquire<IntSymExpr>(args&: lhs, args&: op, args&: rhs, args&: type));
91}
92
93nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *lhs,
94 BinaryOperator::Opcode op,
95 const SymExpr *rhs, QualType type) {
96 assert(lhs && rhs);
97 assert(!Loc::isLocType(type));
98 return nonloc::SymbolVal(SymMgr.acquire<SymSymExpr>(args&: lhs, args&: op, args&: rhs, args&: type));
99}
100
101NonLoc SValBuilder::makeNonLoc(const SymExpr *operand, UnaryOperator::Opcode op,
102 QualType type) {
103 assert(operand);
104 assert(!Loc::isLocType(type));
105 return nonloc::SymbolVal(SymMgr.acquire<UnarySymExpr>(args&: operand, args&: op, args&: type));
106}
107
108nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *operand,
109 QualType fromTy, QualType toTy) {
110 assert(operand);
111 assert(!Loc::isLocType(toTy));
112 if (fromTy == toTy)
113 return nonloc::SymbolVal(operand);
114 return nonloc::SymbolVal(SymMgr.acquire<SymbolCast>(args&: operand, args&: fromTy, args&: toTy));
115}
116
117SVal SValBuilder::convertToArrayIndex(SVal val) {
118 if (val.isUnknownOrUndef())
119 return val;
120
121 // Common case: we have an appropriately sized integer.
122 if (std::optional<nonloc::ConcreteInt> CI =
123 val.getAs<nonloc::ConcreteInt>()) {
124 const llvm::APSInt& I = CI->getValue();
125 if (I.getBitWidth() == ArrayIndexWidth && I.isSigned())
126 return val;
127 }
128
129 return evalCast(V: val, CastTy: ArrayIndexTy, OriginalTy: QualType{});
130}
131
132nonloc::ConcreteInt SValBuilder::makeBoolVal(const CXXBoolLiteralExpr *boolean){
133 return makeTruthVal(b: boolean->getValue());
134}
135
136DefinedOrUnknownSVal
137SValBuilder::getRegionValueSymbolVal(const TypedValueRegion *region) {
138 QualType T = region->getValueType();
139
140 if (T->isNullPtrType())
141 return makeZeroVal(type: T);
142
143 if (!SymbolManager::canSymbolicate(T))
144 return UnknownVal();
145
146 SymbolRef sym = SymMgr.acquire<SymbolRegionValue>(args&: region);
147
148 if (Loc::isLocType(T))
149 return loc::MemRegionVal(MemMgr.getSymbolicRegion(Sym: sym));
150
151 return nonloc::SymbolVal(sym);
152}
153
154DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *SymbolTag,
155 ConstCFGElementRef elem,
156 const LocationContext *LCtx,
157 unsigned Count) {
158 const Expr *Ex = dyn_cast<Expr>(Val: elem->getAs<CFGStmt>()->getStmt());
159 assert(Ex && "elem must be a CFGStmt containing an Expr");
160 QualType T = Ex->getType();
161
162 if (T->isNullPtrType())
163 return makeZeroVal(type: T);
164
165 // Compute the type of the result. If the expression is not an R-value, the
166 // result should be a location.
167 QualType ExType = Ex->getType();
168 if (Ex->isGLValue())
169 T = LCtx->getAnalysisDeclContext()->getASTContext().getPointerType(T: ExType);
170
171 return conjureSymbolVal(symbolTag: SymbolTag, elem, LCtx, type: T, count: Count);
172}
173
174DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *symbolTag,
175 ConstCFGElementRef elem,
176 const LocationContext *LCtx,
177 QualType type,
178 unsigned count) {
179 if (type->isNullPtrType())
180 return makeZeroVal(type);
181
182 if (!SymbolManager::canSymbolicate(T: type))
183 return UnknownVal();
184
185 SymbolRef sym = SymMgr.conjureSymbol(Elem: elem, LCtx, T: type, VisitCount: count, SymbolTag: symbolTag);
186
187 if (Loc::isLocType(T: type))
188 return loc::MemRegionVal(MemMgr.getSymbolicRegion(Sym: sym));
189
190 return nonloc::SymbolVal(sym);
191}
192
193DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(ConstCFGElementRef elem,
194 const LocationContext *LCtx,
195 QualType type,
196 unsigned visitCount) {
197 return conjureSymbolVal(/*symbolTag=*/nullptr, elem, LCtx, type, count: visitCount);
198}
199
200DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const CallEvent &call,
201 unsigned visitCount,
202 const void *symbolTag) {
203 return conjureSymbolVal(symbolTag, elem: call.getCFGElementRef(),
204 LCtx: call.getLocationContext(), type: call.getResultType(),
205 count: visitCount);
206}
207
208DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const CallEvent &call,
209 QualType type,
210 unsigned visitCount,
211 const void *symbolTag) {
212 return conjureSymbolVal(symbolTag, elem: call.getCFGElementRef(),
213 LCtx: call.getLocationContext(), type, count: visitCount);
214}
215
216DefinedSVal SValBuilder::getConjuredHeapSymbolVal(ConstCFGElementRef elem,
217 const LocationContext *LCtx,
218 QualType type,
219 unsigned VisitCount) {
220 assert(Loc::isLocType(type));
221 assert(SymbolManager::canSymbolicate(type));
222 if (type->isNullPtrType()) {
223 // makeZeroVal() returns UnknownVal only in case of FP number, which
224 // is not the case.
225 return makeZeroVal(type).castAs<DefinedSVal>();
226 }
227
228 SymbolRef sym = SymMgr.conjureSymbol(Elem: elem, LCtx, T: type, VisitCount);
229 return loc::MemRegionVal(MemMgr.getSymbolicHeapRegion(sym));
230}
231
232loc::MemRegionVal SValBuilder::getAllocaRegionVal(const Expr *E,
233 const LocationContext *LCtx,
234 unsigned VisitCount) {
235 const AllocaRegion *R =
236 getRegionManager().getAllocaRegion(Ex: E, Cnt: VisitCount, LC: LCtx);
237 return loc::MemRegionVal(R);
238}
239
240DefinedSVal SValBuilder::getMetadataSymbolVal(const void *symbolTag,
241 const MemRegion *region,
242 const Expr *expr, QualType type,
243 const LocationContext *LCtx,
244 unsigned count) {
245 assert(SymbolManager::canSymbolicate(type) && "Invalid metadata symbol type");
246
247 SymbolRef sym = SymMgr.acquire<SymbolMetadata>(args&: region, args&: expr, args&: type, args&: LCtx,
248 args&: count, args&: symbolTag);
249
250 if (Loc::isLocType(T: type))
251 return loc::MemRegionVal(MemMgr.getSymbolicRegion(Sym: sym));
252
253 return nonloc::SymbolVal(sym);
254}
255
256DefinedOrUnknownSVal
257SValBuilder::getDerivedRegionValueSymbolVal(SymbolRef parentSymbol,
258 const TypedValueRegion *region) {
259 QualType T = region->getValueType();
260
261 if (T->isNullPtrType())
262 return makeZeroVal(type: T);
263
264 if (!SymbolManager::canSymbolicate(T))
265 return UnknownVal();
266
267 SymbolRef sym = SymMgr.acquire<SymbolDerived>(args&: parentSymbol, args&: region);
268
269 if (Loc::isLocType(T))
270 return loc::MemRegionVal(MemMgr.getSymbolicRegion(Sym: sym));
271
272 return nonloc::SymbolVal(sym);
273}
274
275DefinedSVal SValBuilder::getMemberPointer(const NamedDecl *ND) {
276 assert(!ND || (isa<CXXMethodDecl, FieldDecl, IndirectFieldDecl>(ND)));
277
278 if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(Val: ND)) {
279 // Sema treats pointers to static member functions as have function pointer
280 // type, so return a function pointer for the method.
281 // We don't need to play a similar trick for static member fields
282 // because these are represented as plain VarDecls and not FieldDecls
283 // in the AST.
284 if (!MD->isImplicitObjectMemberFunction())
285 return getFunctionPointer(func: MD);
286 }
287
288 return nonloc::PointerToMember(ND);
289}
290
291DefinedSVal SValBuilder::getFunctionPointer(const FunctionDecl *func) {
292 return loc::MemRegionVal(MemMgr.getFunctionCodeRegion(FD: func));
293}
294
295DefinedSVal SValBuilder::getBlockPointer(const BlockDecl *block,
296 CanQualType locTy,
297 const LocationContext *locContext,
298 unsigned blockCount) {
299 const BlockCodeRegion *BC =
300 MemMgr.getBlockCodeRegion(BD: block, locTy, AC: locContext->getAnalysisDeclContext());
301 const BlockDataRegion *BD = MemMgr.getBlockDataRegion(bc: BC, lc: locContext,
302 blockCount);
303 return loc::MemRegionVal(BD);
304}
305
306std::optional<loc::MemRegionVal>
307SValBuilder::getCastedMemRegionVal(const MemRegion *R, QualType Ty) {
308 if (auto OptR = StateMgr.getStoreManager().castRegion(region: R, CastToTy: Ty))
309 return loc::MemRegionVal(*OptR);
310 return std::nullopt;
311}
312
313/// Return a memory region for the 'this' object reference.
314loc::MemRegionVal SValBuilder::getCXXThis(const CXXMethodDecl *D,
315 const StackFrameContext *SFC) {
316 return loc::MemRegionVal(
317 getRegionManager().getCXXThisRegion(thisPointerTy: D->getThisType(), LC: SFC));
318}
319
320/// Return a memory region for the 'this' object reference.
321loc::MemRegionVal SValBuilder::getCXXThis(const CXXRecordDecl *D,
322 const StackFrameContext *SFC) {
323 const Type *T = D->getTypeForDecl();
324 QualType PT = getContext().getPointerType(T: QualType(T, 0));
325 return loc::MemRegionVal(getRegionManager().getCXXThisRegion(thisPointerTy: PT, LC: SFC));
326}
327
328std::optional<SVal> SValBuilder::getConstantVal(const Expr *E) {
329 E = E->IgnoreParens();
330
331 switch (E->getStmtClass()) {
332 // Handle expressions that we treat differently from the AST's constant
333 // evaluator.
334 case Stmt::AddrLabelExprClass:
335 return makeLoc(expr: cast<AddrLabelExpr>(Val: E));
336
337 case Stmt::CXXScalarValueInitExprClass:
338 case Stmt::ImplicitValueInitExprClass:
339 return makeZeroVal(type: E->getType());
340
341 case Stmt::ObjCStringLiteralClass: {
342 const auto *SL = cast<ObjCStringLiteral>(Val: E);
343 return makeLoc(region: getRegionManager().getObjCStringRegion(Str: SL));
344 }
345
346 case Stmt::StringLiteralClass: {
347 const auto *SL = cast<StringLiteral>(Val: E);
348 return makeLoc(region: getRegionManager().getStringRegion(Str: SL));
349 }
350
351 case Stmt::PredefinedExprClass: {
352 const auto *PE = cast<PredefinedExpr>(Val: E);
353 assert(PE->getFunctionName() &&
354 "Since we analyze only instantiated functions, PredefinedExpr "
355 "should have a function name.");
356 return makeLoc(region: getRegionManager().getStringRegion(Str: PE->getFunctionName()));
357 }
358
359 // Fast-path some expressions to avoid the overhead of going through the AST's
360 // constant evaluator
361 case Stmt::CharacterLiteralClass: {
362 const auto *C = cast<CharacterLiteral>(Val: E);
363 return makeIntVal(integer: C->getValue(), type: C->getType());
364 }
365
366 case Stmt::CXXBoolLiteralExprClass:
367 return makeBoolVal(boolean: cast<CXXBoolLiteralExpr>(Val: E));
368
369 case Stmt::TypeTraitExprClass: {
370 const auto *TE = cast<TypeTraitExpr>(Val: E);
371 if (TE->isStoredAsBoolean())
372 return makeTruthVal(b: TE->getBoolValue(), type: TE->getType());
373 assert(TE->getAPValue().isInt() && "APValue type not supported");
374 return makeIntVal(integer: TE->getAPValue().getInt());
375 }
376
377 case Stmt::IntegerLiteralClass:
378 return makeIntVal(integer: cast<IntegerLiteral>(Val: E));
379
380 case Stmt::ObjCBoolLiteralExprClass:
381 return makeBoolVal(boolean: cast<ObjCBoolLiteralExpr>(Val: E));
382
383 case Stmt::CXXNullPtrLiteralExprClass:
384 return makeNullWithType(type: E->getType());
385
386 case Stmt::CStyleCastExprClass:
387 case Stmt::CXXFunctionalCastExprClass:
388 case Stmt::CXXConstCastExprClass:
389 case Stmt::CXXReinterpretCastExprClass:
390 case Stmt::CXXStaticCastExprClass:
391 case Stmt::ImplicitCastExprClass: {
392 const auto *CE = cast<CastExpr>(Val: E);
393 switch (CE->getCastKind()) {
394 default:
395 break;
396 case CK_ArrayToPointerDecay:
397 case CK_IntegralToPointer:
398 case CK_NoOp:
399 case CK_BitCast: {
400 const Expr *SE = CE->getSubExpr();
401 std::optional<SVal> Val = getConstantVal(E: SE);
402 if (!Val)
403 return std::nullopt;
404 return evalCast(V: *Val, CastTy: CE->getType(), OriginalTy: SE->getType());
405 }
406 }
407 [[fallthrough]];
408 }
409
410 // If we don't have a special case, fall back to the AST's constant evaluator.
411 default: {
412 // Don't try to come up with a value for materialized temporaries.
413 if (E->isGLValue())
414 return std::nullopt;
415
416 ASTContext &Ctx = getContext();
417 Expr::EvalResult Result;
418 if (E->EvaluateAsInt(Result, Ctx))
419 return makeIntVal(integer: Result.Val.getInt());
420
421 if (Loc::isLocType(T: E->getType()))
422 if (E->isNullPointerConstant(Ctx, NPC: Expr::NPC_ValueDependentIsNotNull))
423 return makeNullWithType(type: E->getType());
424
425 return std::nullopt;
426 }
427 }
428}
429
430SVal SValBuilder::makeSymExprValNN(BinaryOperator::Opcode Op,
431 NonLoc LHS, NonLoc RHS,
432 QualType ResultTy) {
433 SymbolRef symLHS = LHS.getAsSymbol();
434 SymbolRef symRHS = RHS.getAsSymbol();
435
436 // TODO: When the Max Complexity is reached, we should conjure a symbol
437 // instead of generating an Unknown value and propagate the taint info to it.
438 const unsigned MaxComp = AnOpts.MaxSymbolComplexity;
439
440 if (symLHS && symRHS &&
441 (symLHS->computeComplexity() + symRHS->computeComplexity()) < MaxComp)
442 return makeNonLoc(lhs: symLHS, op: Op, rhs: symRHS, type: ResultTy);
443
444 if (symLHS && symLHS->computeComplexity() < MaxComp)
445 if (std::optional<nonloc::ConcreteInt> rInt =
446 RHS.getAs<nonloc::ConcreteInt>())
447 return makeNonLoc(lhs: symLHS, op: Op, rhs: rInt->getValue(), type: ResultTy);
448
449 if (symRHS && symRHS->computeComplexity() < MaxComp)
450 if (std::optional<nonloc::ConcreteInt> lInt =
451 LHS.getAs<nonloc::ConcreteInt>())
452 return makeNonLoc(lhs: lInt->getValue(), op: Op, rhs: symRHS, type: ResultTy);
453
454 return UnknownVal();
455}
456
457SVal SValBuilder::evalMinus(NonLoc X) {
458 switch (X.getKind()) {
459 case nonloc::ConcreteIntKind:
460 return makeIntVal(integer: -X.castAs<nonloc::ConcreteInt>().getValue());
461 case nonloc::SymbolValKind:
462 return makeNonLoc(operand: X.castAs<nonloc::SymbolVal>().getSymbol(), op: UO_Minus,
463 type: X.getType(Context));
464 default:
465 return UnknownVal();
466 }
467}
468
469SVal SValBuilder::evalComplement(NonLoc X) {
470 switch (X.getKind()) {
471 case nonloc::ConcreteIntKind:
472 return makeIntVal(integer: ~X.castAs<nonloc::ConcreteInt>().getValue());
473 case nonloc::SymbolValKind:
474 return makeNonLoc(operand: X.castAs<nonloc::SymbolVal>().getSymbol(), op: UO_Not,
475 type: X.getType(Context));
476 default:
477 return UnknownVal();
478 }
479}
480
481SVal SValBuilder::evalUnaryOp(ProgramStateRef state, UnaryOperator::Opcode opc,
482 SVal operand, QualType type) {
483 auto OpN = operand.getAs<NonLoc>();
484 if (!OpN)
485 return UnknownVal();
486
487 if (opc == UO_Minus)
488 return evalMinus(X: *OpN);
489 if (opc == UO_Not)
490 return evalComplement(X: *OpN);
491 llvm_unreachable("Unexpected unary operator");
492}
493
494SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
495 SVal lhs, SVal rhs, QualType type) {
496 if (lhs.isUndef() || rhs.isUndef())
497 return UndefinedVal();
498
499 if (lhs.isUnknown() || rhs.isUnknown())
500 return UnknownVal();
501
502 if (isa<nonloc::LazyCompoundVal>(Val: lhs) || isa<nonloc::LazyCompoundVal>(Val: rhs)) {
503 return UnknownVal();
504 }
505
506 if (op == BinaryOperatorKind::BO_Cmp) {
507 // We can't reason about C++20 spaceship operator yet.
508 //
509 // FIXME: Support C++20 spaceship operator.
510 // The main problem here is that the result is not integer.
511 return UnknownVal();
512 }
513
514 if (std::optional<Loc> LV = lhs.getAs<Loc>()) {
515 if (std::optional<Loc> RV = rhs.getAs<Loc>())
516 return evalBinOpLL(state, op, lhs: *LV, rhs: *RV, resultTy: type);
517
518 return evalBinOpLN(state, op, lhs: *LV, rhs: rhs.castAs<NonLoc>(), resultTy: type);
519 }
520
521 if (const std::optional<Loc> RV = rhs.getAs<Loc>()) {
522 const auto IsCommutative = [](BinaryOperatorKind Op) {
523 return Op == BO_Mul || Op == BO_Add || Op == BO_And || Op == BO_Xor ||
524 Op == BO_Or;
525 };
526
527 if (IsCommutative(op)) {
528 // Swap operands.
529 return evalBinOpLN(state, op, lhs: *RV, rhs: lhs.castAs<NonLoc>(), resultTy: type);
530 }
531
532 // If the right operand is a concrete int location then we have nothing
533 // better but to treat it as a simple nonloc.
534 if (auto RV = rhs.getAs<loc::ConcreteInt>()) {
535 const nonloc::ConcreteInt RhsAsLoc = makeIntVal(integer: RV->getValue());
536 return evalBinOpNN(state, op, lhs: lhs.castAs<NonLoc>(), rhs: RhsAsLoc, resultTy: type);
537 }
538 }
539
540 return evalBinOpNN(state, op, lhs: lhs.castAs<NonLoc>(), rhs: rhs.castAs<NonLoc>(),
541 resultTy: type);
542}
543
544ConditionTruthVal SValBuilder::areEqual(ProgramStateRef state, SVal lhs,
545 SVal rhs) {
546 return state->isNonNull(V: evalEQ(state, lhs, rhs));
547}
548
549SVal SValBuilder::evalEQ(ProgramStateRef state, SVal lhs, SVal rhs) {
550 return evalBinOp(state, op: BO_EQ, lhs, rhs, type: getConditionType());
551}
552
553DefinedOrUnknownSVal SValBuilder::evalEQ(ProgramStateRef state,
554 DefinedOrUnknownSVal lhs,
555 DefinedOrUnknownSVal rhs) {
556 return evalEQ(state, lhs: static_cast<SVal>(lhs), rhs: static_cast<SVal>(rhs))
557 .castAs<DefinedOrUnknownSVal>();
558}
559
560/// Recursively check if the pointer types are equal modulo const, volatile,
561/// and restrict qualifiers. Also, assume that all types are similar to 'void'.
562/// Assumes the input types are canonical.
563static bool shouldBeModeledWithNoOp(ASTContext &Context, QualType ToTy,
564 QualType FromTy) {
565 while (Context.UnwrapSimilarTypes(T1&: ToTy, T2&: FromTy)) {
566 Qualifiers Quals1, Quals2;
567 ToTy = Context.getUnqualifiedArrayType(T: ToTy, Quals&: Quals1);
568 FromTy = Context.getUnqualifiedArrayType(T: FromTy, Quals&: Quals2);
569
570 // Make sure that non-cvr-qualifiers the other qualifiers (e.g., address
571 // spaces) are identical.
572 Quals1.removeCVRQualifiers();
573 Quals2.removeCVRQualifiers();
574 if (Quals1 != Quals2)
575 return false;
576 }
577
578 // If we are casting to void, the 'From' value can be used to represent the
579 // 'To' value.
580 //
581 // FIXME: Doing this after unwrapping the types doesn't make any sense. A
582 // cast from 'int**' to 'void**' is not special in the way that a cast from
583 // 'int*' to 'void*' is.
584 if (ToTy->isVoidType())
585 return true;
586
587 if (ToTy != FromTy)
588 return false;
589
590 return true;
591}
592
593// Handles casts of type CK_IntegralCast.
594// At the moment, this function will redirect to evalCast, except when the range
595// of the original value is known to be greater than the max of the target type.
596SVal SValBuilder::evalIntegralCast(ProgramStateRef state, SVal val,
597 QualType castTy, QualType originalTy) {
598 // No truncations if target type is big enough.
599 if (getContext().getTypeSize(T: castTy) >= getContext().getTypeSize(T: originalTy))
600 return evalCast(V: val, CastTy: castTy, OriginalTy: originalTy);
601
602 auto AsNonLoc = val.getAs<NonLoc>();
603 SymbolRef AsSymbol = val.getAsSymbol();
604 if (!AsSymbol || !AsNonLoc) // Let evalCast handle non symbolic expressions.
605 return evalCast(V: val, CastTy: castTy, OriginalTy: originalTy);
606
607 // Find the maximum value of the target type.
608 APSIntType ToType(getContext().getTypeSize(T: castTy),
609 castTy->isUnsignedIntegerType());
610 llvm::APSInt ToTypeMax = ToType.getMaxValue();
611
612 NonLoc ToTypeMaxVal = makeIntVal(integer: ToTypeMax);
613
614 // Check the range of the symbol being casted against the maximum value of the
615 // target type.
616 QualType CmpTy = getConditionType();
617 NonLoc CompVal = evalBinOpNN(state, op: BO_LE, lhs: *AsNonLoc, rhs: ToTypeMaxVal, resultTy: CmpTy)
618 .castAs<NonLoc>();
619 ProgramStateRef IsNotTruncated, IsTruncated;
620 std::tie(args&: IsNotTruncated, args&: IsTruncated) = state->assume(Cond: CompVal);
621 if (!IsNotTruncated && IsTruncated) {
622 // Symbol is truncated so we evaluate it as a cast.
623 return makeNonLoc(operand: AsSymbol, fromTy: originalTy, toTy: castTy);
624 }
625 return evalCast(V: val, CastTy: castTy, OriginalTy: originalTy);
626}
627
628//===----------------------------------------------------------------------===//
629// Cast method.
630// `evalCast` and its helper `EvalCastVisitor`
631//===----------------------------------------------------------------------===//
632
633namespace {
634class EvalCastVisitor : public SValVisitor<EvalCastVisitor, SVal> {
635private:
636 SValBuilder &VB;
637 ASTContext &Context;
638 QualType CastTy, OriginalTy;
639
640public:
641 EvalCastVisitor(SValBuilder &VB, QualType CastTy, QualType OriginalTy)
642 : VB(VB), Context(VB.getContext()), CastTy(CastTy),
643 OriginalTy(OriginalTy) {}
644
645 SVal Visit(SVal V) {
646 if (CastTy.isNull())
647 return V;
648
649 CastTy = Context.getCanonicalType(T: CastTy);
650
651 const bool IsUnknownOriginalType = OriginalTy.isNull();
652 if (!IsUnknownOriginalType) {
653 OriginalTy = Context.getCanonicalType(T: OriginalTy);
654
655 if (CastTy == OriginalTy)
656 return V;
657
658 // FIXME: Move this check to the most appropriate
659 // evalCastKind/evalCastSubKind function. For const casts, casts to void,
660 // just propagate the value.
661 if (!CastTy->isVariableArrayType() && !OriginalTy->isVariableArrayType())
662 if (shouldBeModeledWithNoOp(Context, ToTy: Context.getPointerType(T: CastTy),
663 FromTy: Context.getPointerType(T: OriginalTy)))
664 return V;
665 }
666 return SValVisitor::Visit(V);
667 }
668 SVal VisitUndefinedVal(UndefinedVal V) { return V; }
669 SVal VisitUnknownVal(UnknownVal V) { return V; }
670 SVal VisitConcreteInt(loc::ConcreteInt V) {
671 // Pointer to bool.
672 if (CastTy->isBooleanType())
673 return VB.makeTruthVal(b: V.getValue()->getBoolValue(), type: CastTy);
674
675 // Pointer to integer.
676 if (CastTy->isIntegralOrEnumerationType()) {
677 llvm::APSInt Value = V.getValue();
678 VB.getBasicValueFactory().getAPSIntType(T: CastTy).apply(Value);
679 return VB.makeIntVal(integer: Value);
680 }
681
682 // Pointer to any pointer.
683 if (Loc::isLocType(T: CastTy)) {
684 llvm::APSInt Value = V.getValue();
685 VB.getBasicValueFactory().getAPSIntType(T: CastTy).apply(Value);
686 return loc::ConcreteInt(VB.getBasicValueFactory().getValue(X: Value));
687 }
688
689 // Pointer to whatever else.
690 return UnknownVal();
691 }
692 SVal VisitGotoLabel(loc::GotoLabel V) {
693 // Pointer to bool.
694 if (CastTy->isBooleanType())
695 // Labels are always true.
696 return VB.makeTruthVal(b: true, type: CastTy);
697
698 // Pointer to integer.
699 if (CastTy->isIntegralOrEnumerationType()) {
700 const unsigned BitWidth = Context.getIntWidth(T: CastTy);
701 return VB.makeLocAsInteger(loc: V, bits: BitWidth);
702 }
703
704 const bool IsUnknownOriginalType = OriginalTy.isNull();
705 if (!IsUnknownOriginalType) {
706 // Array to pointer.
707 if (isa<ArrayType>(Val: OriginalTy))
708 if (CastTy->isPointerType() || CastTy->isReferenceType())
709 return UnknownVal();
710 }
711
712 // Pointer to any pointer.
713 if (Loc::isLocType(T: CastTy))
714 return V;
715
716 // Pointer to whatever else.
717 return UnknownVal();
718 }
719 SVal VisitMemRegionVal(loc::MemRegionVal V) {
720 // Pointer to bool.
721 if (CastTy->isBooleanType()) {
722 const MemRegion *R = V.getRegion();
723 if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(Val: R))
724 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(Val: FTR->getDecl()))
725 if (FD->isWeak())
726 // FIXME: Currently we are using an extent symbol here,
727 // because there are no generic region address metadata
728 // symbols to use, only content metadata.
729 return nonloc::SymbolVal(
730 VB.getSymbolManager().acquire<SymbolExtent>(args&: FTR));
731
732 if (const SymbolicRegion *SymR = R->getSymbolicBase()) {
733 SymbolRef Sym = SymR->getSymbol();
734 QualType Ty = Sym->getType();
735 // This change is needed for architectures with varying
736 // pointer widths. See the amdgcn opencl reproducer with
737 // this change as an example: solver-sym-simplification-ptr-bool.cl
738 if (!Ty->isReferenceType())
739 return VB.makeNonLoc(
740 lhs: Sym, op: BO_NE, rhs: VB.getBasicValueFactory().getZeroWithTypeSize(T: Ty),
741 type: CastTy);
742 }
743 // Non-symbolic memory regions are always true.
744 return VB.makeTruthVal(b: true, type: CastTy);
745 }
746
747 const bool IsUnknownOriginalType = OriginalTy.isNull();
748 // Try to cast to array
749 const auto *ArrayTy =
750 IsUnknownOriginalType
751 ? nullptr
752 : dyn_cast<ArrayType>(Val: OriginalTy.getCanonicalType());
753
754 // Pointer to integer.
755 if (CastTy->isIntegralOrEnumerationType()) {
756 SVal Val = V;
757 // Array to integer.
758 if (ArrayTy) {
759 // We will always decay to a pointer.
760 QualType ElemTy = ArrayTy->getElementType();
761 Val = VB.getStateManager().ArrayToPointer(Array: V, ElementTy: ElemTy);
762 // FIXME: Keep these here for now in case we decide soon that we
763 // need the original decayed type.
764 // QualType elemTy = cast<ArrayType>(originalTy)->getElementType();
765 // QualType pointerTy = C.getPointerType(elemTy);
766 }
767 const unsigned BitWidth = Context.getIntWidth(T: CastTy);
768 return VB.makeLocAsInteger(loc: Val.castAs<Loc>(), bits: BitWidth);
769 }
770
771 // Pointer to pointer.
772 if (Loc::isLocType(T: CastTy)) {
773
774 if (IsUnknownOriginalType) {
775 // When retrieving symbolic pointer and expecting a non-void pointer,
776 // wrap them into element regions of the expected type if necessary.
777 // It is necessary to make sure that the retrieved value makes sense,
778 // because there's no other cast in the AST that would tell us to cast
779 // it to the correct pointer type. We might need to do that for non-void
780 // pointers as well.
781 // FIXME: We really need a single good function to perform casts for us
782 // correctly every time we need it.
783 const MemRegion *R = V.getRegion();
784 if (CastTy->isPointerType() && !CastTy->isVoidPointerType()) {
785 if (const auto *SR = dyn_cast<SymbolicRegion>(Val: R)) {
786 QualType SRTy = SR->getSymbol()->getType();
787
788 auto HasSameUnqualifiedPointeeType = [](QualType ty1,
789 QualType ty2) {
790 return ty1->getPointeeType().getCanonicalType().getTypePtr() ==
791 ty2->getPointeeType().getCanonicalType().getTypePtr();
792 };
793 if (!HasSameUnqualifiedPointeeType(SRTy, CastTy)) {
794 if (auto OptMemRegV = VB.getCastedMemRegionVal(R: SR, Ty: CastTy))
795 return *OptMemRegV;
796 }
797 }
798 }
799 // Next fixes pointer dereference using type different from its initial
800 // one. See PR37503 and PR49007 for details.
801 if (const auto *ER = dyn_cast<ElementRegion>(Val: R)) {
802 if (auto OptMemRegV = VB.getCastedMemRegionVal(R: ER, Ty: CastTy))
803 return *OptMemRegV;
804 }
805
806 return V;
807 }
808
809 if (OriginalTy->isIntegralOrEnumerationType() ||
810 OriginalTy->isBlockPointerType() ||
811 OriginalTy->isFunctionPointerType())
812 return V;
813
814 // Array to pointer.
815 if (ArrayTy) {
816 // Are we casting from an array to a pointer? If so just pass on
817 // the decayed value.
818 if (CastTy->isPointerType() || CastTy->isReferenceType()) {
819 // We will always decay to a pointer.
820 QualType ElemTy = ArrayTy->getElementType();
821 return VB.getStateManager().ArrayToPointer(Array: V, ElementTy: ElemTy);
822 }
823 // Are we casting from an array to an integer? If so, cast the decayed
824 // pointer value to an integer.
825 assert(CastTy->isIntegralOrEnumerationType());
826 }
827
828 // Other pointer to pointer.
829 assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() ||
830 CastTy->isReferenceType());
831
832 // We get a symbolic function pointer for a dereference of a function
833 // pointer, but it is of function type. Example:
834
835 // struct FPRec {
836 // void (*my_func)(int * x);
837 // };
838 //
839 // int bar(int x);
840 //
841 // int f1_a(struct FPRec* foo) {
842 // int x;
843 // (*foo->my_func)(&x);
844 // return bar(x)+1; // no-warning
845 // }
846
847 // Get the result of casting a region to a different type.
848 const MemRegion *R = V.getRegion();
849 if (auto OptMemRegV = VB.getCastedMemRegionVal(R, Ty: CastTy))
850 return *OptMemRegV;
851 }
852
853 // Pointer to whatever else.
854 // FIXME: There can be gross cases where one casts the result of a
855 // function (that returns a pointer) to some other value that happens to
856 // fit within that pointer value. We currently have no good way to model
857 // such operations. When this happens, the underlying operation is that
858 // the caller is reasoning about bits. Conceptually we are layering a
859 // "view" of a location on top of those bits. Perhaps we need to be more
860 // lazy about mutual possible views, even on an SVal? This may be
861 // necessary for bit-level reasoning as well.
862 return UnknownVal();
863 }
864 SVal VisitCompoundVal(nonloc::CompoundVal V) {
865 // Compound to whatever.
866 return UnknownVal();
867 }
868 SVal VisitConcreteInt(nonloc::ConcreteInt V) {
869 auto CastedValue = [V, this]() {
870 llvm::APSInt Value = V.getValue();
871 VB.getBasicValueFactory().getAPSIntType(T: CastTy).apply(Value);
872 return Value;
873 };
874
875 // Integer to bool.
876 if (CastTy->isBooleanType())
877 return VB.makeTruthVal(b: V.getValue()->getBoolValue(), type: CastTy);
878
879 // Integer to pointer.
880 if (CastTy->isIntegralOrEnumerationType())
881 return VB.makeIntVal(integer: CastedValue());
882
883 // Integer to pointer.
884 if (Loc::isLocType(T: CastTy))
885 return VB.makeIntLocVal(integer: CastedValue());
886
887 // Pointer to whatever else.
888 return UnknownVal();
889 }
890 SVal VisitLazyCompoundVal(nonloc::LazyCompoundVal V) {
891 // LazyCompound to whatever.
892 return UnknownVal();
893 }
894 SVal VisitLocAsInteger(nonloc::LocAsInteger V) {
895 Loc L = V.getLoc();
896
897 // Pointer as integer to bool.
898 if (CastTy->isBooleanType())
899 // Pass to Loc function.
900 return Visit(V: L);
901
902 const bool IsUnknownOriginalType = OriginalTy.isNull();
903 // Pointer as integer to pointer.
904 if (!IsUnknownOriginalType && Loc::isLocType(T: CastTy) &&
905 OriginalTy->isIntegralOrEnumerationType()) {
906 if (const MemRegion *R = L.getAsRegion())
907 if (auto OptMemRegV = VB.getCastedMemRegionVal(R, Ty: CastTy))
908 return *OptMemRegV;
909 return L;
910 }
911
912 // Pointer as integer with region to integer/pointer.
913 const MemRegion *R = L.getAsRegion();
914 if (!IsUnknownOriginalType && R) {
915 if (CastTy->isIntegralOrEnumerationType())
916 return VisitMemRegionVal(V: loc::MemRegionVal(R));
917
918 if (Loc::isLocType(T: CastTy)) {
919 assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() ||
920 CastTy->isReferenceType());
921 // Delegate to store manager to get the result of casting a region to a
922 // different type. If the MemRegion* returned is NULL, this expression
923 // Evaluates to UnknownVal.
924 if (auto OptMemRegV = VB.getCastedMemRegionVal(R, Ty: CastTy))
925 return *OptMemRegV;
926 }
927 } else {
928 if (Loc::isLocType(T: CastTy)) {
929 if (IsUnknownOriginalType)
930 return VisitMemRegionVal(V: loc::MemRegionVal(R));
931 return L;
932 }
933
934 SymbolRef SE = nullptr;
935 if (R) {
936 if (const SymbolicRegion *SR =
937 dyn_cast<SymbolicRegion>(Val: R->StripCasts())) {
938 SE = SR->getSymbol();
939 }
940 }
941
942 if (!CastTy->isFloatingType() || !SE || SE->getType()->isFloatingType()) {
943 // FIXME: Correctly support promotions/truncations.
944 const unsigned CastSize = Context.getIntWidth(T: CastTy);
945 if (CastSize == V.getNumBits())
946 return V;
947
948 return VB.makeLocAsInteger(loc: L, bits: CastSize);
949 }
950 }
951
952 // Pointer as integer to whatever else.
953 return UnknownVal();
954 }
955 SVal VisitSymbolVal(nonloc::SymbolVal V) {
956 SymbolRef SE = V.getSymbol();
957
958 const bool IsUnknownOriginalType = OriginalTy.isNull();
959 // Symbol to bool.
960 if (!IsUnknownOriginalType && CastTy->isBooleanType()) {
961 // Non-float to bool.
962 if (Loc::isLocType(T: OriginalTy) ||
963 OriginalTy->isIntegralOrEnumerationType() ||
964 OriginalTy->isMemberPointerType()) {
965 BasicValueFactory &BVF = VB.getBasicValueFactory();
966 return VB.makeNonLoc(lhs: SE, op: BO_NE, rhs: BVF.getValue(X: 0, T: SE->getType()), type: CastTy);
967 }
968 } else {
969 // Symbol to integer, float.
970 QualType T = Context.getCanonicalType(T: SE->getType());
971
972 // Produce SymbolCast if CastTy and T are different integers.
973 // NOTE: In the end the type of SymbolCast shall be equal to CastTy.
974 if (T->isIntegralOrUnscopedEnumerationType() &&
975 CastTy->isIntegralOrUnscopedEnumerationType()) {
976 AnalyzerOptions &Opts = VB.getStateManager()
977 .getOwningEngine()
978 .getAnalysisManager()
979 .getAnalyzerOptions();
980 // If appropriate option is disabled, ignore the cast.
981 // NOTE: ShouldSupportSymbolicIntegerCasts is `false` by default.
982 if (!Opts.ShouldSupportSymbolicIntegerCasts)
983 return V;
984 return simplifySymbolCast(V, CastTy);
985 }
986 if (!Loc::isLocType(T: CastTy))
987 if (!IsUnknownOriginalType || !CastTy->isFloatingType() ||
988 T->isFloatingType())
989 return VB.makeNonLoc(operand: SE, fromTy: T, toTy: CastTy);
990 }
991
992 // FIXME: We should be able to cast NonLoc -> Loc
993 // (when Loc::isLocType(CastTy) is true)
994 // But it's hard to do as SymbolicRegions can't refer to SymbolCasts holding
995 // generic SymExprs. Check the commit message for the details.
996
997 // Symbol to pointer and whatever else.
998 return UnknownVal();
999 }
1000 SVal VisitPointerToMember(nonloc::PointerToMember V) {
1001 // Member pointer to whatever.
1002 return V;
1003 }
1004
1005 /// Reduce cast expression by removing redundant intermediate casts.
1006 /// E.g.
1007 /// - (char)(short)(int x) -> (char)(int x)
1008 /// - (int)(int x) -> int x
1009 ///
1010 /// \param V -- SymbolVal, which pressumably contains SymbolCast or any symbol
1011 /// that is applicable for cast operation.
1012 /// \param CastTy -- QualType, which `V` shall be cast to.
1013 /// \return SVal with simplified cast expression.
1014 /// \note: Currently only support integral casts.
1015 nonloc::SymbolVal simplifySymbolCast(nonloc::SymbolVal V, QualType CastTy) {
1016 // We use seven conditions to recognize a simplification case.
1017 // For the clarity let `CastTy` be `C`, SE->getType() - `T`, root type -
1018 // `R`, prefix `u` for unsigned, `s` for signed, no prefix - any sign: E.g.
1019 // (char)(short)(uint x)
1020 // ( sC )( sT )( uR x)
1021 //
1022 // C === R (the same type)
1023 // (char)(char x) -> (char x)
1024 // (long)(long x) -> (long x)
1025 // Note: Comparisons operators below are for bit width.
1026 // C == T
1027 // (short)(short)(int x) -> (short)(int x)
1028 // (int)(long)(char x) -> (int)(char x) (sizeof(long) == sizeof(int))
1029 // (long)(ullong)(char x) -> (long)(char x) (sizeof(long) ==
1030 // sizeof(ullong))
1031 // C < T
1032 // (short)(int)(char x) -> (short)(char x)
1033 // (char)(int)(short x) -> (char)(short x)
1034 // (short)(int)(short x) -> (short x)
1035 // C > T > uR
1036 // (int)(short)(uchar x) -> (int)(uchar x)
1037 // (uint)(short)(uchar x) -> (uint)(uchar x)
1038 // (int)(ushort)(uchar x) -> (int)(uchar x)
1039 // C > sT > sR
1040 // (int)(short)(char x) -> (int)(char x)
1041 // (uint)(short)(char x) -> (uint)(char x)
1042 // C > sT == sR
1043 // (int)(char)(char x) -> (int)(char x)
1044 // (uint)(short)(short x) -> (uint)(short x)
1045 // C > uT == uR
1046 // (int)(uchar)(uchar x) -> (int)(uchar x)
1047 // (uint)(ushort)(ushort x) -> (uint)(ushort x)
1048 // (llong)(ulong)(uint x) -> (llong)(uint x) (sizeof(ulong) ==
1049 // sizeof(uint))
1050
1051 SymbolRef SE = V.getSymbol();
1052 QualType T = Context.getCanonicalType(T: SE->getType());
1053
1054 if (T == CastTy)
1055 return V;
1056
1057 if (!isa<SymbolCast>(Val: SE))
1058 return VB.makeNonLoc(operand: SE, fromTy: T, toTy: CastTy);
1059
1060 SymbolRef RootSym = cast<SymbolCast>(Val: SE)->getOperand();
1061 QualType RT = RootSym->getType().getCanonicalType();
1062
1063 // FIXME support simplification from non-integers.
1064 if (!RT->isIntegralOrEnumerationType())
1065 return VB.makeNonLoc(operand: SE, fromTy: T, toTy: CastTy);
1066
1067 BasicValueFactory &BVF = VB.getBasicValueFactory();
1068 APSIntType CTy = BVF.getAPSIntType(T: CastTy);
1069 APSIntType TTy = BVF.getAPSIntType(T);
1070
1071 const auto WC = CTy.getBitWidth();
1072 const auto WT = TTy.getBitWidth();
1073
1074 if (WC <= WT) {
1075 const bool isSameType = (RT == CastTy);
1076 if (isSameType)
1077 return nonloc::SymbolVal(RootSym);
1078 return VB.makeNonLoc(operand: RootSym, fromTy: RT, toTy: CastTy);
1079 }
1080
1081 APSIntType RTy = BVF.getAPSIntType(T: RT);
1082 const auto WR = RTy.getBitWidth();
1083 const bool UT = TTy.isUnsigned();
1084 const bool UR = RTy.isUnsigned();
1085
1086 if (((WT > WR) && (UR || !UT)) || ((WT == WR) && (UT == UR)))
1087 return VB.makeNonLoc(operand: RootSym, fromTy: RT, toTy: CastTy);
1088
1089 return VB.makeNonLoc(operand: SE, fromTy: T, toTy: CastTy);
1090 }
1091};
1092} // end anonymous namespace
1093
1094/// Cast a given SVal to another SVal using given QualType's.
1095/// \param V -- SVal that should be casted.
1096/// \param CastTy -- QualType that V should be casted according to.
1097/// \param OriginalTy -- QualType which is associated to V. It provides
1098/// additional information about what type the cast performs from.
1099/// \returns the most appropriate casted SVal.
1100/// Note: Many cases don't use an exact OriginalTy. It can be extracted
1101/// from SVal or the cast can performs unconditionaly. Always pass OriginalTy!
1102/// It can be crucial in certain cases and generates different results.
1103/// FIXME: If `OriginalTy.isNull()` is true, then cast performs based on CastTy
1104/// only. This behavior is uncertain and should be improved.
1105SVal SValBuilder::evalCast(SVal V, QualType CastTy, QualType OriginalTy) {
1106 EvalCastVisitor TRV{*this, CastTy, OriginalTy};
1107 return TRV.Visit(V);
1108}
1109