1 // SValBuilder.h - Construction of SVals from evaluating expressions -*- C++ -*- 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, a class that defines the interface for 10 // "symbolical evaluators" which construct an SVal from an expression. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALBUILDER_H 15 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALBUILDER_H 16 17 #include "clang/AST/ASTContext.h" 18 #include "clang/AST/DeclarationName.h" 19 #include "clang/AST/Expr.h" 20 #include "clang/AST/ExprObjC.h" 21 #include "clang/AST/Type.h" 22 #include "clang/Basic/LLVM.h" 23 #include "clang/Basic/LangOptions.h" 24 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h" 25 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 26 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" 27 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 28 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 29 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 30 #include "llvm/ADT/ImmutableList.h" 31 #include <cstdint> 32 #include <optional> 33 34 namespace clang { 35 36 class AnalyzerOptions; 37 class BlockDecl; 38 class CXXBoolLiteralExpr; 39 class CXXMethodDecl; 40 class CXXRecordDecl; 41 class DeclaratorDecl; 42 class FunctionDecl; 43 class LocationContext; 44 class StackFrameContext; 45 class Stmt; 46 47 namespace ento { 48 49 class ConditionTruthVal; 50 class ProgramStateManager; 51 class StoreRef; 52 53 class SValBuilder { 54 virtual void anchor(); 55 56 protected: 57 ASTContext &Context; 58 59 /// Manager of APSInt values. 60 BasicValueFactory BasicVals; 61 62 /// Manages the creation of symbols. 63 SymbolManager SymMgr; 64 65 /// Manages the creation of memory regions. 66 MemRegionManager MemMgr; 67 68 ProgramStateManager &StateMgr; 69 70 const AnalyzerOptions &AnOpts; 71 72 /// The scalar type to use for array indices. 73 const QualType ArrayIndexTy; 74 75 /// The width of the scalar type used for array indices. 76 const unsigned ArrayIndexWidth; 77 78 public: 79 SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, 80 ProgramStateManager &stateMgr); 81 82 virtual ~SValBuilder() = default; 83 84 SVal evalCast(SVal V, QualType CastTy, QualType OriginalTy); 85 86 // Handles casts of type CK_IntegralCast. 87 SVal evalIntegralCast(ProgramStateRef state, SVal val, QualType castTy, 88 QualType originalType); 89 90 SVal evalMinus(NonLoc val); 91 SVal evalComplement(NonLoc val); 92 93 /// Create a new value which represents a binary expression with two non- 94 /// location operands. 95 virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, 96 NonLoc lhs, NonLoc rhs, QualType resultTy) = 0; 97 98 /// Create a new value which represents a binary expression with two memory 99 /// location operands. 100 virtual SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op, 101 Loc lhs, Loc rhs, QualType resultTy) = 0; 102 103 /// Create a new value which represents a binary expression with a memory 104 /// location and non-location operands. For example, this would be used to 105 /// evaluate a pointer arithmetic operation. 106 virtual SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op, 107 Loc lhs, NonLoc rhs, QualType resultTy) = 0; 108 109 /// Evaluates a given SVal. If the SVal has only one possible (integer) value, 110 /// that value is returned. Otherwise, returns NULL. 111 virtual const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal val) = 0; 112 113 /// Tries to get the minimal possible (integer) value of a given SVal. If the 114 /// constraint manager cannot provide an useful answer, this returns NULL. 115 virtual const llvm::APSInt *getMinValue(ProgramStateRef state, SVal val) = 0; 116 117 /// Tries to get the maximal possible (integer) value of a given SVal. If the 118 /// constraint manager cannot provide an useful answer, this returns NULL. 119 virtual const llvm::APSInt *getMaxValue(ProgramStateRef state, SVal val) = 0; 120 121 /// Simplify symbolic expressions within a given SVal. Return an SVal 122 /// that represents the same value, but is hopefully easier to work with 123 /// than the original SVal. 124 virtual SVal simplifySVal(ProgramStateRef State, SVal Val) = 0; 125 126 /// Constructs a symbolic expression for two non-location values. 127 SVal makeSymExprValNN(BinaryOperator::Opcode op, 128 NonLoc lhs, NonLoc rhs, QualType resultTy); 129 130 SVal evalUnaryOp(ProgramStateRef state, UnaryOperator::Opcode opc, 131 SVal operand, QualType type); 132 133 SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, 134 SVal lhs, SVal rhs, QualType type); 135 136 /// \return Whether values in \p lhs and \p rhs are equal at \p state. 137 ConditionTruthVal areEqual(ProgramStateRef state, SVal lhs, SVal rhs); 138 139 SVal evalEQ(ProgramStateRef state, SVal lhs, SVal rhs); 140 141 DefinedOrUnknownSVal evalEQ(ProgramStateRef state, DefinedOrUnknownSVal lhs, 142 DefinedOrUnknownSVal rhs); 143 getContext()144 ASTContext &getContext() { return Context; } getContext()145 const ASTContext &getContext() const { return Context; } 146 getStateManager()147 ProgramStateManager &getStateManager() { return StateMgr; } 148 getConditionType()149 QualType getConditionType() const { 150 return Context.getLangOpts().CPlusPlus ? Context.BoolTy : Context.IntTy; 151 } 152 getArrayIndexType()153 QualType getArrayIndexType() const { 154 return ArrayIndexTy; 155 } 156 getBasicValueFactory()157 BasicValueFactory &getBasicValueFactory() { return BasicVals; } getBasicValueFactory()158 const BasicValueFactory &getBasicValueFactory() const { return BasicVals; } 159 getSymbolManager()160 SymbolManager &getSymbolManager() { return SymMgr; } getSymbolManager()161 const SymbolManager &getSymbolManager() const { return SymMgr; } 162 getRegionManager()163 MemRegionManager &getRegionManager() { return MemMgr; } getRegionManager()164 const MemRegionManager &getRegionManager() const { return MemMgr; } 165 getAnalyzerOptions()166 const AnalyzerOptions &getAnalyzerOptions() const { return AnOpts; } 167 168 // Forwarding methods to SymbolManager. 169 170 const SymbolConjured* conjureSymbol(const Stmt *stmt, 171 const LocationContext *LCtx, 172 QualType type, 173 unsigned visitCount, 174 const void *symbolTag = nullptr) { 175 return SymMgr.conjureSymbol(stmt, LCtx, type, visitCount, symbolTag); 176 } 177 178 const SymbolConjured* conjureSymbol(const Expr *expr, 179 const LocationContext *LCtx, 180 unsigned visitCount, 181 const void *symbolTag = nullptr) { 182 return SymMgr.conjureSymbol(expr, LCtx, visitCount, symbolTag); 183 } 184 185 /// Construct an SVal representing '0' for the specified type. 186 DefinedOrUnknownSVal makeZeroVal(QualType type); 187 188 /// Make a unique symbol for value of region. 189 DefinedOrUnknownSVal getRegionValueSymbolVal(const TypedValueRegion *region); 190 191 /// Create a new symbol with a unique 'name'. 192 /// 193 /// We resort to conjured symbols when we cannot construct a derived symbol. 194 /// The advantage of symbols derived/built from other symbols is that we 195 /// preserve the relation between related(or even equivalent) expressions, so 196 /// conjured symbols should be used sparingly. 197 DefinedOrUnknownSVal conjureSymbolVal(const void *symbolTag, 198 const Expr *expr, 199 const LocationContext *LCtx, 200 unsigned count); 201 DefinedOrUnknownSVal conjureSymbolVal(const void *symbolTag, 202 const Expr *expr, 203 const LocationContext *LCtx, 204 QualType type, 205 unsigned count); 206 DefinedOrUnknownSVal conjureSymbolVal(const Stmt *stmt, 207 const LocationContext *LCtx, 208 QualType type, 209 unsigned visitCount); 210 211 /// Conjure a symbol representing heap allocated memory region. 212 /// 213 /// Note, the expression should represent a location. 214 DefinedOrUnknownSVal getConjuredHeapSymbolVal(const Expr *E, 215 const LocationContext *LCtx, 216 unsigned Count); 217 218 /// Conjure a symbol representing heap allocated memory region. 219 /// 220 /// Note, now, the expression *doesn't* need to represent a location. 221 /// But the type need to! 222 DefinedOrUnknownSVal getConjuredHeapSymbolVal(const Expr *E, 223 const LocationContext *LCtx, 224 QualType type, unsigned Count); 225 226 /// Create an SVal representing the result of an alloca()-like call, that is, 227 /// an AllocaRegion on the stack. 228 /// 229 /// After calling this function, it's a good idea to set the extent of the 230 /// returned AllocaRegion. 231 loc::MemRegionVal getAllocaRegionVal(const Expr *E, 232 const LocationContext *LCtx, 233 unsigned Count); 234 235 DefinedOrUnknownSVal getDerivedRegionValueSymbolVal( 236 SymbolRef parentSymbol, const TypedValueRegion *region); 237 238 DefinedSVal getMetadataSymbolVal(const void *symbolTag, 239 const MemRegion *region, 240 const Expr *expr, QualType type, 241 const LocationContext *LCtx, 242 unsigned count); 243 244 DefinedSVal getMemberPointer(const NamedDecl *ND); 245 246 DefinedSVal getFunctionPointer(const FunctionDecl *func); 247 248 DefinedSVal getBlockPointer(const BlockDecl *block, CanQualType locTy, 249 const LocationContext *locContext, 250 unsigned blockCount); 251 252 /// Returns the value of \p E, if it can be determined in a non-path-sensitive 253 /// manner. 254 /// 255 /// If \p E is not a constant or cannot be modeled, returns \c std::nullopt. 256 std::optional<SVal> getConstantVal(const Expr *E); 257 makeCompoundVal(QualType type,llvm::ImmutableList<SVal> vals)258 NonLoc makeCompoundVal(QualType type, llvm::ImmutableList<SVal> vals) { 259 return nonloc::CompoundVal(BasicVals.getCompoundValData(type, vals)); 260 } 261 makeLazyCompoundVal(const StoreRef & store,const TypedValueRegion * region)262 NonLoc makeLazyCompoundVal(const StoreRef &store, 263 const TypedValueRegion *region) { 264 return nonloc::LazyCompoundVal( 265 BasicVals.getLazyCompoundValData(store, region)); 266 } 267 makePointerToMember(const DeclaratorDecl * DD)268 NonLoc makePointerToMember(const DeclaratorDecl *DD) { 269 return nonloc::PointerToMember(DD); 270 } 271 makePointerToMember(const PointerToMemberData * PTMD)272 NonLoc makePointerToMember(const PointerToMemberData *PTMD) { 273 return nonloc::PointerToMember(PTMD); 274 } 275 makeZeroArrayIndex()276 NonLoc makeZeroArrayIndex() { 277 return nonloc::ConcreteInt(BasicVals.getValue(0, ArrayIndexTy)); 278 } 279 makeArrayIndex(uint64_t idx)280 NonLoc makeArrayIndex(uint64_t idx) { 281 return nonloc::ConcreteInt(BasicVals.getValue(idx, ArrayIndexTy)); 282 } 283 284 SVal convertToArrayIndex(SVal val); 285 makeIntVal(const IntegerLiteral * integer)286 nonloc::ConcreteInt makeIntVal(const IntegerLiteral* integer) { 287 return nonloc::ConcreteInt( 288 BasicVals.getValue(integer->getValue(), 289 integer->getType()->isUnsignedIntegerOrEnumerationType())); 290 } 291 makeBoolVal(const ObjCBoolLiteralExpr * boolean)292 nonloc::ConcreteInt makeBoolVal(const ObjCBoolLiteralExpr *boolean) { 293 return makeTruthVal(boolean->getValue(), boolean->getType()); 294 } 295 296 nonloc::ConcreteInt makeBoolVal(const CXXBoolLiteralExpr *boolean); 297 makeIntVal(const llvm::APSInt & integer)298 nonloc::ConcreteInt makeIntVal(const llvm::APSInt& integer) { 299 return nonloc::ConcreteInt(BasicVals.getValue(integer)); 300 } 301 makeIntLocVal(const llvm::APSInt & integer)302 loc::ConcreteInt makeIntLocVal(const llvm::APSInt &integer) { 303 return loc::ConcreteInt(BasicVals.getValue(integer)); 304 } 305 makeIntVal(const llvm::APInt & integer,bool isUnsigned)306 NonLoc makeIntVal(const llvm::APInt& integer, bool isUnsigned) { 307 return nonloc::ConcreteInt(BasicVals.getValue(integer, isUnsigned)); 308 } 309 makeIntVal(uint64_t integer,QualType type)310 DefinedSVal makeIntVal(uint64_t integer, QualType type) { 311 if (Loc::isLocType(type)) 312 return loc::ConcreteInt(BasicVals.getValue(integer, type)); 313 314 return nonloc::ConcreteInt(BasicVals.getValue(integer, type)); 315 } 316 makeIntVal(uint64_t integer,bool isUnsigned)317 NonLoc makeIntVal(uint64_t integer, bool isUnsigned) { 318 return nonloc::ConcreteInt(BasicVals.getIntValue(integer, isUnsigned)); 319 } 320 makeIntValWithWidth(QualType ptrType,uint64_t integer)321 NonLoc makeIntValWithWidth(QualType ptrType, uint64_t integer) { 322 return nonloc::ConcreteInt(BasicVals.getValue(integer, ptrType)); 323 } 324 makeLocAsInteger(Loc loc,unsigned bits)325 NonLoc makeLocAsInteger(Loc loc, unsigned bits) { 326 return nonloc::LocAsInteger(BasicVals.getPersistentSValWithData(loc, bits)); 327 } 328 329 nonloc::SymbolVal makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, 330 const llvm::APSInt &rhs, QualType type); 331 332 nonloc::SymbolVal makeNonLoc(const llvm::APSInt &rhs, 333 BinaryOperator::Opcode op, const SymExpr *lhs, 334 QualType type); 335 336 nonloc::SymbolVal makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, 337 const SymExpr *rhs, QualType type); 338 339 NonLoc makeNonLoc(const SymExpr *operand, UnaryOperator::Opcode op, 340 QualType type); 341 342 /// Create a NonLoc value for cast. 343 nonloc::SymbolVal makeNonLoc(const SymExpr *operand, QualType fromTy, 344 QualType toTy); 345 makeTruthVal(bool b,QualType type)346 nonloc::ConcreteInt makeTruthVal(bool b, QualType type) { 347 return nonloc::ConcreteInt(BasicVals.getTruthValue(b, type)); 348 } 349 makeTruthVal(bool b)350 nonloc::ConcreteInt makeTruthVal(bool b) { 351 return nonloc::ConcreteInt(BasicVals.getTruthValue(b)); 352 } 353 354 /// Create NULL pointer, with proper pointer bit-width for given address 355 /// space. 356 /// \param type pointer type. makeNullWithType(QualType type)357 loc::ConcreteInt makeNullWithType(QualType type) { 358 // We cannot use the `isAnyPointerType()`. 359 assert((type->isPointerType() || type->isObjCObjectPointerType() || 360 type->isBlockPointerType() || type->isNullPtrType() || 361 type->isReferenceType()) && 362 "makeNullWithType must use pointer type"); 363 364 // The `sizeof(T&)` is `sizeof(T)`, thus we replace the reference with a 365 // pointer. Here we assume that references are actually implemented by 366 // pointers under-the-hood. 367 type = type->isReferenceType() 368 ? Context.getPointerType(type->getPointeeType()) 369 : type; 370 return loc::ConcreteInt(BasicVals.getZeroWithTypeSize(type)); 371 } 372 makeLoc(SymbolRef sym)373 loc::MemRegionVal makeLoc(SymbolRef sym) { 374 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 375 } 376 makeLoc(const MemRegion * region)377 loc::MemRegionVal makeLoc(const MemRegion *region) { 378 return loc::MemRegionVal(region); 379 } 380 makeLoc(const AddrLabelExpr * expr)381 loc::GotoLabel makeLoc(const AddrLabelExpr *expr) { 382 return loc::GotoLabel(expr->getLabel()); 383 } 384 makeLoc(const llvm::APSInt & integer)385 loc::ConcreteInt makeLoc(const llvm::APSInt &integer) { 386 return loc::ConcreteInt(BasicVals.getValue(integer)); 387 } 388 389 /// Return MemRegionVal on success cast, otherwise return std::nullopt. 390 std::optional<loc::MemRegionVal> 391 getCastedMemRegionVal(const MemRegion *region, QualType type); 392 393 /// Make an SVal that represents the given symbol. This follows the convention 394 /// of representing Loc-type symbols (symbolic pointers and references) 395 /// as Loc values wrapping the symbol rather than as plain symbol values. makeSymbolVal(SymbolRef Sym)396 DefinedSVal makeSymbolVal(SymbolRef Sym) { 397 if (Loc::isLocType(Sym->getType())) 398 return makeLoc(Sym); 399 return nonloc::SymbolVal(Sym); 400 } 401 402 /// Return a memory region for the 'this' object reference. 403 loc::MemRegionVal getCXXThis(const CXXMethodDecl *D, 404 const StackFrameContext *SFC); 405 406 /// Return a memory region for the 'this' object reference. 407 loc::MemRegionVal getCXXThis(const CXXRecordDecl *D, 408 const StackFrameContext *SFC); 409 }; 410 411 SValBuilder* createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc, 412 ASTContext &context, 413 ProgramStateManager &stateMgr); 414 415 } // namespace ento 416 417 } // namespace clang 418 419 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALBUILDER_H 420