contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/Environment.cpp

   1 //== Environment.cpp - Map from Stmt* to Locations/Values -------*- 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 defined the Environment and EnvironmentManager classes.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/AST/ExprCXX.h"
  15 #include "clang/AST/ExprObjC.h"
  16 #include "clang/Analysis/AnalysisContext.h"
  17 #include "clang/Analysis/CFG.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  19 #include "llvm/Support/raw_ostream.h"
  20
  21 using namespace clang;
  22 using namespace ento;
  23
  24 static const Expr *ignoreTransparentExprs(const Expr *E) {
  25   E = E->IgnoreParens();
  26
  27   switch (E->getStmtClass()) {
  28   case Stmt::OpaqueValueExprClass:
  29     E = cast<OpaqueValueExpr>(E)->getSourceExpr();
  30     break;
  31   case Stmt::ExprWithCleanupsClass:
  32     E = cast<ExprWithCleanups>(E)->getSubExpr();
  33     break;
  34   case Stmt::CXXBindTemporaryExprClass:
  35     E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
  36     break;
  37   case Stmt::SubstNonTypeTemplateParmExprClass:
  38     E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement();
  39     break;
  40   default:
  41     // This is the base case: we can't look through more than we already have.
  42     return E;
  43   }
  44
  45   return ignoreTransparentExprs(E);
  46 }
  47
  48 static const Stmt *ignoreTransparentExprs(const Stmt *S) {
  49   if (const Expr *E = dyn_cast<Expr>(S))
  50     return ignoreTransparentExprs(E);
  51   return S;
  52 }
  53
  54 EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L)
  55   : std::pair<const Stmt *,
  56               const StackFrameContext *>(ignoreTransparentExprs(S),
  57                                          L ? L->getCurrentStackFrame() : 0) {}
  58
  59 SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
  60   const SVal* X = ExprBindings.lookup(E);
  61   if (X) {
  62     SVal V = *X;
  63     return V;
  64   }
  65   return UnknownVal();
  66 }
  67
  68 SVal Environment::getSVal(const EnvironmentEntry &Entry,
  69                           SValBuilder& svalBuilder) const {
  70   const Stmt *S = Entry.getStmt();
  71   const LocationContext *LCtx = Entry.getLocationContext();
  72
  73   switch (S->getStmtClass()) {
  74   case Stmt::CXXBindTemporaryExprClass:
  75   case Stmt::ExprWithCleanupsClass:
  76   case Stmt::GenericSelectionExprClass:
  77   case Stmt::OpaqueValueExprClass:
  78   case Stmt::ParenExprClass:
  79   case Stmt::SubstNonTypeTemplateParmExprClass:
  80     llvm_unreachable("Should have been handled by ignoreTransparentExprs");
  81
  82   case Stmt::AddrLabelExprClass:
  83     return svalBuilder.makeLoc(cast<AddrLabelExpr>(S));
  84
  85   case Stmt::CharacterLiteralClass: {
  86     const CharacterLiteral *C = cast<CharacterLiteral>(S);
  87     return svalBuilder.makeIntVal(C->getValue(), C->getType());
  88   }
  89
  90   case Stmt::CXXBoolLiteralExprClass:
  91     return svalBuilder.makeBoolVal(cast<CXXBoolLiteralExpr>(S));
  92
  93   case Stmt::CXXScalarValueInitExprClass:
  94   case Stmt::ImplicitValueInitExprClass: {
  95     QualType Ty = cast<Expr>(S)->getType();
  96     return svalBuilder.makeZeroVal(Ty);
  97   }
  98
  99   case Stmt::IntegerLiteralClass:
 100     return svalBuilder.makeIntVal(cast<IntegerLiteral>(S));
 101
 102   case Stmt::ObjCBoolLiteralExprClass:
 103     return svalBuilder.makeBoolVal(cast<ObjCBoolLiteralExpr>(S));
 104
 105   // For special C0xx nullptr case, make a null pointer SVal.
 106   case Stmt::CXXNullPtrLiteralExprClass:
 107     return svalBuilder.makeNull();
 108
 109   case Stmt::ObjCStringLiteralClass: {
 110     MemRegionManager &MRMgr = svalBuilder.getRegionManager();
 111     const ObjCStringLiteral *SL = cast<ObjCStringLiteral>(S);
 112     return svalBuilder.makeLoc(MRMgr.getObjCStringRegion(SL));
 113   }
 114
 115   case Stmt::StringLiteralClass: {
 116     MemRegionManager &MRMgr = svalBuilder.getRegionManager();
 117     const StringLiteral *SL = cast<StringLiteral>(S);
 118     return svalBuilder.makeLoc(MRMgr.getStringRegion(SL));
 119   }
 120
 121   case Stmt::ReturnStmtClass: {
 122     const ReturnStmt *RS = cast<ReturnStmt>(S);
 123     if (const Expr *RE = RS->getRetValue())
 124       return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
 125     return UndefinedVal();
 126   }
 127
 128   // Handle all other Stmt* using a lookup.
 129   default:
 130     break;
 131   }
 132
 133   return lookupExpr(EnvironmentEntry(S, LCtx));
 134 }
 135
 136 Environment EnvironmentManager::bindExpr(Environment Env,
 137                                          const EnvironmentEntry &E,
 138                                          SVal V,
 139                                          bool Invalidate) {
 140   if (V.isUnknown()) {
 141     if (Invalidate)
 142       return Environment(F.remove(Env.ExprBindings, E));
 143     else
 144       return Env;
 145   }
 146   return Environment(F.add(Env.ExprBindings, E, V));
 147 }
 148
 149 namespace {
 150 class MarkLiveCallback : public SymbolVisitor {
 151   SymbolReaper &SymReaper;
 152 public:
 153   MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
 154   bool VisitSymbol(SymbolRef sym) {
 155     SymReaper.markLive(sym);
 156     return true;
 157   }
 158   bool VisitMemRegion(const MemRegion *R) {
 159     SymReaper.markLive(R);
 160     return true;
 161   }
 162 };
 163 } // end anonymous namespace
 164
 165 // removeDeadBindings:
 166 //  - Remove subexpression bindings.
 167 //  - Remove dead block expression bindings.
 168 //  - Keep live block expression bindings:
 169 //   - Mark their reachable symbols live in SymbolReaper,
 170 //     see ScanReachableSymbols.
 171 //   - Mark the region in DRoots if the binding is a loc::MemRegionVal.
 172 Environment
 173 EnvironmentManager::removeDeadBindings(Environment Env,
 174                                        SymbolReaper &SymReaper,
 175                                        ProgramStateRef ST) {
 176
 177   // We construct a new Environment object entirely, as this is cheaper than
 178   // individually removing all the subexpression bindings (which will greatly
 179   // outnumber block-level expression bindings).
 180   Environment NewEnv = getInitialEnvironment();
 181
 182   MarkLiveCallback CB(SymReaper);
 183   ScanReachableSymbols RSScaner(ST, CB);
 184
 185   llvm::ImmutableMapRef<EnvironmentEntry,SVal>
 186     EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
 187              F.getTreeFactory());
 188
 189   // Iterate over the block-expr bindings.
 190   for (Environment::iterator I = Env.begin(), E = Env.end();
 191        I != E; ++I) {
 192
 193     const EnvironmentEntry &BlkExpr = I.getKey();
 194     const SVal &X = I.getData();
 195
 196     if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
 197       // Copy the binding to the new map.
 198       EBMapRef = EBMapRef.add(BlkExpr, X);
 199
 200       // If the block expr's value is a memory region, then mark that region.
 201       if (Optional<loc::MemRegionVal> R = X.getAs<loc::MemRegionVal>())
 202         SymReaper.markLive(R->getRegion());
 203
 204       // Mark all symbols in the block expr's value live.
 205       RSScaner.scan(X);
 206       continue;
 207     } else {
 208       SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
 209       for (; SI != SE; ++SI)
 210         SymReaper.maybeDead(*SI);
 211     }
 212   }
 213
 214   NewEnv.ExprBindings = EBMapRef.asImmutableMap();
 215   return NewEnv;
 216 }
 217
 218 void Environment::print(raw_ostream &Out, const char *NL,
 219                         const char *Sep) const {
 220   bool isFirst = true;
 221
 222   for (Environment::iterator I = begin(), E = end(); I != E; ++I) {
 223     const EnvironmentEntry &En = I.getKey();
 224
 225     if (isFirst) {
 226       Out << NL << NL
 227           << "Expressions:"
 228           << NL;
 229       isFirst = false;
 230     } else {
 231       Out << NL;
 232     }
 233
 234     const Stmt *S = En.getStmt();
 235
 236     Out << " (" << (const void*) En.getLocationContext() << ','
 237       << (const void*) S << ") ";
 238     LangOptions LO; // FIXME.
 239     S->printPretty(Out, 0, PrintingPolicy(LO));
 240     Out << " : " << I.getData();
 241   }
 242 }