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