123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297 |
- //===- Environment.cpp - Map from Stmt* to Locations/Values ---------------===//
- //
- // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
- // See https://llvm.org/LICENSE.txt for license information.
- // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
- //
- //===----------------------------------------------------------------------===//
- //
- // This file defined the Environment and EnvironmentManager classes.
- //
- //===----------------------------------------------------------------------===//
- #include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h"
- #include "clang/AST/Expr.h"
- #include "clang/AST/ExprCXX.h"
- #include "clang/AST/PrettyPrinter.h"
- #include "clang/AST/Stmt.h"
- #include "clang/AST/StmtObjC.h"
- #include "clang/Analysis/AnalysisDeclContext.h"
- #include "clang/Basic/LLVM.h"
- #include "clang/Basic/LangOptions.h"
- #include "clang/Basic/JsonSupport.h"
- #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
- #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
- #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
- #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
- #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
- #include "llvm/ADT/ImmutableMap.h"
- #include "llvm/ADT/SmallPtrSet.h"
- #include "llvm/Support/Casting.h"
- #include "llvm/Support/ErrorHandling.h"
- #include "llvm/Support/raw_ostream.h"
- #include <cassert>
- using namespace clang;
- using namespace ento;
- static const Expr *ignoreTransparentExprs(const Expr *E) {
- E = E->IgnoreParens();
- switch (E->getStmtClass()) {
- case Stmt::OpaqueValueExprClass:
- E = cast<OpaqueValueExpr>(E)->getSourceExpr();
- break;
- case Stmt::ExprWithCleanupsClass:
- E = cast<ExprWithCleanups>(E)->getSubExpr();
- break;
- case Stmt::ConstantExprClass:
- E = cast<ConstantExpr>(E)->getSubExpr();
- break;
- case Stmt::CXXBindTemporaryExprClass:
- E = cast<CXXBindTemporaryExpr>(E)->getSubExpr();
- break;
- case Stmt::SubstNonTypeTemplateParmExprClass:
- E = cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement();
- break;
- default:
- // This is the base case: we can't look through more than we already have.
- return E;
- }
- return ignoreTransparentExprs(E);
- }
- static const Stmt *ignoreTransparentExprs(const Stmt *S) {
- if (const auto *E = dyn_cast<Expr>(S))
- return ignoreTransparentExprs(E);
- return S;
- }
- EnvironmentEntry::EnvironmentEntry(const Stmt *S, const LocationContext *L)
- : std::pair<const Stmt *,
- const StackFrameContext *>(ignoreTransparentExprs(S),
- L ? L->getStackFrame()
- : nullptr) {}
- SVal Environment::lookupExpr(const EnvironmentEntry &E) const {
- const SVal* X = ExprBindings.lookup(E);
- if (X) {
- SVal V = *X;
- return V;
- }
- return UnknownVal();
- }
- SVal Environment::getSVal(const EnvironmentEntry &Entry,
- SValBuilder& svalBuilder) const {
- const Stmt *S = Entry.getStmt();
- assert(!isa<ObjCForCollectionStmt>(S) &&
- "Use ExprEngine::hasMoreIteration()!");
- assert((isa<Expr, ReturnStmt>(S)) &&
- "Environment can only argue about Exprs, since only they express "
- "a value! Any non-expression statement stored in Environment is a "
- "result of a hack!");
- const LocationContext *LCtx = Entry.getLocationContext();
- switch (S->getStmtClass()) {
- case Stmt::CXXBindTemporaryExprClass:
- case Stmt::ExprWithCleanupsClass:
- case Stmt::GenericSelectionExprClass:
- case Stmt::OpaqueValueExprClass:
- case Stmt::ConstantExprClass:
- case Stmt::ParenExprClass:
- case Stmt::SubstNonTypeTemplateParmExprClass:
- llvm_unreachable("Should have been handled by ignoreTransparentExprs");
- case Stmt::AddrLabelExprClass:
- case Stmt::CharacterLiteralClass:
- case Stmt::CXXBoolLiteralExprClass:
- case Stmt::CXXScalarValueInitExprClass:
- case Stmt::ImplicitValueInitExprClass:
- case Stmt::IntegerLiteralClass:
- case Stmt::ObjCBoolLiteralExprClass:
- case Stmt::CXXNullPtrLiteralExprClass:
- case Stmt::ObjCStringLiteralClass:
- case Stmt::StringLiteralClass:
- case Stmt::TypeTraitExprClass:
- case Stmt::SizeOfPackExprClass:
- case Stmt::PredefinedExprClass:
- // Known constants; defer to SValBuilder.
- return svalBuilder.getConstantVal(cast<Expr>(S)).getValue();
- case Stmt::ReturnStmtClass: {
- const auto *RS = cast<ReturnStmt>(S);
- if (const Expr *RE = RS->getRetValue())
- return getSVal(EnvironmentEntry(RE, LCtx), svalBuilder);
- return UndefinedVal();
- }
- // Handle all other Stmt* using a lookup.
- default:
- return lookupExpr(EnvironmentEntry(S, LCtx));
- }
- }
- Environment EnvironmentManager::bindExpr(Environment Env,
- const EnvironmentEntry &E,
- SVal V,
- bool Invalidate) {
- if (V.isUnknown()) {
- if (Invalidate)
- return Environment(F.remove(Env.ExprBindings, E));
- else
- return Env;
- }
- return Environment(F.add(Env.ExprBindings, E, V));
- }
- namespace {
- class MarkLiveCallback final : public SymbolVisitor {
- SymbolReaper &SymReaper;
- public:
- MarkLiveCallback(SymbolReaper &symreaper) : SymReaper(symreaper) {}
- bool VisitSymbol(SymbolRef sym) override {
- SymReaper.markLive(sym);
- return true;
- }
- bool VisitMemRegion(const MemRegion *R) override {
- SymReaper.markLive(R);
- return true;
- }
- };
- } // namespace
- // removeDeadBindings:
- // - Remove subexpression bindings.
- // - Remove dead block expression bindings.
- // - Keep live block expression bindings:
- // - Mark their reachable symbols live in SymbolReaper,
- // see ScanReachableSymbols.
- // - Mark the region in DRoots if the binding is a loc::MemRegionVal.
- Environment
- EnvironmentManager::removeDeadBindings(Environment Env,
- SymbolReaper &SymReaper,
- ProgramStateRef ST) {
- // We construct a new Environment object entirely, as this is cheaper than
- // individually removing all the subexpression bindings (which will greatly
- // outnumber block-level expression bindings).
- Environment NewEnv = getInitialEnvironment();
- MarkLiveCallback CB(SymReaper);
- ScanReachableSymbols RSScaner(ST, CB);
- llvm::ImmutableMapRef<EnvironmentEntry, SVal>
- EBMapRef(NewEnv.ExprBindings.getRootWithoutRetain(),
- F.getTreeFactory());
- // Iterate over the block-expr bindings.
- for (Environment::iterator I = Env.begin(), End = Env.end(); I != End; ++I) {
- const EnvironmentEntry &BlkExpr = I.getKey();
- const SVal &X = I.getData();
- const Expr *E = dyn_cast<Expr>(BlkExpr.getStmt());
- if (!E)
- continue;
- if (SymReaper.isLive(E, BlkExpr.getLocationContext())) {
- // Copy the binding to the new map.
- EBMapRef = EBMapRef.add(BlkExpr, X);
- // Mark all symbols in the block expr's value live.
- RSScaner.scan(X);
- }
- }
- NewEnv.ExprBindings = EBMapRef.asImmutableMap();
- return NewEnv;
- }
- void Environment::printJson(raw_ostream &Out, const ASTContext &Ctx,
- const LocationContext *LCtx, const char *NL,
- unsigned int Space, bool IsDot) const {
- Indent(Out, Space, IsDot) << "\"environment\": ";
- if (ExprBindings.isEmpty()) {
- Out << "null," << NL;
- return;
- }
- ++Space;
- if (!LCtx) {
- // Find the freshest location context.
- llvm::SmallPtrSet<const LocationContext *, 16> FoundContexts;
- for (const auto &I : *this) {
- const LocationContext *LC = I.first.getLocationContext();
- if (FoundContexts.count(LC) == 0) {
- // This context is fresher than all other contexts so far.
- LCtx = LC;
- for (const LocationContext *LCI = LC; LCI; LCI = LCI->getParent())
- FoundContexts.insert(LCI);
- }
- }
- }
- assert(LCtx);
- Out << "{ \"pointer\": \"" << (const void *)LCtx->getStackFrame()
- << "\", \"items\": [" << NL;
- PrintingPolicy PP = Ctx.getPrintingPolicy();
- LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) {
- // LCtx items begin
- bool HasItem = false;
- unsigned int InnerSpace = Space + 1;
- // Store the last ExprBinding which we will print.
- BindingsTy::iterator LastI = ExprBindings.end();
- for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end();
- ++I) {
- if (I->first.getLocationContext() != LC)
- continue;
- if (!HasItem) {
- HasItem = true;
- Out << '[' << NL;
- }
- const Stmt *S = I->first.getStmt();
- (void)S;
- assert(S != nullptr && "Expected non-null Stmt");
- LastI = I;
- }
- for (BindingsTy::iterator I = ExprBindings.begin(); I != ExprBindings.end();
- ++I) {
- if (I->first.getLocationContext() != LC)
- continue;
- const Stmt *S = I->first.getStmt();
- Indent(Out, InnerSpace, IsDot)
- << "{ \"stmt_id\": " << S->getID(Ctx) << ", \"pretty\": ";
- S->printJson(Out, nullptr, PP, /*AddQuotes=*/true);
- Out << ", \"value\": ";
- I->second.printJson(Out, /*AddQuotes=*/true);
- Out << " }";
- if (I != LastI)
- Out << ',';
- Out << NL;
- }
- if (HasItem)
- Indent(Out, --InnerSpace, IsDot) << ']';
- else
- Out << "null ";
- });
- Indent(Out, --Space, IsDot) << "]}," << NL;
- }
|