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