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

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