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/AST/ExprCXX.h"
  16 #include "clang/AST/DeclCXX.h"
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  21 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
  22
  23 using namespace clang;
  24 using namespace ento;
  25
  26 //===----------------------------------------------------------------------===//
  27 // Basic SVal creation.
  28 //===----------------------------------------------------------------------===//
  29
  30 void SValBuilder::anchor() { }
  31
  32 DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType type) {
  33   if (Loc::isLocType(type))
  34     return makeNull();
  35
  36   if (type->isIntegerType())
  37     return makeIntVal(0, type);
  38
  39   // FIXME: Handle floats.
  40   // FIXME: Handle structs.
  41   return UnknownVal();
  42 }
  43
  44 NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
  45                                 const llvm::APSInt& rhs, QualType type) {
  46   // The Environment ensures we always get a persistent APSInt in
  47   // BasicValueFactory, so we don't need to get the APSInt from
  48   // BasicValueFactory again.
  49   assert(lhs);
  50   assert(!Loc::isLocType(type));
  51   return nonloc::SymbolVal(SymMgr.getSymIntExpr(lhs, op, rhs, type));
  52 }
  53
  54 NonLoc SValBuilder::makeNonLoc(const llvm::APSInt& lhs,
  55                                BinaryOperator::Opcode op, const SymExpr *rhs,
  56                                QualType type) {
  57   assert(rhs);
  58   assert(!Loc::isLocType(type));
  59   return nonloc::SymbolVal(SymMgr.getIntSymExpr(lhs, op, rhs, type));
  60 }
  61
  62 NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
  63                                const SymExpr *rhs, QualType type) {
  64   assert(lhs && rhs);
  65   assert(!Loc::isLocType(type));
  66   return nonloc::SymbolVal(SymMgr.getSymSymExpr(lhs, op, rhs, type));
  67 }
  68
  69 NonLoc SValBuilder::makeNonLoc(const SymExpr *operand,
  70                                QualType fromTy, QualType toTy) {
  71   assert(operand);
  72   assert(!Loc::isLocType(toTy));
  73   return nonloc::SymbolVal(SymMgr.getCastSymbol(operand, fromTy, toTy));
  74 }
  75
  76 SVal SValBuilder::convertToArrayIndex(SVal val) {
  77   if (val.isUnknownOrUndef())
  78     return val;
  79
  80   // Common case: we have an appropriately sized integer.
  81   if (nonloc::ConcreteInt* CI = dyn_cast<nonloc::ConcreteInt>(&val)) {
  82     const llvm::APSInt& I = CI->getValue();
  83     if (I.getBitWidth() == ArrayIndexWidth && I.isSigned())
  84       return val;
  85   }
  86
  87   return evalCastFromNonLoc(cast<NonLoc>(val), ArrayIndexTy);
  88 }
  89
  90 nonloc::ConcreteInt SValBuilder::makeBoolVal(const CXXBoolLiteralExpr *boolean){
  91   return makeTruthVal(boolean->getValue());
  92 }
  93
  94 DefinedOrUnknownSVal
  95 SValBuilder::getRegionValueSymbolVal(const TypedValueRegion* region) {
  96   QualType T = region->getValueType();
  97
  98   if (!SymbolManager::canSymbolicate(T))
  99     return UnknownVal();
 100
 101   SymbolRef sym = SymMgr.getRegionValueSymbol(region);
 102
 103   if (Loc::isLocType(T))
 104     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
 105
 106   return nonloc::SymbolVal(sym);
 107 }
 108
 109 DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *symbolTag,
 110                                                    const Expr *expr,
 111                                                    const LocationContext *LCtx,
 112                                                    unsigned count) {
 113   QualType T = expr->getType();
 114   return conjureSymbolVal(symbolTag, expr, LCtx, T, count);
 115 }
 116
 117 DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *symbolTag,
 118                                                    const Expr *expr,
 119                                                    const LocationContext *LCtx,
 120                                                    QualType type,
 121                                                    unsigned count) {
 122   if (!SymbolManager::canSymbolicate(type))
 123     return UnknownVal();
 124
 125   SymbolRef sym = SymMgr.conjureSymbol(expr, LCtx, type, count, symbolTag);
 126
 127   if (Loc::isLocType(type))
 128     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
 129
 130   return nonloc::SymbolVal(sym);
 131 }
 132
 133
 134 DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const Stmt *stmt,
 135                                                    const LocationContext *LCtx,
 136                                                    QualType type,
 137                                                    unsigned visitCount) {
 138   if (!SymbolManager::canSymbolicate(type))
 139     return UnknownVal();
 140
 141   SymbolRef sym = SymMgr.conjureSymbol(stmt, LCtx, type, visitCount);
 142
 143   if (Loc::isLocType(type))
 144     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
 145
 146   return nonloc::SymbolVal(sym);
 147 }
 148
 149 DefinedOrUnknownSVal
 150 SValBuilder::getConjuredHeapSymbolVal(const Expr *E,
 151                                       const LocationContext *LCtx,
 152                                       unsigned VisitCount) {
 153   QualType T = E->getType();
 154   assert(Loc::isLocType(T));
 155   assert(SymbolManager::canSymbolicate(T));
 156
 157   SymbolRef sym = SymMgr.conjureSymbol(E, LCtx, T, VisitCount);
 158   return loc::MemRegionVal(MemMgr.getSymbolicHeapRegion(sym));
 159 }
 160
 161 DefinedSVal SValBuilder::getMetadataSymbolVal(const void *symbolTag,
 162                                               const MemRegion *region,
 163                                               const Expr *expr, QualType type,
 164                                               unsigned count) {
 165   assert(SymbolManager::canSymbolicate(type) && "Invalid metadata symbol type");
 166
 167   SymbolRef sym =
 168       SymMgr.getMetadataSymbol(region, expr, type, count, symbolTag);
 169
 170   if (Loc::isLocType(type))
 171     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
 172
 173   return nonloc::SymbolVal(sym);
 174 }
 175
 176 DefinedOrUnknownSVal
 177 SValBuilder::getDerivedRegionValueSymbolVal(SymbolRef parentSymbol,
 178                                              const TypedValueRegion *region) {
 179   QualType T = region->getValueType();
 180
 181   if (!SymbolManager::canSymbolicate(T))
 182     return UnknownVal();
 183
 184   SymbolRef sym = SymMgr.getDerivedSymbol(parentSymbol, region);
 185
 186   if (Loc::isLocType(T))
 187     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
 188
 189   return nonloc::SymbolVal(sym);
 190 }
 191
 192 DefinedSVal SValBuilder::getFunctionPointer(const FunctionDecl *func) {
 193   return loc::MemRegionVal(MemMgr.getFunctionTextRegion(func));
 194 }
 195
 196 DefinedSVal SValBuilder::getBlockPointer(const BlockDecl *block,
 197                                          CanQualType locTy,
 198                                          const LocationContext *locContext) {
 199   const BlockTextRegion *BC =
 200     MemMgr.getBlockTextRegion(block, locTy, locContext->getAnalysisDeclContext());
 201   const BlockDataRegion *BD = MemMgr.getBlockDataRegion(BC, locContext);
 202   return loc::MemRegionVal(BD);
 203 }
 204
 205 /// Return a memory region for the 'this' object reference.
 206 loc::MemRegionVal SValBuilder::getCXXThis(const CXXMethodDecl *D,
 207                                           const StackFrameContext *SFC) {
 208   return loc::MemRegionVal(getRegionManager().
 209                            getCXXThisRegion(D->getThisType(getContext()), SFC));
 210 }
 211
 212 /// Return a memory region for the 'this' object reference.
 213 loc::MemRegionVal SValBuilder::getCXXThis(const CXXRecordDecl *D,
 214                                           const StackFrameContext *SFC) {
 215   const Type *T = D->getTypeForDecl();
 216   QualType PT = getContext().getPointerType(QualType(T, 0));
 217   return loc::MemRegionVal(getRegionManager().getCXXThisRegion(PT, SFC));
 218 }
 219
 220 //===----------------------------------------------------------------------===//
 221
 222 SVal SValBuilder::makeSymExprValNN(ProgramStateRef State,
 223                                    BinaryOperator::Opcode Op,
 224                                    NonLoc LHS, NonLoc RHS,
 225                                    QualType ResultTy) {
 226   if (!State->isTainted(RHS) && !State->isTainted(LHS))
 227     return UnknownVal();
 228
 229   const SymExpr *symLHS = LHS.getAsSymExpr();
 230   const SymExpr *symRHS = RHS.getAsSymExpr();
 231   // TODO: When the Max Complexity is reached, we should conjure a symbol
 232   // instead of generating an Unknown value and propagate the taint info to it.
 233   const unsigned MaxComp = 10000; // 100000 28X
 234
 235   if (symLHS && symRHS &&
 236       (symLHS->computeComplexity() + symRHS->computeComplexity()) <  MaxComp)
 237     return makeNonLoc(symLHS, Op, symRHS, ResultTy);
 238
 239   if (symLHS && symLHS->computeComplexity() < MaxComp)
 240     if (const nonloc::ConcreteInt *rInt = dyn_cast<nonloc::ConcreteInt>(&RHS))
 241       return makeNonLoc(symLHS, Op, rInt->getValue(), ResultTy);
 242
 243   if (symRHS && symRHS->computeComplexity() < MaxComp)
 244     if (const nonloc::ConcreteInt *lInt = dyn_cast<nonloc::ConcreteInt>(&LHS))
 245       return makeNonLoc(lInt->getValue(), Op, symRHS, ResultTy);
 246
 247   return UnknownVal();
 248 }
 249
 250
 251 SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
 252                             SVal lhs, SVal rhs, QualType type) {
 253
 254   if (lhs.isUndef() || rhs.isUndef())
 255     return UndefinedVal();
 256
 257   if (lhs.isUnknown() || rhs.isUnknown())
 258     return UnknownVal();
 259
 260   if (isa<Loc>(lhs)) {
 261     if (isa<Loc>(rhs))
 262       return evalBinOpLL(state, op, cast<Loc>(lhs), cast<Loc>(rhs), type);
 263
 264     return evalBinOpLN(state, op, cast<Loc>(lhs), cast<NonLoc>(rhs), type);
 265   }
 266
 267   if (isa<Loc>(rhs)) {
 268     // Support pointer arithmetic where the addend is on the left
 269     // and the pointer on the right.
 270     assert(op == BO_Add);
 271
 272     // Commute the operands.
 273     return evalBinOpLN(state, op, cast<Loc>(rhs), cast<NonLoc>(lhs), type);
 274   }
 275
 276   return evalBinOpNN(state, op, cast<NonLoc>(lhs), cast<NonLoc>(rhs), type);
 277 }
 278
 279 DefinedOrUnknownSVal SValBuilder::evalEQ(ProgramStateRef state,
 280                                          DefinedOrUnknownSVal lhs,
 281                                          DefinedOrUnknownSVal rhs) {
 282   return cast<DefinedOrUnknownSVal>(evalBinOp(state, BO_EQ, lhs, rhs,
 283                                               Context.IntTy));
 284 }
 285
 286 /// Recursively check if the pointer types are equal modulo const, volatile,
 287 /// and restrict qualifiers. Assumes the input types are canonical.
 288 /// TODO: This is based off of code in SemaCast; can we reuse it.
 289 static bool haveSimilarTypes(ASTContext &Context, QualType T1,
 290                                                   QualType T2) {
 291   while (Context.UnwrapSimilarPointerTypes(T1, T2)) {
 292     Qualifiers Quals1, Quals2;
 293     T1 = Context.getUnqualifiedArrayType(T1, Quals1);
 294     T2 = Context.getUnqualifiedArrayType(T2, Quals2);
 295
 296     // Make sure that non cvr-qualifiers the other qualifiers (e.g., address
 297     // spaces) are identical.
 298     Quals1.removeCVRQualifiers();
 299     Quals2.removeCVRQualifiers();
 300     if (Quals1 != Quals2)
 301       return false;
 302   }
 303
 304   if (T1 != T2)
 305     return false;
 306
 307   return true;
 308 }
 309
 310 // FIXME: should rewrite according to the cast kind.
 311 SVal SValBuilder::evalCast(SVal val, QualType castTy, QualType originalTy) {
 312   castTy = Context.getCanonicalType(castTy);
 313   originalTy = Context.getCanonicalType(originalTy);
 314   if (val.isUnknownOrUndef() || castTy == originalTy)
 315     return val;
 316
 317   // For const casts, just propagate the value.
 318   if (!castTy->isVariableArrayType() && !originalTy->isVariableArrayType())
 319     if (haveSimilarTypes(Context, Context.getPointerType(castTy),
 320                                   Context.getPointerType(originalTy)))
 321       return val;
 322
 323   // Check for casts from pointers to integers.
 324   if (castTy->isIntegerType() && Loc::isLocType(originalTy))
 325     return evalCastFromLoc(cast<Loc>(val), castTy);
 326
 327   // Check for casts from integers to pointers.
 328   if (Loc::isLocType(castTy) && originalTy->isIntegerType()) {
 329     if (nonloc::LocAsInteger *LV = dyn_cast<nonloc::LocAsInteger>(&val)) {
 330       if (const MemRegion *R = LV->getLoc().getAsRegion()) {
 331         StoreManager &storeMgr = StateMgr.getStoreManager();
 332         R = storeMgr.castRegion(R, castTy);
 333         return R ? SVal(loc::MemRegionVal(R)) : UnknownVal();
 334       }
 335       return LV->getLoc();
 336     }
 337     return dispatchCast(val, castTy);
 338   }
 339
 340   // Just pass through function and block pointers.
 341   if (originalTy->isBlockPointerType() || originalTy->isFunctionPointerType()) {
 342     assert(Loc::isLocType(castTy));
 343     return val;
 344   }
 345
 346   // Check for casts from array type to another type.
 347   if (originalTy->isArrayType()) {
 348     // We will always decay to a pointer.
 349     val = StateMgr.ArrayToPointer(cast<Loc>(val));
 350
 351     // Are we casting from an array to a pointer?  If so just pass on
 352     // the decayed value.
 353     if (castTy->isPointerType() || castTy->isReferenceType())
 354       return val;
 355
 356     // Are we casting from an array to an integer?  If so, cast the decayed
 357     // pointer value to an integer.
 358     assert(castTy->isIntegerType());
 359
 360     // FIXME: Keep these here for now in case we decide soon that we
 361     // need the original decayed type.
 362     //    QualType elemTy = cast<ArrayType>(originalTy)->getElementType();
 363     //    QualType pointerTy = C.getPointerType(elemTy);
 364     return evalCastFromLoc(cast<Loc>(val), castTy);
 365   }
 366
 367   // Check for casts from a region to a specific type.
 368   if (const MemRegion *R = val.getAsRegion()) {
 369     // Handle other casts of locations to integers.
 370     if (castTy->isIntegerType())
 371       return evalCastFromLoc(loc::MemRegionVal(R), castTy);
 372
 373     // FIXME: We should handle the case where we strip off view layers to get
 374     //  to a desugared type.
 375     if (!Loc::isLocType(castTy)) {
 376       // FIXME: There can be gross cases where one casts the result of a function
 377       // (that returns a pointer) to some other value that happens to fit
 378       // within that pointer value.  We currently have no good way to
 379       // model such operations.  When this happens, the underlying operation
 380       // is that the caller is reasoning about bits.  Conceptually we are
 381       // layering a "view" of a location on top of those bits.  Perhaps
 382       // we need to be more lazy about mutual possible views, even on an
 383       // SVal?  This may be necessary for bit-level reasoning as well.
 384       return UnknownVal();
 385     }
 386
 387     // We get a symbolic function pointer for a dereference of a function
 388     // pointer, but it is of function type. Example:
 389
 390     //  struct FPRec {
 391     //    void (*my_func)(int * x);
 392     //  };
 393     //
 394     //  int bar(int x);
 395     //
 396     //  int f1_a(struct FPRec* foo) {
 397     //    int x;
 398     //    (*foo->my_func)(&x);
 399     //    return bar(x)+1; // no-warning
 400     //  }
 401
 402     assert(Loc::isLocType(originalTy) || originalTy->isFunctionType() ||
 403            originalTy->isBlockPointerType() || castTy->isReferenceType());
 404
 405     StoreManager &storeMgr = StateMgr.getStoreManager();
 406
 407     // Delegate to store manager to get the result of casting a region to a
 408     // different type.  If the MemRegion* returned is NULL, this expression
 409     // Evaluates to UnknownVal.
 410     R = storeMgr.castRegion(R, castTy);
 411     return R ? SVal(loc::MemRegionVal(R)) : UnknownVal();
 412   }
 413
 414   return dispatchCast(val, castTy);
 415 }