Home | History | Annotate | Line # | Download | only in Core 
      1 //===- Environment.cpp - Map from Stmt* to Locations/Values ---------------===//
      2 //
      3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
      4 // See https://llvm.org/LICENSE.txt for license information.
      5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
      6 //
      7 //===----------------------------------------------------------------------===//
      8 //
      9 //  This file defined the Environment and EnvironmentManager classes.
     10 //
     11 //===----------------------------------------------------------------------===//
     12 
     13 #include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h"
     14 #include "clang/AST/Expr.h"
     15 #include "clang/AST/ExprCXX.h"
     16 #include "clang/AST/PrettyPrinter.h"
     17 #include "clang/AST/Stmt.h"
     18 #include "clang/AST/StmtObjC.h"
     19 #include "clang/Analysis/AnalysisDeclContext.h"
     20 #include "clang/Basic/LLVM.h"
     21 #include "clang/Basic/LangOptions.h"
     22 #include "clang/Basic/JsonSupport.h"
     23 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
     24 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
     25 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
     26 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
     27 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
     28 #include "llvm/ADT/ImmutableMap.h"
     29 #include "llvm/ADT/SmallPtrSet.h"
     30 #include "llvm/Support/Casting.h"
     31 #include "llvm/Support/ErrorHandling.h"
     32 #include "llvm/Support/raw_ostream.h"
     33 #include <cassert>
     34 
     35 using namespace clang;
     36 using namespace ento;
     37 
     38 static const Expr *ignoreTransparentExprs(const Expr *E) {
     39   E = E->IgnoreParens();
     40 
     41   switch (E->getStmtClass()) {
     42   case Stmt::OpaqueValueExprClass:
     43     E = cast<OpaqueValueExpr>(E)->getSourceExpr();
     44     break;
     45   case Stmt::ExprWithCleanupsClass:
     46     E = cast<ExprWithCleanups>(E)->getSubExpr();
     47     break;
     48   case Stmt::ConstantExprClass:
     49     E = cast<ConstantExpr>(E)->getSubExpr();
     50     break;
     51   case Stmt::CXXBindTemporaryExprClass:
     52     E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
     53     break;
     54   case Stmt::SubstNonTypeTemplateParmExprClass:
     55     E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement();
     56     break;
     57   default:
     58     // This is the base case: we can't look through more than we already have.
     59     return E;
     60   }
     61 
     62   return ignoreTransparentExprs(E);
     63 }
     64 
     65 static const Stmt *ignoreTransparentExprs(const Stmt *S) {
     66   if (const auto *E = dyn_cast<Expr>(S))
     67     return ignoreTransparentExprs(E);
     68   return S;
     69 }
     70 
     71 EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L)
     72     : std::pair<const Stmt *,
     73                 const StackFrameContext *>(ignoreTransparentExprs(S),
     74                                            L ? L->getStackFrame()
     75                                              : nullptr) {}
     76 
     77 SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
     78   const SVal* X = ExprBindings.lookup(E);
     79   if (X) {
     80     SVal V = *X;
     81     return V;
     82   }
     83   return UnknownVal();
     84 }
     85 
     86 SVal Environment::getSVal(const EnvironmentEntry &Entry,
     87                           SValBuilder& svalBuilder) const {
     88   const Stmt *S = Entry.getStmt();
     89   assert(!isa<ObjCForCollectionStmt>(S) &&
     90          "Use ExprEngine::hasMoreIteration()!");
     91   assert((isa<Expr>(S) || isa<ReturnStmt>(S)) &&
     92          "Environment can only argue about Exprs, since only they express "
     93          "a value! Any non-expression statement stored in Environment is a "
     94          "result of a hack!");
     95   const LocationContext *LCtx = Entry.getLocationContext();
     96 
     97   switch (S->getStmtClass()) {
     98   case Stmt::CXXBindTemporaryExprClass:
     99   case Stmt::ExprWithCleanupsClass:
    100   case Stmt::GenericSelectionExprClass:
    101   case Stmt::OpaqueValueExprClass:
    102   case Stmt::ConstantExprClass:
    103   case Stmt::ParenExprClass:
    104   case Stmt::SubstNonTypeTemplateParmExprClass:
    105     llvm_unreachable("Should have been handled by ignoreTransparentExprs");
    106 
    107   case Stmt::AddrLabelExprClass:
    108   case Stmt::CharacterLiteralClass:
    109   case Stmt::CXXBoolLiteralExprClass:
    110   case Stmt::CXXScalarValueInitExprClass:
    111   case Stmt::ImplicitValueInitExprClass:
    112   case Stmt::IntegerLiteralClass:
    113   case Stmt::ObjCBoolLiteralExprClass:
    114   case Stmt::CXXNullPtrLiteralExprClass:
    115   case Stmt::ObjCStringLiteralClass:
    116   case Stmt::StringLiteralClass:
    117   case Stmt::TypeTraitExprClass:
    118   case Stmt::SizeOfPackExprClass:
    119   case Stmt::PredefinedExprClass:
    120     // Known constants; defer to SValBuilder.
    121     return svalBuilder.getConstantVal(cast<Expr>(S)).getValue();
    122 
    123   case Stmt::ReturnStmtClass: {
    124     const auto *RS = cast<ReturnStmt>(S);
    125     if (const Expr *RE = RS->getRetValue())
    126       return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
    127     return UndefinedVal();
    128   }
    129 
    130   // Handle all other Stmt* using a lookup.
    131   default:
    132     return lookupExpr(EnvironmentEntry(S, LCtx));
    133   }
    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 
    151 class MarkLiveCallback final : public SymbolVisitor {
    152   SymbolReaper &SymReaper;
    153 
    154 public:
    155   MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
    156 
    157   bool VisitSymbol(SymbolRef sym) override {
    158     SymReaper.markLive(sym);
    159     return true;
    160   }
    161 
    162   bool VisitMemRegion(const MemRegion *R) override {
    163     SymReaper.markLive(R);
    164     return true;
    165   }
    166 };
    167 
    168 } // namespace
    169 
    170 // removeDeadBindings:
    171 //  - Remove subexpression bindings.
    172 //  - Remove dead block expression bindings.
    173 //  - Keep live block expression bindings:
    174 //   - Mark their reachable symbols live in SymbolReaper,
    175 //     see ScanReachableSymbols.
    176 //   - Mark the region in DRoots if the binding is a loc::MemRegionVal.
    177 Environment
    178 EnvironmentManager::removeDeadBindings(Environment Env,
    179                                        SymbolReaper &SymReaper,
    180                                        ProgramStateRef ST) {
    181   // We construct a new Environment object entirely, as this is cheaper than
    182   // individually removing all the subexpression bindings (which will greatly
    183   // outnumber block-level expression bindings).
    184   Environment NewEnv = getInitialEnvironment();
    185 
    186   MarkLiveCallback CB(SymReaper);
    187   ScanReachableSymbols RSScaner(ST, CB);
    188 
    189   llvm::ImmutableMapRef<EnvironmentEntry, SVal>
    190     EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
    191              F.getTreeFactory());
    192 
    193   // Iterate over the block-expr bindings.
    194   for (Environment::iterator I = Env.begin(), End = Env.end(); I != End; ++I) {
    195     const EnvironmentEntry &BlkExpr = I.getKey();
    196     const SVal &X = I.getData();
    197 
    198     const Expr *E = dyn_cast<Expr>(BlkExpr.getStmt());
    199     if (!E)
    200       continue;
    201 
    202     if (SymReaper.isLive(E, BlkExpr.getLocationContext())) {
    203       // Copy the binding to the new map.
    204       EBMapRef = EBMapRef.add(BlkExpr, X);
    205 
    206       // Mark all symbols in the block expr's value live.
    207       RSScaner.scan(X);
    208     }
    209   }
    210 
    211   NewEnv.ExprBindings = EBMapRef.asImmutableMap();
    212   return NewEnv;
    213 }
    214 
    215 void Environment::printJson(raw_ostream &Out, const ASTContext &Ctx,
    216                             const LocationContext *LCtx, const char *NL,
    217                             unsigned int Space, bool IsDot) const {
    218   Indent(Out, Space, IsDot) << "\"environment\": ";
    219 
    220   if (ExprBindings.isEmpty()) {
    221     Out << "null," << NL;
    222     return;
    223   }
    224 
    225   ++Space;
    226   if (!LCtx) {
    227     // Find the freshest location context.
    228     llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts;
    229     for (const auto &I : *this) {
    230       const LocationContext *LC = I.first.getLocationContext();
    231       if (FoundContexts.count(LC) == 0) {
    232         // This context is fresher than all other contexts so far.
    233         LCtx = LC;
    234         for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent())
    235           FoundContexts.insert(LCI);
    236       }
    237     }
    238   }
    239 
    240   assert(LCtx);
    241 
    242   Out << "{ \"pointer\": \"" << (const void *)LCtx->getStackFrame()
    243       << "\", \"items\": [" << NL;
    244   PrintingPolicy PP = Ctx.getPrintingPolicy();
    245 
    246   LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) {
    247     // LCtx items begin
    248     bool HasItem = false;
    249     unsigned int InnerSpace = Space + 1;
    250 
    251     // Store the last ExprBinding which we will print.
    252     BindingsTy::iterator LastI = ExprBindings.end();
    253     for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end();
    254          ++I) {
    255       if (I->first.getLocationContext() != LC)
    256         continue;
    257 
    258       if (!HasItem) {
    259         HasItem = true;
    260         Out << '[' << NL;
    261       }
    262 
    263       const Stmt *S = I->first.getStmt();
    264       (void)S;
    265       assert(S != nullptr && "Expected non-null Stmt");
    266 
    267       LastI = I;
    268     }
    269 
    270     for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end();
    271          ++I) {
    272       if (I->first.getLocationContext() != LC)
    273         continue;
    274 
    275       const Stmt *S = I->first.getStmt();
    276       Indent(Out, InnerSpace, IsDot)
    277           << "{ \"stmt_id\": " << S->getID(Ctx) << ", \"pretty\": ";
    278       S->printJson(Out, nullptr, PP, /*AddQuotes=*/true);
    279 
    280       Out << ", \"value\": ";
    281       I->second.printJson(Out, /*AddQuotes=*/true);
    282 
    283       Out << " }";
    284 
    285       if (I != LastI)
    286         Out << ',';
    287       Out << NL;
    288     }
    289 
    290     if (HasItem)
    291       Indent(Out, --InnerSpace, IsDot) << ']';
    292     else
    293       Out << "null ";
    294   });
    295 
    296   Indent(Out, --Space, IsDot) << "]}," << NL;
    297 }
    298