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

source code of clang/lib/StaticAnalyzer/Core/SValBuilder.cpp