blob: 64e915a09cebe02eaa290595ff7a76b58d880146 [file] [log] [blame]
//===- 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;
}