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