SValBuilder.cpp revision baeaa9ad120f60b1c5b6f1a84286b507dbe2b55d
1// SValBuilder.cpp - Basic class for all SValBuilder implementations -*- C++ -*- 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines SValBuilder, the base class for all (complete) SValBuilder 11// implementations. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/AST/ExprCXX.h" 16#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 17#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 19#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 20#include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h" 21 22using namespace clang; 23using namespace ento; 24 25//===----------------------------------------------------------------------===// 26// Basic SVal creation. 27//===----------------------------------------------------------------------===// 28 29void SValBuilder::anchor() { } 30 31DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType type) { 32 if (Loc::isLocType(type)) 33 return makeNull(); 34 35 if (type->isIntegerType()) 36 return makeIntVal(0, type); 37 38 // FIXME: Handle floats. 39 // FIXME: Handle structs. 40 return UnknownVal(); 41} 42 43NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, 44 const llvm::APSInt& rhs, QualType type) { 45 // The Environment ensures we always get a persistent APSInt in 46 // BasicValueFactory, so we don't need to get the APSInt from 47 // BasicValueFactory again. 48 assert(lhs); 49 assert(!Loc::isLocType(type)); 50 return nonloc::SymbolVal(SymMgr.getSymIntExpr(lhs, op, rhs, type)); 51} 52 53NonLoc SValBuilder::makeNonLoc(const llvm::APSInt& lhs, 54 BinaryOperator::Opcode op, const SymExpr *rhs, 55 QualType type) { 56 assert(rhs); 57 assert(!Loc::isLocType(type)); 58 return nonloc::SymbolVal(SymMgr.getIntSymExpr(lhs, op, rhs, type)); 59} 60 61NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, 62 const SymExpr *rhs, QualType type) { 63 assert(lhs && rhs); 64 assert(haveSameType(lhs->getType(Context), rhs->getType(Context)) == true); 65 assert(!Loc::isLocType(type)); 66 return nonloc::SymbolVal(SymMgr.getSymSymExpr(lhs, op, rhs, type)); 67} 68 69NonLoc SValBuilder::makeNonLoc(const SymExpr *operand, 70 QualType fromTy, QualType toTy) { 71 assert(operand); 72 assert(!Loc::isLocType(toTy)); 73 return nonloc::SymbolVal(SymMgr.getCastSymbol(operand, fromTy, toTy)); 74} 75 76SVal SValBuilder::convertToArrayIndex(SVal val) { 77 if (val.isUnknownOrUndef()) 78 return val; 79 80 // Common case: we have an appropriately sized integer. 81 if (nonloc::ConcreteInt* CI = dyn_cast<nonloc::ConcreteInt>(&val)) { 82 const llvm::APSInt& I = CI->getValue(); 83 if (I.getBitWidth() == ArrayIndexWidth && I.isSigned()) 84 return val; 85 } 86 87 return evalCastFromNonLoc(cast<NonLoc>(val), ArrayIndexTy); 88} 89 90nonloc::ConcreteInt SValBuilder::makeBoolVal(const CXXBoolLiteralExpr *boolean){ 91 return makeTruthVal(boolean->getValue()); 92} 93 94DefinedOrUnknownSVal 95SValBuilder::getRegionValueSymbolVal(const TypedValueRegion* region) { 96 QualType T = region->getValueType(); 97 98 if (!SymbolManager::canSymbolicate(T)) 99 return UnknownVal(); 100 101 SymbolRef sym = SymMgr.getRegionValueSymbol(region); 102 103 if (Loc::isLocType(T)) 104 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 105 106 return nonloc::SymbolVal(sym); 107} 108 109DefinedOrUnknownSVal 110SValBuilder::getConjuredSymbolVal(const void *symbolTag, 111 const Expr *expr, 112 const LocationContext *LCtx, 113 unsigned count) { 114 QualType T = expr->getType(); 115 return getConjuredSymbolVal(symbolTag, expr, LCtx, T, count); 116} 117 118DefinedOrUnknownSVal 119SValBuilder::getConjuredSymbolVal(const void *symbolTag, 120 const Expr *expr, 121 const LocationContext *LCtx, 122 QualType type, 123 unsigned count) { 124 if (!SymbolManager::canSymbolicate(type)) 125 return UnknownVal(); 126 127 SymbolRef sym = SymMgr.getConjuredSymbol(expr, LCtx, type, count, symbolTag); 128 129 if (Loc::isLocType(type)) 130 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 131 132 return nonloc::SymbolVal(sym); 133} 134 135 136DefinedOrUnknownSVal 137SValBuilder::getConjuredSymbolVal(const Stmt *stmt, 138 const LocationContext *LCtx, 139 QualType type, 140 unsigned visitCount) { 141 if (!SymbolManager::canSymbolicate(type)) 142 return UnknownVal(); 143 144 SymbolRef sym = SymMgr.getConjuredSymbol(stmt, LCtx, type, visitCount); 145 146 if (Loc::isLocType(type)) 147 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 148 149 return nonloc::SymbolVal(sym); 150} 151 152DefinedSVal SValBuilder::getMetadataSymbolVal(const void *symbolTag, 153 const MemRegion *region, 154 const Expr *expr, QualType type, 155 unsigned count) { 156 assert(SymbolManager::canSymbolicate(type) && "Invalid metadata symbol type"); 157 158 SymbolRef sym = 159 SymMgr.getMetadataSymbol(region, expr, type, count, symbolTag); 160 161 if (Loc::isLocType(type)) 162 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 163 164 return nonloc::SymbolVal(sym); 165} 166 167DefinedOrUnknownSVal 168SValBuilder::getDerivedRegionValueSymbolVal(SymbolRef parentSymbol, 169 const TypedValueRegion *region) { 170 QualType T = region->getValueType(); 171 172 if (!SymbolManager::canSymbolicate(T)) 173 return UnknownVal(); 174 175 SymbolRef sym = SymMgr.getDerivedSymbol(parentSymbol, region); 176 177 if (Loc::isLocType(T)) 178 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 179 180 return nonloc::SymbolVal(sym); 181} 182 183DefinedSVal SValBuilder::getFunctionPointer(const FunctionDecl *func) { 184 return loc::MemRegionVal(MemMgr.getFunctionTextRegion(func)); 185} 186 187DefinedSVal SValBuilder::getBlockPointer(const BlockDecl *block, 188 CanQualType locTy, 189 const LocationContext *locContext) { 190 const BlockTextRegion *BC = 191 MemMgr.getBlockTextRegion(block, locTy, locContext->getAnalysisDeclContext()); 192 const BlockDataRegion *BD = MemMgr.getBlockDataRegion(BC, locContext); 193 return loc::MemRegionVal(BD); 194} 195 196//===----------------------------------------------------------------------===// 197 198SVal SValBuilder::makeSymExprValNN(ProgramStateRef State, 199 BinaryOperator::Opcode Op, 200 NonLoc LHS, NonLoc RHS, 201 QualType ResultTy) { 202 if (!State->isTainted(RHS) && !State->isTainted(LHS)) 203 return UnknownVal(); 204 205 const SymExpr *symLHS = LHS.getAsSymExpr(); 206 const SymExpr *symRHS = RHS.getAsSymExpr(); 207 // TODO: When the Max Complexity is reached, we should conjure a symbol 208 // instead of generating an Unknown value and propagate the taint info to it. 209 const unsigned MaxComp = 10000; // 100000 28X 210 211 if (symLHS && symRHS && 212 (symLHS->computeComplexity() + symRHS->computeComplexity()) < MaxComp) 213 return makeNonLoc(symLHS, Op, symRHS, ResultTy); 214 215 if (symLHS && symLHS->computeComplexity() < MaxComp) 216 if (const nonloc::ConcreteInt *rInt = dyn_cast<nonloc::ConcreteInt>(&RHS)) 217 return makeNonLoc(symLHS, Op, rInt->getValue(), ResultTy); 218 219 if (symRHS && symRHS->computeComplexity() < MaxComp) 220 if (const nonloc::ConcreteInt *lInt = dyn_cast<nonloc::ConcreteInt>(&LHS)) 221 return makeNonLoc(lInt->getValue(), Op, symRHS, ResultTy); 222 223 return UnknownVal(); 224} 225 226 227SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, 228 SVal lhs, SVal rhs, QualType type) { 229 230 if (lhs.isUndef() || rhs.isUndef()) 231 return UndefinedVal(); 232 233 if (lhs.isUnknown() || rhs.isUnknown()) 234 return UnknownVal(); 235 236 if (isa<Loc>(lhs)) { 237 if (isa<Loc>(rhs)) 238 return evalBinOpLL(state, op, cast<Loc>(lhs), cast<Loc>(rhs), type); 239 240 return evalBinOpLN(state, op, cast<Loc>(lhs), cast<NonLoc>(rhs), type); 241 } 242 243 if (isa<Loc>(rhs)) { 244 // Support pointer arithmetic where the addend is on the left 245 // and the pointer on the right. 246 assert(op == BO_Add); 247 248 // Commute the operands. 249 return evalBinOpLN(state, op, cast<Loc>(rhs), cast<NonLoc>(lhs), type); 250 } 251 252 return evalBinOpNN(state, op, cast<NonLoc>(lhs), cast<NonLoc>(rhs), type); 253} 254 255DefinedOrUnknownSVal SValBuilder::evalEQ(ProgramStateRef state, 256 DefinedOrUnknownSVal lhs, 257 DefinedOrUnknownSVal rhs) { 258 return cast<DefinedOrUnknownSVal>(evalBinOp(state, BO_EQ, lhs, rhs, 259 Context.IntTy)); 260} 261 262/// Recursively check if the pointer types are equal modulo const, volatile, 263/// and restrict qualifiers. Assumes the input types are canonical. 264/// TODO: This is based off of code in SemaCast; can we reuse it. 265static bool haveSimilarTypes(ASTContext &Context, QualType T1, 266 QualType T2) { 267 while (Context.UnwrapSimilarPointerTypes(T1, T2)) { 268 Qualifiers Quals1, Quals2; 269 T1 = Context.getUnqualifiedArrayType(T1, Quals1); 270 T2 = Context.getUnqualifiedArrayType(T2, Quals2); 271 272 // Make sure that non cvr-qualifiers the other qualifiers (e.g., address 273 // spaces) are identical. 274 Quals1.removeCVRQualifiers(); 275 Quals2.removeCVRQualifiers(); 276 if (Quals1 != Quals2) 277 return false; 278 } 279 280 if (T1 != T2) 281 return false; 282 283 return true; 284} 285 286// FIXME: should rewrite according to the cast kind. 287SVal SValBuilder::evalCast(SVal val, QualType castTy, QualType originalTy) { 288 castTy = Context.getCanonicalType(castTy); 289 originalTy = Context.getCanonicalType(originalTy); 290 if (val.isUnknownOrUndef() || castTy == originalTy) 291 return val; 292 293 // For const casts, just propagate the value. 294 if (!castTy->isVariableArrayType() && !originalTy->isVariableArrayType()) 295 if (haveSimilarTypes(Context, Context.getPointerType(castTy), 296 Context.getPointerType(originalTy))) 297 return val; 298 299 // Check for casts from pointers to integers. 300 if (castTy->isIntegerType() && Loc::isLocType(originalTy)) 301 return evalCastFromLoc(cast<Loc>(val), castTy); 302 303 // Check for casts from integers to pointers. 304 if (Loc::isLocType(castTy) && originalTy->isIntegerType()) { 305 if (nonloc::LocAsInteger *LV = dyn_cast<nonloc::LocAsInteger>(&val)) { 306 if (const MemRegion *R = LV->getLoc().getAsRegion()) { 307 StoreManager &storeMgr = StateMgr.getStoreManager(); 308 R = storeMgr.castRegion(R, castTy); 309 return R ? SVal(loc::MemRegionVal(R)) : UnknownVal(); 310 } 311 return LV->getLoc(); 312 } 313 return dispatchCast(val, castTy); 314 } 315 316 // Just pass through function and block pointers. 317 if (originalTy->isBlockPointerType() || originalTy->isFunctionPointerType()) { 318 assert(Loc::isLocType(castTy)); 319 return val; 320 } 321 322 // Check for casts from array type to another type. 323 if (originalTy->isArrayType()) { 324 // We will always decay to a pointer. 325 val = StateMgr.ArrayToPointer(cast<Loc>(val)); 326 327 // Are we casting from an array to a pointer? If so just pass on 328 // the decayed value. 329 if (castTy->isPointerType()) 330 return val; 331 332 // Are we casting from an array to an integer? If so, cast the decayed 333 // pointer value to an integer. 334 assert(castTy->isIntegerType()); 335 336 // FIXME: Keep these here for now in case we decide soon that we 337 // need the original decayed type. 338 // QualType elemTy = cast<ArrayType>(originalTy)->getElementType(); 339 // QualType pointerTy = C.getPointerType(elemTy); 340 return evalCastFromLoc(cast<Loc>(val), castTy); 341 } 342 343 // Check for casts from a region to a specific type. 344 if (const MemRegion *R = val.getAsRegion()) { 345 // Handle other casts of locations to integers. 346 if (castTy->isIntegerType()) 347 return evalCastFromLoc(loc::MemRegionVal(R), castTy); 348 349 // FIXME: We should handle the case where we strip off view layers to get 350 // to a desugared type. 351 if (!Loc::isLocType(castTy)) { 352 // FIXME: There can be gross cases where one casts the result of a function 353 // (that returns a pointer) to some other value that happens to fit 354 // within that pointer value. We currently have no good way to 355 // model such operations. When this happens, the underlying operation 356 // is that the caller is reasoning about bits. Conceptually we are 357 // layering a "view" of a location on top of those bits. Perhaps 358 // we need to be more lazy about mutual possible views, even on an 359 // SVal? This may be necessary for bit-level reasoning as well. 360 return UnknownVal(); 361 } 362 363 // We get a symbolic function pointer for a dereference of a function 364 // pointer, but it is of function type. Example: 365 366 // struct FPRec { 367 // void (*my_func)(int * x); 368 // }; 369 // 370 // int bar(int x); 371 // 372 // int f1_a(struct FPRec* foo) { 373 // int x; 374 // (*foo->my_func)(&x); 375 // return bar(x)+1; // no-warning 376 // } 377 378 assert(Loc::isLocType(originalTy) || originalTy->isFunctionType() || 379 originalTy->isBlockPointerType() || castTy->isReferenceType()); 380 381 StoreManager &storeMgr = StateMgr.getStoreManager(); 382 383 // Delegate to store manager to get the result of casting a region to a 384 // different type. If the MemRegion* returned is NULL, this expression 385 // Evaluates to UnknownVal. 386 R = storeMgr.castRegion(R, castTy); 387 return R ? SVal(loc::MemRegionVal(R)) : UnknownVal(); 388 } 389 390 return dispatchCast(val, castTy); 391} 392