lib/Checker/SValBuilder.cpp

   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/GR/PathSensitive/MemRegion.h"
  16 #include "clang/GR/PathSensitive/SVals.h"
  17 #include "clang/GR/PathSensitive/SValBuilder.h"
  18 #include "clang/GR/PathSensitive/GRState.h"
  19 #include "clang/GR/PathSensitive/BasicValueFactory.h"
  20
  21 using namespace clang;
  22
  23 //===----------------------------------------------------------------------===//
  24 // Basic SVal creation.
  25 //===----------------------------------------------------------------------===//
  26
  27 DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType T) {
  28   if (Loc::IsLocType(T))
  29     return makeNull();
  30
  31   if (T->isIntegerType())
  32     return makeIntVal(0, T);
  33
  34   // FIXME: Handle floats.
  35   // FIXME: Handle structs.
  36   return UnknownVal();
  37 }
  38
  39
  40 NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
  41                                 const llvm::APSInt& v, QualType T) {
  42   // The Environment ensures we always get a persistent APSInt in
  43   // BasicValueFactory, so we don't need to get the APSInt from
  44   // BasicValueFactory again.
  45   assert(!Loc::IsLocType(T));
  46   return nonloc::SymExprVal(SymMgr.getSymIntExpr(lhs, op, v, T));
  47 }
  48
  49 NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
  50                                 const SymExpr *rhs, QualType T) {
  51   assert(SymMgr.getType(lhs) == SymMgr.getType(rhs));
  52   assert(!Loc::IsLocType(T));
  53   return nonloc::SymExprVal(SymMgr.getSymSymExpr(lhs, op, rhs, T));
  54 }
  55
  56
  57 SVal SValBuilder::convertToArrayIndex(SVal V) {
  58   if (V.isUnknownOrUndef())
  59     return V;
  60
  61   // Common case: we have an appropriately sized integer.
  62   if (nonloc::ConcreteInt* CI = dyn_cast<nonloc::ConcreteInt>(&V)) {
  63     const llvm::APSInt& I = CI->getValue();
  64     if (I.getBitWidth() == ArrayIndexWidth && I.isSigned())
  65       return V;
  66   }
  67
  68   return evalCastNL(cast<NonLoc>(V), ArrayIndexTy);
  69 }
  70
  71 DefinedOrUnknownSVal
  72 SValBuilder::getRegionValueSymbolVal(const TypedRegion* R) {
  73   QualType T = R->getValueType();
  74
  75   if (!SymbolManager::canSymbolicate(T))
  76     return UnknownVal();
  77
  78   SymbolRef sym = SymMgr.getRegionValueSymbol(R);
  79
  80   if (Loc::IsLocType(T))
  81     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
  82
  83   return nonloc::SymbolVal(sym);
  84 }
  85
  86 DefinedOrUnknownSVal SValBuilder::getConjuredSymbolVal(const void *SymbolTag,
  87                                                         const Expr *E,
  88                                                         unsigned Count) {
  89   QualType T = E->getType();
  90
  91   if (!SymbolManager::canSymbolicate(T))
  92     return UnknownVal();
  93
  94   SymbolRef sym = SymMgr.getConjuredSymbol(E, Count, SymbolTag);
  95
  96   if (Loc::IsLocType(T))
  97     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
  98
  99   return nonloc::SymbolVal(sym);
 100 }
 101
 102 DefinedOrUnknownSVal SValBuilder::getConjuredSymbolVal(const void *SymbolTag,
 103                                                         const Expr *E,
 104                                                         QualType T,
 105                                                         unsigned Count) {
 106
 107   if (!SymbolManager::canSymbolicate(T))
 108     return UnknownVal();
 109
 110   SymbolRef sym = SymMgr.getConjuredSymbol(E, T, Count, SymbolTag);
 111
 112   if (Loc::IsLocType(T))
 113     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
 114
 115   return nonloc::SymbolVal(sym);
 116 }
 117
 118 DefinedSVal SValBuilder::getMetadataSymbolVal(const void *SymbolTag,
 119                                                const MemRegion *MR,
 120                                                const Expr *E, QualType T,
 121                                                unsigned Count) {
 122   assert(SymbolManager::canSymbolicate(T) && "Invalid metadata symbol type");
 123
 124   SymbolRef sym = SymMgr.getMetadataSymbol(MR, E, T, Count, SymbolTag);
 125
 126   if (Loc::IsLocType(T))
 127     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
 128
 129   return nonloc::SymbolVal(sym);
 130 }
 131
 132 DefinedOrUnknownSVal
 133 SValBuilder::getDerivedRegionValueSymbolVal(SymbolRef parentSymbol,
 134                                              const TypedRegion *R) {
 135   QualType T = R->getValueType();
 136
 137   if (!SymbolManager::canSymbolicate(T))
 138     return UnknownVal();
 139
 140   SymbolRef sym = SymMgr.getDerivedSymbol(parentSymbol, R);
 141
 142   if (Loc::IsLocType(T))
 143     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
 144
 145   return nonloc::SymbolVal(sym);
 146 }
 147
 148 DefinedSVal SValBuilder::getFunctionPointer(const FunctionDecl* FD) {
 149   return loc::MemRegionVal(MemMgr.getFunctionTextRegion(FD));
 150 }
 151
 152 DefinedSVal SValBuilder::getBlockPointer(const BlockDecl *D,
 153                                           CanQualType locTy,
 154                                           const LocationContext *LC) {
 155   const BlockTextRegion *BC =
 156     MemMgr.getBlockTextRegion(D, locTy, LC->getAnalysisContext());
 157   const BlockDataRegion *BD = MemMgr.getBlockDataRegion(BC, LC);
 158   return loc::MemRegionVal(BD);
 159 }
 160
 161 //===----------------------------------------------------------------------===//
 162
 163 SVal SValBuilder::evalBinOp(const GRState *ST, BinaryOperator::Opcode Op,
 164                           SVal L, SVal R, QualType T) {
 165
 166   if (L.isUndef() || R.isUndef())
 167     return UndefinedVal();
 168
 169   if (L.isUnknown() || R.isUnknown())
 170     return UnknownVal();
 171
 172   if (isa<Loc>(L)) {
 173     if (isa<Loc>(R))
 174       return evalBinOpLL(ST, Op, cast<Loc>(L), cast<Loc>(R), T);
 175
 176     return evalBinOpLN(ST, Op, cast<Loc>(L), cast<NonLoc>(R), T);
 177   }
 178
 179   if (isa<Loc>(R)) {
 180     // Support pointer arithmetic where the addend is on the left
 181     // and the pointer on the right.
 182     assert(Op == BO_Add);
 183
 184     // Commute the operands.
 185     return evalBinOpLN(ST, Op, cast<Loc>(R), cast<NonLoc>(L), T);
 186   }
 187
 188   return evalBinOpNN(ST, Op, cast<NonLoc>(L), cast<NonLoc>(R), T);
 189 }
 190
 191 DefinedOrUnknownSVal SValBuilder::evalEQ(const GRState *ST,
 192                                        DefinedOrUnknownSVal L,
 193                                        DefinedOrUnknownSVal R) {
 194   return cast<DefinedOrUnknownSVal>(evalBinOp(ST, BO_EQ, L, R,
 195                                               Context.IntTy));
 196 }
 197
 198 // FIXME: should rewrite according to the cast kind.
 199 SVal SValBuilder::evalCast(SVal val, QualType castTy, QualType originalTy) {
 200   if (val.isUnknownOrUndef() || castTy == originalTy)
 201     return val;
 202
 203   // For const casts, just propagate the value.
 204   if (!castTy->isVariableArrayType() && !originalTy->isVariableArrayType())
 205     if (Context.hasSameUnqualifiedType(castTy, originalTy))
 206       return val;
 207
 208   // Check for casts to real or complex numbers.  We don't handle these at all
 209   // right now.
 210   if (castTy->isFloatingType() || castTy->isAnyComplexType())
 211     return UnknownVal();
 212
 213   // Check for casts from integers to integers.
 214   if (castTy->isIntegerType() && originalTy->isIntegerType())
 215     return evalCastNL(cast<NonLoc>(val), castTy);
 216
 217   // Check for casts from pointers to integers.
 218   if (castTy->isIntegerType() && Loc::IsLocType(originalTy))
 219     return evalCastL(cast<Loc>(val), castTy);
 220
 221   // Check for casts from integers to pointers.
 222   if (Loc::IsLocType(castTy) && originalTy->isIntegerType()) {
 223     if (nonloc::LocAsInteger *LV = dyn_cast<nonloc::LocAsInteger>(&val)) {
 224       if (const MemRegion *R = LV->getLoc().getAsRegion()) {
 225         StoreManager &storeMgr = StateMgr.getStoreManager();
 226         R = storeMgr.CastRegion(R, castTy);
 227         return R ? SVal(loc::MemRegionVal(R)) : UnknownVal();
 228       }
 229       return LV->getLoc();
 230     }
 231     goto DispatchCast;
 232   }
 233
 234   // Just pass through function and block pointers.
 235   if (originalTy->isBlockPointerType() || originalTy->isFunctionPointerType()) {
 236     assert(Loc::IsLocType(castTy));
 237     return val;
 238   }
 239
 240   // Check for casts from array type to another type.
 241   if (originalTy->isArrayType()) {
 242     // We will always decay to a pointer.
 243     val = StateMgr.ArrayToPointer(cast<Loc>(val));
 244
 245     // Are we casting from an array to a pointer?  If so just pass on
 246     // the decayed value.
 247     if (castTy->isPointerType())
 248       return val;
 249
 250     // Are we casting from an array to an integer?  If so, cast the decayed
 251     // pointer value to an integer.
 252     assert(castTy->isIntegerType());
 253
 254     // FIXME: Keep these here for now in case we decide soon that we
 255     // need the original decayed type.
 256     //    QualType elemTy = cast<ArrayType>(originalTy)->getElementType();
 257     //    QualType pointerTy = C.getPointerType(elemTy);
 258     return evalCastL(cast<Loc>(val), castTy);
 259   }
 260
 261   // Check for casts from a region to a specific type.
 262   if (const MemRegion *R = val.getAsRegion()) {
 263     // FIXME: We should handle the case where we strip off view layers to get
 264     //  to a desugared type.
 265
 266     if (!Loc::IsLocType(castTy)) {
 267       // FIXME: There can be gross cases where one casts the result of a function
 268       // (that returns a pointer) to some other value that happens to fit
 269       // within that pointer value.  We currently have no good way to
 270       // model such operations.  When this happens, the underlying operation
 271       // is that the caller is reasoning about bits.  Conceptually we are
 272       // layering a "view" of a location on top of those bits.  Perhaps
 273       // we need to be more lazy about mutual possible views, even on an
 274       // SVal?  This may be necessary for bit-level reasoning as well.
 275       return UnknownVal();
 276     }
 277
 278     // We get a symbolic function pointer for a dereference of a function
 279     // pointer, but it is of function type. Example:
 280
 281     //  struct FPRec {
 282     //    void (*my_func)(int * x);
 283     //  };
 284     //
 285     //  int bar(int x);
 286     //
 287     //  int f1_a(struct FPRec* foo) {
 288     //    int x;
 289     //    (*foo->my_func)(&x);
 290     //    return bar(x)+1; // no-warning
 291     //  }
 292
 293     assert(Loc::IsLocType(originalTy) || originalTy->isFunctionType() ||
 294            originalTy->isBlockPointerType());
 295
 296     StoreManager &storeMgr = StateMgr.getStoreManager();
 297
 298     // Delegate to store manager to get the result of casting a region to a
 299     // different type.  If the MemRegion* returned is NULL, this expression
 300     // Evaluates to UnknownVal.
 301     R = storeMgr.CastRegion(R, castTy);
 302     return R ? SVal(loc::MemRegionVal(R)) : UnknownVal();
 303   }
 304
 305 DispatchCast:
 306   // All other cases.
 307   return isa<Loc>(val) ? evalCastL(cast<Loc>(val), castTy)
 308                        : evalCastNL(cast<NonLoc>(val), castTy);
 309 }