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