1218887Sdim//= RValues.cpp - Abstract RValues for Path-Sens. Value Tracking -*- C++ -*-==// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defines SVal, Loc, and NonLoc, classes that represent 11218887Sdim// abstract r-values for use with path-sensitive value tracking. 12218887Sdim// 13218887Sdim//===----------------------------------------------------------------------===// 14218887Sdim 15226633Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 16218887Sdim#include "clang/AST/ExprObjC.h" 17218887Sdim#include "clang/Basic/IdentifierTable.h" 18249423Sdim#include "llvm/Support/raw_ostream.h" 19218887Sdimusing namespace clang; 20218887Sdimusing namespace ento; 21218887Sdimusing llvm::APSInt; 22218887Sdim 23218887Sdim//===----------------------------------------------------------------------===// 24218887Sdim// Symbol iteration within an SVal. 25218887Sdim//===----------------------------------------------------------------------===// 26218887Sdim 27218887Sdim 28218887Sdim//===----------------------------------------------------------------------===// 29218887Sdim// Utility methods. 30218887Sdim//===----------------------------------------------------------------------===// 31218887Sdim 32218887Sdimbool SVal::hasConjuredSymbol() const { 33249423Sdim if (Optional<nonloc::SymbolVal> SV = getAs<nonloc::SymbolVal>()) { 34218887Sdim SymbolRef sym = SV->getSymbol(); 35218887Sdim if (isa<SymbolConjured>(sym)) 36218887Sdim return true; 37218887Sdim } 38218887Sdim 39249423Sdim if (Optional<loc::MemRegionVal> RV = getAs<loc::MemRegionVal>()) { 40218887Sdim const MemRegion *R = RV->getRegion(); 41218887Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 42218887Sdim SymbolRef sym = SR->getSymbol(); 43218887Sdim if (isa<SymbolConjured>(sym)) 44218887Sdim return true; 45218887Sdim } 46218887Sdim } 47218887Sdim 48218887Sdim return false; 49218887Sdim} 50218887Sdim 51218887Sdimconst FunctionDecl *SVal::getAsFunctionDecl() const { 52249423Sdim if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>()) { 53218887Sdim const MemRegion* R = X->getRegion(); 54218887Sdim if (const FunctionTextRegion *CTR = R->getAs<FunctionTextRegion>()) 55243830Sdim if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CTR->getDecl())) 56243830Sdim return FD; 57218887Sdim } 58218887Sdim 59234353Sdim return 0; 60218887Sdim} 61218887Sdim 62234353Sdim/// \brief If this SVal is a location (subclasses Loc) and wraps a symbol, 63234353Sdim/// return that SymbolRef. Otherwise return 0. 64234353Sdim/// 65234353Sdim/// Implicit casts (ex: void* -> char*) can turn Symbolic region into Element 66234353Sdim/// region. If that is the case, gets the underlining region. 67251662Sdim/// When IncludeBaseRegions is set to true and the SubRegion is non-symbolic, 68251662Sdim/// the first symbolic parent region is returned. 69251662SdimSymbolRef SVal::getAsLocSymbol(bool IncludeBaseRegions) const { 70234353Sdim // FIXME: should we consider SymbolRef wrapped in CodeTextRegion? 71249423Sdim if (Optional<nonloc::LocAsInteger> X = getAs<nonloc::LocAsInteger>()) 72218887Sdim return X->getLoc().getAsLocSymbol(); 73218887Sdim 74249423Sdim if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>()) { 75251662Sdim const MemRegion *R = X->getRegion(); 76251662Sdim if (const SymbolicRegion *SymR = IncludeBaseRegions ? 77251662Sdim R->getSymbolicBase() : 78251662Sdim dyn_cast<SymbolicRegion>(R->StripCasts())) 79218887Sdim return SymR->getSymbol(); 80218887Sdim } 81234353Sdim return 0; 82218887Sdim} 83218887Sdim 84218887Sdim/// Get the symbol in the SVal or its base region. 85218887SdimSymbolRef SVal::getLocSymbolInBase() const { 86249423Sdim Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>(); 87218887Sdim 88218887Sdim if (!X) 89218887Sdim return 0; 90218887Sdim 91218887Sdim const MemRegion *R = X->getRegion(); 92218887Sdim 93218887Sdim while (const SubRegion *SR = dyn_cast<SubRegion>(R)) { 94218887Sdim if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(SR)) 95218887Sdim return SymR->getSymbol(); 96218887Sdim else 97218887Sdim R = SR->getSuperRegion(); 98218887Sdim } 99218887Sdim 100218887Sdim return 0; 101218887Sdim} 102218887Sdim 103234353Sdim// TODO: The next 3 functions have to be simplified. 104234353Sdim 105234353Sdim/// \brief If this SVal wraps a symbol return that SymbolRef. 106251662Sdim/// Otherwise, return 0. 107251662Sdim/// 108251662Sdim/// Casts are ignored during lookup. 109251662Sdim/// \param IncludeBaseRegions The boolean that controls whether the search 110251662Sdim/// should continue to the base regions if the region is not symbolic. 111251662SdimSymbolRef SVal::getAsSymbol(bool IncludeBaseRegion) const { 112234353Sdim // FIXME: should we consider SymbolRef wrapped in CodeTextRegion? 113249423Sdim if (Optional<nonloc::SymbolVal> X = getAs<nonloc::SymbolVal>()) 114218887Sdim return X->getSymbol(); 115218887Sdim 116251662Sdim return getAsLocSymbol(IncludeBaseRegion); 117218887Sdim} 118218887Sdim 119218887Sdim/// getAsSymbolicExpression - If this Sval wraps a symbolic expression then 120218887Sdim/// return that expression. Otherwise return NULL. 121218887Sdimconst SymExpr *SVal::getAsSymbolicExpression() const { 122249423Sdim if (Optional<nonloc::SymbolVal> X = getAs<nonloc::SymbolVal>()) 123234353Sdim return X->getSymbol(); 124218887Sdim 125218887Sdim return getAsSymbol(); 126218887Sdim} 127218887Sdim 128234353Sdimconst SymExpr* SVal::getAsSymExpr() const { 129234353Sdim const SymExpr* Sym = getAsSymbol(); 130234353Sdim if (!Sym) 131234353Sdim Sym = getAsSymbolicExpression(); 132234353Sdim return Sym; 133234353Sdim} 134234353Sdim 135218887Sdimconst MemRegion *SVal::getAsRegion() const { 136249423Sdim if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>()) 137218887Sdim return X->getRegion(); 138218887Sdim 139249423Sdim if (Optional<nonloc::LocAsInteger> X = getAs<nonloc::LocAsInteger>()) 140218887Sdim return X->getLoc().getAsRegion(); 141218887Sdim 142218887Sdim return 0; 143218887Sdim} 144218887Sdim 145239462Sdimconst MemRegion *loc::MemRegionVal::stripCasts(bool StripBaseCasts) const { 146218887Sdim const MemRegion *R = getRegion(); 147239462Sdim return R ? R->StripCasts(StripBaseCasts) : NULL; 148218887Sdim} 149218887Sdim 150218887Sdimconst void *nonloc::LazyCompoundVal::getStore() const { 151218887Sdim return static_cast<const LazyCompoundValData*>(Data)->getStore(); 152218887Sdim} 153218887Sdim 154249423Sdimconst TypedValueRegion *nonloc::LazyCompoundVal::getRegion() const { 155218887Sdim return static_cast<const LazyCompoundValData*>(Data)->getRegion(); 156218887Sdim} 157218887Sdim 158218887Sdim//===----------------------------------------------------------------------===// 159218887Sdim// Other Iterators. 160218887Sdim//===----------------------------------------------------------------------===// 161218887Sdim 162218887Sdimnonloc::CompoundVal::iterator nonloc::CompoundVal::begin() const { 163218887Sdim return getValue()->begin(); 164218887Sdim} 165218887Sdim 166218887Sdimnonloc::CompoundVal::iterator nonloc::CompoundVal::end() const { 167218887Sdim return getValue()->end(); 168218887Sdim} 169218887Sdim 170218887Sdim//===----------------------------------------------------------------------===// 171218887Sdim// Useful predicates. 172218887Sdim//===----------------------------------------------------------------------===// 173218887Sdim 174218887Sdimbool SVal::isConstant() const { 175249423Sdim return getAs<nonloc::ConcreteInt>() || getAs<loc::ConcreteInt>(); 176218887Sdim} 177218887Sdim 178218887Sdimbool SVal::isConstant(int I) const { 179249423Sdim if (Optional<loc::ConcreteInt> LV = getAs<loc::ConcreteInt>()) 180249423Sdim return LV->getValue() == I; 181249423Sdim if (Optional<nonloc::ConcreteInt> NV = getAs<nonloc::ConcreteInt>()) 182249423Sdim return NV->getValue() == I; 183249423Sdim return false; 184218887Sdim} 185218887Sdim 186218887Sdimbool SVal::isZeroConstant() const { 187218887Sdim return isConstant(0); 188218887Sdim} 189218887Sdim 190218887Sdim 191218887Sdim//===----------------------------------------------------------------------===// 192218887Sdim// Transfer function dispatch for Non-Locs. 193218887Sdim//===----------------------------------------------------------------------===// 194218887Sdim 195218887SdimSVal nonloc::ConcreteInt::evalBinOp(SValBuilder &svalBuilder, 196218887Sdim BinaryOperator::Opcode Op, 197218887Sdim const nonloc::ConcreteInt& R) const { 198218887Sdim const llvm::APSInt* X = 199218887Sdim svalBuilder.getBasicValueFactory().evalAPSInt(Op, getValue(), R.getValue()); 200218887Sdim 201218887Sdim if (X) 202218887Sdim return nonloc::ConcreteInt(*X); 203218887Sdim else 204218887Sdim return UndefinedVal(); 205218887Sdim} 206218887Sdim 207218887Sdimnonloc::ConcreteInt 208218887Sdimnonloc::ConcreteInt::evalComplement(SValBuilder &svalBuilder) const { 209218887Sdim return svalBuilder.makeIntVal(~getValue()); 210218887Sdim} 211218887Sdim 212218887Sdimnonloc::ConcreteInt 213218887Sdimnonloc::ConcreteInt::evalMinus(SValBuilder &svalBuilder) const { 214218887Sdim return svalBuilder.makeIntVal(-getValue()); 215218887Sdim} 216218887Sdim 217218887Sdim//===----------------------------------------------------------------------===// 218218887Sdim// Transfer function dispatch for Locs. 219218887Sdim//===----------------------------------------------------------------------===// 220218887Sdim 221218887SdimSVal loc::ConcreteInt::evalBinOp(BasicValueFactory& BasicVals, 222218887Sdim BinaryOperator::Opcode Op, 223218887Sdim const loc::ConcreteInt& R) const { 224218887Sdim 225249423Sdim assert(BinaryOperator::isComparisonOp(Op) || Op == BO_Sub); 226218887Sdim 227249423Sdim const llvm::APSInt *X = BasicVals.evalAPSInt(Op, getValue(), R.getValue()); 228218887Sdim 229218887Sdim if (X) 230249423Sdim return nonloc::ConcreteInt(*X); 231218887Sdim else 232218887Sdim return UndefinedVal(); 233218887Sdim} 234218887Sdim 235218887Sdim//===----------------------------------------------------------------------===// 236218887Sdim// Pretty-Printing. 237218887Sdim//===----------------------------------------------------------------------===// 238218887Sdim 239218887Sdimvoid SVal::dump() const { dumpToStream(llvm::errs()); } 240218887Sdim 241226633Sdimvoid SVal::dumpToStream(raw_ostream &os) const { 242218887Sdim switch (getBaseKind()) { 243218887Sdim case UnknownKind: 244218887Sdim os << "Unknown"; 245218887Sdim break; 246218887Sdim case NonLocKind: 247249423Sdim castAs<NonLoc>().dumpToStream(os); 248218887Sdim break; 249218887Sdim case LocKind: 250249423Sdim castAs<Loc>().dumpToStream(os); 251218887Sdim break; 252218887Sdim case UndefinedKind: 253218887Sdim os << "Undefined"; 254218887Sdim break; 255218887Sdim } 256218887Sdim} 257218887Sdim 258226633Sdimvoid NonLoc::dumpToStream(raw_ostream &os) const { 259218887Sdim switch (getSubKind()) { 260218887Sdim case nonloc::ConcreteIntKind: { 261249423Sdim const nonloc::ConcreteInt& C = castAs<nonloc::ConcreteInt>(); 262218887Sdim if (C.getValue().isUnsigned()) 263218887Sdim os << C.getValue().getZExtValue(); 264218887Sdim else 265218887Sdim os << C.getValue().getSExtValue(); 266218887Sdim os << ' ' << (C.getValue().isUnsigned() ? 'U' : 'S') 267218887Sdim << C.getValue().getBitWidth() << 'b'; 268218887Sdim break; 269218887Sdim } 270234353Sdim case nonloc::SymbolValKind: { 271249423Sdim os << castAs<nonloc::SymbolVal>().getSymbol(); 272218887Sdim break; 273218887Sdim } 274218887Sdim case nonloc::LocAsIntegerKind: { 275249423Sdim const nonloc::LocAsInteger& C = castAs<nonloc::LocAsInteger>(); 276218887Sdim os << C.getLoc() << " [as " << C.getNumBits() << " bit integer]"; 277218887Sdim break; 278218887Sdim } 279218887Sdim case nonloc::CompoundValKind: { 280249423Sdim const nonloc::CompoundVal& C = castAs<nonloc::CompoundVal>(); 281218887Sdim os << "compoundVal{"; 282218887Sdim bool first = true; 283218887Sdim for (nonloc::CompoundVal::iterator I=C.begin(), E=C.end(); I!=E; ++I) { 284218887Sdim if (first) { 285218887Sdim os << ' '; first = false; 286218887Sdim } 287218887Sdim else 288218887Sdim os << ", "; 289218887Sdim 290218887Sdim (*I).dumpToStream(os); 291218887Sdim } 292218887Sdim os << "}"; 293218887Sdim break; 294218887Sdim } 295218887Sdim case nonloc::LazyCompoundValKind: { 296249423Sdim const nonloc::LazyCompoundVal &C = castAs<nonloc::LazyCompoundVal>(); 297218887Sdim os << "lazyCompoundVal{" << const_cast<void *>(C.getStore()) 298218887Sdim << ',' << C.getRegion() 299218887Sdim << '}'; 300218887Sdim break; 301218887Sdim } 302218887Sdim default: 303218887Sdim assert (false && "Pretty-printed not implemented for this NonLoc."); 304218887Sdim break; 305218887Sdim } 306218887Sdim} 307218887Sdim 308226633Sdimvoid Loc::dumpToStream(raw_ostream &os) const { 309218887Sdim switch (getSubKind()) { 310218887Sdim case loc::ConcreteIntKind: 311249423Sdim os << castAs<loc::ConcreteInt>().getValue().getZExtValue() << " (Loc)"; 312218887Sdim break; 313218887Sdim case loc::GotoLabelKind: 314249423Sdim os << "&&" << castAs<loc::GotoLabel>().getLabel()->getName(); 315218887Sdim break; 316218887Sdim case loc::MemRegionKind: 317249423Sdim os << '&' << castAs<loc::MemRegionVal>().getRegion()->getString(); 318218887Sdim break; 319218887Sdim default: 320226633Sdim llvm_unreachable("Pretty-printing not implemented for this Loc."); 321218887Sdim } 322218887Sdim} 323