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