contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/Store.cpp

   1 //== Store.cpp - Interface for maps from Locations to Values ----*- 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 defined the types Store and StoreManager.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
  15 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  16 #include "clang/AST/CharUnits.h"
  17 #include "clang/AST/DeclObjC.h"
  18
  19 using namespace clang;
  20 using namespace ento;
  21
  22 StoreManager::StoreManager(ProgramStateManager &stateMgr)
  23   : svalBuilder(stateMgr.getSValBuilder()), StateMgr(stateMgr),
  24     MRMgr(svalBuilder.getRegionManager()), Ctx(stateMgr.getContext()) {}
  25
  26 StoreRef StoreManager::enterStackFrame(ProgramStateRef state,
  27                                        const LocationContext *callerCtx,
  28                                        const StackFrameContext *calleeCtx) {
  29   return StoreRef(state->getStore(), *this);
  30 }
  31
  32 const MemRegion *StoreManager::MakeElementRegion(const MemRegion *Base,
  33                                               QualType EleTy, uint64_t index) {
  34   NonLoc idx = svalBuilder.makeArrayIndex(index);
  35   return MRMgr.getElementRegion(EleTy, idx, Base, svalBuilder.getContext());
  36 }
  37
  38 // FIXME: Merge with the implementation of the same method in MemRegion.cpp
  39 static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
  40   if (const RecordType *RT = Ty->getAs<RecordType>()) {
  41     const RecordDecl *D = RT->getDecl();
  42     if (!D->getDefinition())
  43       return false;
  44   }
  45
  46   return true;
  47 }
  48
  49 StoreRef StoreManager::BindDefault(Store store, const MemRegion *R, SVal V) {
  50   return StoreRef(store, *this);
  51 }
  52
  53 const ElementRegion *StoreManager::GetElementZeroRegion(const MemRegion *R,
  54                                                         QualType T) {
  55   NonLoc idx = svalBuilder.makeZeroArrayIndex();
  56   assert(!T.isNull());
  57   return MRMgr.getElementRegion(T, idx, R, Ctx);
  58 }
  59
  60 const MemRegion *StoreManager::castRegion(const MemRegion *R, QualType CastToTy) {
  61
  62   ASTContext &Ctx = StateMgr.getContext();
  63
  64   // Handle casts to Objective-C objects.
  65   if (CastToTy->isObjCObjectPointerType())
  66     return R->StripCasts();
  67
  68   if (CastToTy->isBlockPointerType()) {
  69     // FIXME: We may need different solutions, depending on the symbol
  70     // involved.  Blocks can be casted to/from 'id', as they can be treated
  71     // as Objective-C objects.  This could possibly be handled by enhancing
  72     // our reasoning of downcasts of symbolic objects.
  73     if (isa<CodeTextRegion>(R) || isa<SymbolicRegion>(R))
  74       return R;
  75
  76     // We don't know what to make of it.  Return a NULL region, which
  77     // will be interpretted as UnknownVal.
  78     return NULL;
  79   }
  80
  81   // Now assume we are casting from pointer to pointer. Other cases should
  82   // already be handled.
  83   QualType PointeeTy = CastToTy->getPointeeType();
  84   QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy);
  85
  86   // Handle casts to void*.  We just pass the region through.
  87   if (CanonPointeeTy.getLocalUnqualifiedType() == Ctx.VoidTy)
  88     return R;
  89
  90   // Handle casts from compatible types.
  91   if (R->isBoundable())
  92     if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) {
  93       QualType ObjTy = Ctx.getCanonicalType(TR->getValueType());
  94       if (CanonPointeeTy == ObjTy)
  95         return R;
  96     }
  97
  98   // Process region cast according to the kind of the region being cast.
  99   switch (R->getKind()) {
 100     case MemRegion::CXXThisRegionKind:
 101     case MemRegion::GenericMemSpaceRegionKind:
 102     case MemRegion::StackLocalsSpaceRegionKind:
 103     case MemRegion::StackArgumentsSpaceRegionKind:
 104     case MemRegion::HeapSpaceRegionKind:
 105     case MemRegion::UnknownSpaceRegionKind:
 106     case MemRegion::StaticGlobalSpaceRegionKind:
 107     case MemRegion::GlobalInternalSpaceRegionKind:
 108     case MemRegion::GlobalSystemSpaceRegionKind:
 109     case MemRegion::GlobalImmutableSpaceRegionKind: {
 110       llvm_unreachable("Invalid region cast");
 111     }
 112
 113     case MemRegion::FunctionTextRegionKind:
 114     case MemRegion::BlockTextRegionKind:
 115     case MemRegion::BlockDataRegionKind:
 116     case MemRegion::StringRegionKind:
 117       // FIXME: Need to handle arbitrary downcasts.
 118     case MemRegion::SymbolicRegionKind:
 119     case MemRegion::AllocaRegionKind:
 120     case MemRegion::CompoundLiteralRegionKind:
 121     case MemRegion::FieldRegionKind:
 122     case MemRegion::ObjCIvarRegionKind:
 123     case MemRegion::ObjCStringRegionKind:
 124     case MemRegion::VarRegionKind:
 125     case MemRegion::CXXTempObjectRegionKind:
 126     case MemRegion::CXXBaseObjectRegionKind:
 127       return MakeElementRegion(R, PointeeTy);
 128
 129     case MemRegion::ElementRegionKind: {
 130       // If we are casting from an ElementRegion to another type, the
 131       // algorithm is as follows:
 132       //
 133       // (1) Compute the "raw offset" of the ElementRegion from the
 134       //     base region.  This is done by calling 'getAsRawOffset()'.
 135       //
 136       // (2a) If we get a 'RegionRawOffset' after calling
 137       //      'getAsRawOffset()', determine if the absolute offset
 138       //      can be exactly divided into chunks of the size of the
 139       //      casted-pointee type.  If so, create a new ElementRegion with
 140       //      the pointee-cast type as the new ElementType and the index
 141       //      being the offset divded by the chunk size.  If not, create
 142       //      a new ElementRegion at offset 0 off the raw offset region.
 143       //
 144       // (2b) If we don't a get a 'RegionRawOffset' after calling
 145       //      'getAsRawOffset()', it means that we are at offset 0.
 146       //
 147       // FIXME: Handle symbolic raw offsets.
 148
 149       const ElementRegion *elementR = cast<ElementRegion>(R);
 150       const RegionRawOffset &rawOff = elementR->getAsArrayOffset();
 151       const MemRegion *baseR = rawOff.getRegion();
 152
 153       // If we cannot compute a raw offset, throw up our hands and return
 154       // a NULL MemRegion*.
 155       if (!baseR)
 156         return NULL;
 157
 158       CharUnits off = rawOff.getOffset();
 159
 160       if (off.isZero()) {
 161         // Edge case: we are at 0 bytes off the beginning of baseR.  We
 162         // check to see if type we are casting to is the same as the base
 163         // region.  If so, just return the base region.
 164         if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(baseR)) {
 165           QualType ObjTy = Ctx.getCanonicalType(TR->getValueType());
 166           QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy);
 167           if (CanonPointeeTy == ObjTy)
 168             return baseR;
 169         }
 170
 171         // Otherwise, create a new ElementRegion at offset 0.
 172         return MakeElementRegion(baseR, PointeeTy);
 173       }
 174
 175       // We have a non-zero offset from the base region.  We want to determine
 176       // if the offset can be evenly divided by sizeof(PointeeTy).  If so,
 177       // we create an ElementRegion whose index is that value.  Otherwise, we
 178       // create two ElementRegions, one that reflects a raw offset and the other
 179       // that reflects the cast.
 180
 181       // Compute the index for the new ElementRegion.
 182       int64_t newIndex = 0;
 183       const MemRegion *newSuperR = 0;
 184
 185       // We can only compute sizeof(PointeeTy) if it is a complete type.
 186       if (IsCompleteType(Ctx, PointeeTy)) {
 187         // Compute the size in **bytes**.
 188         CharUnits pointeeTySize = Ctx.getTypeSizeInChars(PointeeTy);
 189         if (!pointeeTySize.isZero()) {
 190           // Is the offset a multiple of the size?  If so, we can layer the
 191           // ElementRegion (with elementType == PointeeTy) directly on top of
 192           // the base region.
 193           if (off % pointeeTySize == 0) {
 194             newIndex = off / pointeeTySize;
 195             newSuperR = baseR;
 196           }
 197         }
 198       }
 199
 200       if (!newSuperR) {
 201         // Create an intermediate ElementRegion to represent the raw byte.
 202         // This will be the super region of the final ElementRegion.
 203         newSuperR = MakeElementRegion(baseR, Ctx.CharTy, off.getQuantity());
 204       }
 205
 206       return MakeElementRegion(newSuperR, PointeeTy, newIndex);
 207     }
 208   }
 209
 210   llvm_unreachable("unreachable");
 211 }
 212
 213
 214 /// CastRetrievedVal - Used by subclasses of StoreManager to implement
 215 ///  implicit casts that arise from loads from regions that are reinterpreted
 216 ///  as another region.
 217 SVal StoreManager::CastRetrievedVal(SVal V, const TypedValueRegion *R,
 218                                     QualType castTy, bool performTestOnly) {
 219
 220   if (castTy.isNull() || V.isUnknownOrUndef())
 221     return V;
 222
 223   ASTContext &Ctx = svalBuilder.getContext();
 224
 225   if (performTestOnly) {
 226     // Automatically translate references to pointers.
 227     QualType T = R->getValueType();
 228     if (const ReferenceType *RT = T->getAs<ReferenceType>())
 229       T = Ctx.getPointerType(RT->getPointeeType());
 230
 231     assert(svalBuilder.getContext().hasSameUnqualifiedType(castTy, T));
 232     return V;
 233   }
 234
 235   return svalBuilder.dispatchCast(V, castTy);
 236 }
 237
 238 SVal StoreManager::getLValueFieldOrIvar(const Decl *D, SVal Base) {
 239   if (Base.isUnknownOrUndef())
 240     return Base;
 241
 242   Loc BaseL = cast<Loc>(Base);
 243   const MemRegion* BaseR = 0;
 244
 245   switch (BaseL.getSubKind()) {
 246   case loc::MemRegionKind:
 247     BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
 248     break;
 249
 250   case loc::GotoLabelKind:
 251     // These are anormal cases. Flag an undefined value.
 252     return UndefinedVal();
 253
 254   case loc::ConcreteIntKind:
 255     // While these seem funny, this can happen through casts.
 256     // FIXME: What we should return is the field offset.  For example,
 257     //  add the field offset to the integer value.  That way funny things
 258     //  like this work properly:  &(((struct foo *) 0xa)->f)
 259     return Base;
 260
 261   default:
 262     llvm_unreachable("Unhandled Base.");
 263   }
 264
 265   // NOTE: We must have this check first because ObjCIvarDecl is a subclass
 266   // of FieldDecl.
 267   if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D))
 268     return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR));
 269
 270   return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR));
 271 }
 272
 273 SVal StoreManager::getLValueIvar(const ObjCIvarDecl *decl, SVal base) {
 274   return getLValueFieldOrIvar(decl, base);
 275 }
 276
 277 SVal StoreManager::getLValueElement(QualType elementType, NonLoc Offset,
 278                                     SVal Base) {
 279
 280   // If the base is an unknown or undefined value, just return it back.
 281   // FIXME: For absolute pointer addresses, we just return that value back as
 282   //  well, although in reality we should return the offset added to that
 283   //  value.
 284   if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base))
 285     return Base;
 286
 287   const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion();
 288
 289   // Pointer of any type can be cast and used as array base.
 290   const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion);
 291
 292   // Convert the offset to the appropriate size and signedness.
 293   Offset = cast<NonLoc>(svalBuilder.convertToArrayIndex(Offset));
 294
 295   if (!ElemR) {
 296     //
 297     // If the base region is not an ElementRegion, create one.
 298     // This can happen in the following example:
 299     //
 300     //   char *p = __builtin_alloc(10);
 301     //   p[1] = 8;
 302     //
 303     //  Observe that 'p' binds to an AllocaRegion.
 304     //
 305     return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
 306                                                     BaseRegion, Ctx));
 307   }
 308
 309   SVal BaseIdx = ElemR->getIndex();
 310
 311   if (!isa<nonloc::ConcreteInt>(BaseIdx))
 312     return UnknownVal();
 313
 314   const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
 315
 316   // Only allow non-integer offsets if the base region has no offset itself.
 317   // FIXME: This is a somewhat arbitrary restriction. We should be using
 318   // SValBuilder here to add the two offsets without checking their types.
 319   if (!isa<nonloc::ConcreteInt>(Offset)) {
 320     if (isa<ElementRegion>(BaseRegion->StripCasts()))
 321       return UnknownVal();
 322
 323     return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
 324                                                     ElemR->getSuperRegion(),
 325                                                     Ctx));
 326   }
 327
 328   const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
 329   assert(BaseIdxI.isSigned());
 330
 331   // Compute the new index.
 332   nonloc::ConcreteInt NewIdx(svalBuilder.getBasicValueFactory().getValue(BaseIdxI +
 333                                                                     OffI));
 334
 335   // Construct the new ElementRegion.
 336   const MemRegion *ArrayR = ElemR->getSuperRegion();
 337   return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR,
 338                                                   Ctx));
 339 }
 340
 341 StoreManager::BindingsHandler::~BindingsHandler() {}
 342
 343 bool StoreManager::FindUniqueBinding::HandleBinding(StoreManager& SMgr,
 344                                                     Store store,
 345                                                     const MemRegion* R,
 346                                                     SVal val) {
 347   SymbolRef SymV = val.getAsLocSymbol();
 348   if (!SymV || SymV != Sym)
 349     return true;
 350
 351   if (Binding) {
 352     First = false;
 353     return false;
 354   }
 355   else
 356     Binding = R;
 357
 358   return true;
 359 }
 360
 361 void SubRegionMap::anchor() { }
 362 void SubRegionMap::Visitor::anchor() { }