clang/lib/StaticAnalyzer/Core/Environment.cpp

   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/JsonSupport.h"
  21 #include "clang/Basic/LLVM.h"
  22 #include "clang/Basic/LangOptions.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, 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));
 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) << ", \"kind\": \""
 278           << S->getStmtClassName() << "\", \"pretty\": ";
 279       S->printJson(Out, nullptr, PP, /*AddQuotes=*/true);
 280
 281       Out << ", \"value\": ";
 282       I->second.printJson(Out, /*AddQuotes=*/true);
 283
 284       Out << " }";
 285
 286       if (I != LastI)
 287         Out << ',';
 288       Out << NL;
 289     }
 290
 291     if (HasItem)
 292       Indent(Out, --InnerSpace, IsDot) << ']';
 293     else
 294       Out << "null ";
 295   });
 296
 297   Indent(Out, --Space, IsDot) << "]}," << NL;
 298 }