Home | History | Annotate | Download | only in Core 
      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 }
    243