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