SVals.cpp revision 25a792b0361d80337c75a14320f5be1b210066dc
1//= RValues.cpp - Abstract RValues for Path-Sens. Value Tracking -*- 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 SVal, Loc, and NonLoc, classes that represent 11// abstract r-values for use with path-sensitive value tracking. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h" 16#include "clang/AST/ExprObjC.h" 17#include "clang/Basic/IdentifierTable.h" 18 19using namespace clang; 20using namespace ento; 21using llvm::dyn_cast; 22using llvm::cast; 23using llvm::APSInt; 24 25//===----------------------------------------------------------------------===// 26// Symbol iteration within an SVal. 27//===----------------------------------------------------------------------===// 28 29 30//===----------------------------------------------------------------------===// 31// Utility methods. 32//===----------------------------------------------------------------------===// 33 34bool SVal::hasConjuredSymbol() const { 35 if (const nonloc::SymbolVal* SV = dyn_cast<nonloc::SymbolVal>(this)) { 36 SymbolRef sym = SV->getSymbol(); 37 if (isa<SymbolConjured>(sym)) 38 return true; 39 } 40 41 if (const loc::MemRegionVal *RV = dyn_cast<loc::MemRegionVal>(this)) { 42 const MemRegion *R = RV->getRegion(); 43 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 44 SymbolRef sym = SR->getSymbol(); 45 if (isa<SymbolConjured>(sym)) 46 return true; 47 } 48 } 49 50 return false; 51} 52 53const FunctionDecl *SVal::getAsFunctionDecl() const { 54 if (const loc::MemRegionVal* X = dyn_cast<loc::MemRegionVal>(this)) { 55 const MemRegion* R = X->getRegion(); 56 if (const FunctionTextRegion *CTR = R->getAs<FunctionTextRegion>()) 57 return CTR->getDecl(); 58 } 59 60 return NULL; 61} 62 63/// getAsLocSymbol - If this SVal is a location (subclasses Loc) and 64/// wraps a symbol, return that SymbolRef. Otherwise return 0. 65// FIXME: should we consider SymbolRef wrapped in CodeTextRegion? 66SymbolRef SVal::getAsLocSymbol() const { 67 if (const nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(this)) 68 return X->getLoc().getAsLocSymbol(); 69 70 if (const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this)) { 71 const MemRegion *R = X->stripCasts(); 72 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R)) 73 return SymR->getSymbol(); 74 } 75 return NULL; 76} 77 78/// Get the symbol in the SVal or its base region. 79SymbolRef SVal::getLocSymbolInBase() const { 80 const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this); 81 82 if (!X) 83 return 0; 84 85 const MemRegion *R = X->getRegion(); 86 87 while (const SubRegion *SR = dyn_cast<SubRegion>(R)) { 88 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(SR)) 89 return SymR->getSymbol(); 90 else 91 R = SR->getSuperRegion(); 92 } 93 94 return 0; 95} 96 97/// getAsSymbol - If this Sval wraps a symbol return that SymbolRef. 98/// Otherwise return 0. 99// FIXME: should we consider SymbolRef wrapped in CodeTextRegion? 100SymbolRef SVal::getAsSymbol() const { 101 if (const nonloc::SymbolVal *X = dyn_cast<nonloc::SymbolVal>(this)) 102 return X->getSymbol(); 103 104 if (const nonloc::SymExprVal *X = dyn_cast<nonloc::SymExprVal>(this)) 105 if (SymbolRef Y = dyn_cast<SymbolData>(X->getSymbolicExpression())) 106 return Y; 107 108 return getAsLocSymbol(); 109} 110 111/// getAsSymbolicExpression - If this Sval wraps a symbolic expression then 112/// return that expression. Otherwise return NULL. 113const SymExpr *SVal::getAsSymbolicExpression() const { 114 if (const nonloc::SymExprVal *X = dyn_cast<nonloc::SymExprVal>(this)) 115 return X->getSymbolicExpression(); 116 117 return getAsSymbol(); 118} 119 120const MemRegion *SVal::getAsRegion() const { 121 if (const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this)) 122 return X->getRegion(); 123 124 if (const nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(this)) { 125 return X->getLoc().getAsRegion(); 126 } 127 128 return 0; 129} 130 131const MemRegion *loc::MemRegionVal::stripCasts() const { 132 const MemRegion *R = getRegion(); 133 return R ? R->StripCasts() : NULL; 134} 135 136bool SVal::symbol_iterator::operator==(const symbol_iterator &X) const { 137 return itr == X.itr; 138} 139 140bool SVal::symbol_iterator::operator!=(const symbol_iterator &X) const { 141 return itr != X.itr; 142} 143 144SVal::symbol_iterator::symbol_iterator(const SymExpr *SE) { 145 itr.push_back(SE); 146 while (!isa<SymbolData>(itr.back())) expand(); 147} 148 149SVal::symbol_iterator& SVal::symbol_iterator::operator++() { 150 assert(!itr.empty() && "attempting to iterate on an 'end' iterator"); 151 assert(isa<SymbolData>(itr.back())); 152 itr.pop_back(); 153 if (!itr.empty()) 154 while (!isa<SymbolData>(itr.back())) expand(); 155 return *this; 156} 157 158SymbolRef SVal::symbol_iterator::operator*() { 159 assert(!itr.empty() && "attempting to dereference an 'end' iterator"); 160 return cast<SymbolData>(itr.back()); 161} 162 163void SVal::symbol_iterator::expand() { 164 const SymExpr *SE = itr.back(); 165 itr.pop_back(); 166 167 if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) { 168 itr.push_back(SIE->getLHS()); 169 return; 170 } 171 else if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) { 172 itr.push_back(SSE->getLHS()); 173 itr.push_back(SSE->getRHS()); 174 return; 175 } 176 177 assert(false && "unhandled expansion case"); 178} 179 180const void *nonloc::LazyCompoundVal::getStore() const { 181 return static_cast<const LazyCompoundValData*>(Data)->getStore(); 182} 183 184const TypedRegion *nonloc::LazyCompoundVal::getRegion() const { 185 return static_cast<const LazyCompoundValData*>(Data)->getRegion(); 186} 187 188//===----------------------------------------------------------------------===// 189// Other Iterators. 190//===----------------------------------------------------------------------===// 191 192nonloc::CompoundVal::iterator nonloc::CompoundVal::begin() const { 193 return getValue()->begin(); 194} 195 196nonloc::CompoundVal::iterator nonloc::CompoundVal::end() const { 197 return getValue()->end(); 198} 199 200//===----------------------------------------------------------------------===// 201// Useful predicates. 202//===----------------------------------------------------------------------===// 203 204bool SVal::isConstant() const { 205 return isa<nonloc::ConcreteInt>(this) || isa<loc::ConcreteInt>(this); 206} 207 208bool SVal::isConstant(int I) const { 209 if (isa<loc::ConcreteInt>(*this)) 210 return cast<loc::ConcreteInt>(*this).getValue() == I; 211 else if (isa<nonloc::ConcreteInt>(*this)) 212 return cast<nonloc::ConcreteInt>(*this).getValue() == I; 213 else 214 return false; 215} 216 217bool SVal::isZeroConstant() const { 218 return isConstant(0); 219} 220 221 222//===----------------------------------------------------------------------===// 223// Transfer function dispatch for Non-Locs. 224//===----------------------------------------------------------------------===// 225 226SVal nonloc::ConcreteInt::evalBinOp(SValBuilder &svalBuilder, 227 BinaryOperator::Opcode Op, 228 const nonloc::ConcreteInt& R) const { 229 const llvm::APSInt* X = 230 svalBuilder.getBasicValueFactory().evalAPSInt(Op, getValue(), R.getValue()); 231 232 if (X) 233 return nonloc::ConcreteInt(*X); 234 else 235 return UndefinedVal(); 236} 237 238nonloc::ConcreteInt 239nonloc::ConcreteInt::evalComplement(SValBuilder &svalBuilder) const { 240 return svalBuilder.makeIntVal(~getValue()); 241} 242 243nonloc::ConcreteInt 244nonloc::ConcreteInt::evalMinus(SValBuilder &svalBuilder) const { 245 return svalBuilder.makeIntVal(-getValue()); 246} 247 248//===----------------------------------------------------------------------===// 249// Transfer function dispatch for Locs. 250//===----------------------------------------------------------------------===// 251 252SVal loc::ConcreteInt::evalBinOp(BasicValueFactory& BasicVals, 253 BinaryOperator::Opcode Op, 254 const loc::ConcreteInt& R) const { 255 256 assert (Op == BO_Add || Op == BO_Sub || 257 (Op >= BO_LT && Op <= BO_NE)); 258 259 const llvm::APSInt* X = BasicVals.evalAPSInt(Op, getValue(), R.getValue()); 260 261 if (X) 262 return loc::ConcreteInt(*X); 263 else 264 return UndefinedVal(); 265} 266 267//===----------------------------------------------------------------------===// 268// Pretty-Printing. 269//===----------------------------------------------------------------------===// 270 271void SVal::dump() const { dumpToStream(llvm::errs()); } 272 273void SVal::dumpToStream(llvm::raw_ostream& os) const { 274 switch (getBaseKind()) { 275 case UnknownKind: 276 os << "Unknown"; 277 break; 278 case NonLocKind: 279 cast<NonLoc>(this)->dumpToStream(os); 280 break; 281 case LocKind: 282 cast<Loc>(this)->dumpToStream(os); 283 break; 284 case UndefinedKind: 285 os << "Undefined"; 286 break; 287 default: 288 assert (false && "Invalid SVal."); 289 } 290} 291 292void NonLoc::dumpToStream(llvm::raw_ostream& os) const { 293 switch (getSubKind()) { 294 case nonloc::ConcreteIntKind: { 295 const nonloc::ConcreteInt& C = *cast<nonloc::ConcreteInt>(this); 296 if (C.getValue().isUnsigned()) 297 os << C.getValue().getZExtValue(); 298 else 299 os << C.getValue().getSExtValue(); 300 os << ' ' << (C.getValue().isUnsigned() ? 'U' : 'S') 301 << C.getValue().getBitWidth() << 'b'; 302 break; 303 } 304 case nonloc::SymbolValKind: 305 os << '$' << cast<nonloc::SymbolVal>(this)->getSymbol(); 306 break; 307 case nonloc::SymExprValKind: { 308 const nonloc::SymExprVal& C = *cast<nonloc::SymExprVal>(this); 309 const SymExpr *SE = C.getSymbolicExpression(); 310 os << SE; 311 break; 312 } 313 case nonloc::LocAsIntegerKind: { 314 const nonloc::LocAsInteger& C = *cast<nonloc::LocAsInteger>(this); 315 os << C.getLoc() << " [as " << C.getNumBits() << " bit integer]"; 316 break; 317 } 318 case nonloc::CompoundValKind: { 319 const nonloc::CompoundVal& C = *cast<nonloc::CompoundVal>(this); 320 os << "compoundVal{"; 321 bool first = true; 322 for (nonloc::CompoundVal::iterator I=C.begin(), E=C.end(); I!=E; ++I) { 323 if (first) { 324 os << ' '; first = false; 325 } 326 else 327 os << ", "; 328 329 (*I).dumpToStream(os); 330 } 331 os << "}"; 332 break; 333 } 334 case nonloc::LazyCompoundValKind: { 335 const nonloc::LazyCompoundVal &C = *cast<nonloc::LazyCompoundVal>(this); 336 os << "lazyCompoundVal{" << const_cast<void *>(C.getStore()) 337 << ',' << C.getRegion() 338 << '}'; 339 break; 340 } 341 default: 342 assert (false && "Pretty-printed not implemented for this NonLoc."); 343 break; 344 } 345} 346 347void Loc::dumpToStream(llvm::raw_ostream& os) const { 348 switch (getSubKind()) { 349 case loc::ConcreteIntKind: 350 os << cast<loc::ConcreteInt>(this)->getValue().getZExtValue() << " (Loc)"; 351 break; 352 case loc::GotoLabelKind: 353 os << "&&" << cast<loc::GotoLabel>(this)->getLabel()->getName(); 354 break; 355 case loc::MemRegionKind: 356 os << '&' << cast<loc::MemRegionVal>(this)->getRegion()->getString(); 357 break; 358 case loc::ObjCPropRefKind: { 359 const ObjCPropertyRefExpr *E = cast<loc::ObjCPropRef>(this)->getPropRefExpr(); 360 os << "objc-prop{"; 361 if (E->isSuperReceiver()) 362 os << "super."; 363 else if (E->getBase()) 364 os << "<base>."; 365 366 if (E->isImplicitProperty()) 367 os << E->getImplicitPropertyGetter()->getSelector().getAsString(); 368 else 369 os << E->getExplicitProperty()->getName(); 370 371 os << "}"; 372 break; 373 } 374 default: 375 assert(false && "Pretty-printing not implemented for this Loc."); 376 break; 377 } 378} 379