llvm/clang/lib/StaticAnalyzer/Core/RegionStore.cpp

//== RegionStore.cpp - Field-sensitive store model --------------*- C++ -*--==//
//
// 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 defines a basic region store model. In this model, we do have field
// sensitivity. But we assume nothing about the heap shape. So recursive data
// structures are largely ignored. Basically we do 1-limiting analysis.
// Parameter pointers are assumed with no aliasing. Pointee objects of
// parameters are created lazily.
//
//===----------------------------------------------------------------------===//

#include "clang/AST/Attr.h"
#include "clang/AST/CharUnits.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/Analysis/Analyses/LiveVariables.h"
#include "clang/Analysis/AnalysisDeclContext.h"
#include "clang/Basic/JsonSupport.h"
#include "clang/Basic/TargetInfo.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
#include "llvm/ADT/ImmutableMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <optional>
#include <utility>

usingnamespaceclang;
usingnamespaceento;

//===----------------------------------------------------------------------===//
// Representation of binding keys.
//===----------------------------------------------------------------------===//

namespace {
class BindingKey { … };
} // end anonymous namespace

BindingKey BindingKey::Make(const MemRegion *R, Kind k) { … }

namespace llvm {
static inline raw_ostream &operator<<(raw_ostream &Out, BindingKey K) { … }

} // namespace llvm

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void BindingKey::dump() const { llvm::errs() << *this; }
#endif

//===----------------------------------------------------------------------===//
// Actual Store type.
//===----------------------------------------------------------------------===//

ClusterBindings;
ClusterBindingsRef;
BindingPair;

RegionBindings;

namespace {
class RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *,
                                 ClusterBindings> { … };
} // end anonymous namespace

RegionBindingsConstRef;

std::optional<SVal>
RegionBindingsRef::getDirectBinding(const MemRegion *R) const { … }

std::optional<SVal>
RegionBindingsRef::getDefaultBinding(const MemRegion *R) const { … }

RegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal V) const { … }


RegionBindingsRef RegionBindingsRef::addBinding(const MemRegion *R,
                                                BindingKey::Kind k,
                                                SVal V) const { … }

const SVal *RegionBindingsRef::lookup(BindingKey K) const { … }

const SVal *RegionBindingsRef::lookup(const MemRegion *R,
                                      BindingKey::Kind k) const { … }

RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) { … }

RegionBindingsRef RegionBindingsRef::removeBinding(const MemRegion *R,
                                                BindingKey::Kind k){ … }

//===----------------------------------------------------------------------===//
// Main RegionStore logic.
//===----------------------------------------------------------------------===//

namespace {
class InvalidateRegionsWorker;

class RegionStoreManager : public StoreManager { … };

} // end anonymous namespace

//===----------------------------------------------------------------------===//
// RegionStore creation.
//===----------------------------------------------------------------------===//

std::unique_ptr<StoreManager>
ento::CreateRegionStoreManager(ProgramStateManager &StMgr) { … }

//===----------------------------------------------------------------------===//
// Region Cluster analysis.
//===----------------------------------------------------------------------===//

namespace {
/// Used to determine which global regions are automatically included in the
/// initial worklist of a ClusterAnalysis.
enum GlobalsFilterKind { … };

template <typename DERIVED>
class ClusterAnalysis  { … };
}

//===----------------------------------------------------------------------===//
// Binding invalidation.
//===----------------------------------------------------------------------===//

bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R,
                                              ScanReachableSymbols &Callbacks) { … }

static inline bool isUnionField(const FieldRegion *FR) { … }

FieldVector;

static void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields) { … }

static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields) { … }

/// Collects all bindings in \p Cluster that may refer to bindings within
/// \p Top.
///
/// Each binding is a pair whose \c first is the key (a BindingKey) and whose
/// \c second is the value (an SVal).
///
/// The \p IncludeAllDefaultBindings parameter specifies whether to include
/// default bindings that may extend beyond \p Top itself, e.g. if \p Top is
/// an aggregate within a larger aggregate with a default binding.
static void
collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings,
                         SValBuilder &SVB, const ClusterBindings &Cluster,
                         const SubRegion *Top, BindingKey TopKey,
                         bool IncludeAllDefaultBindings) { … }

static void
collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings,
                         SValBuilder &SVB, const ClusterBindings &Cluster,
                         const SubRegion *Top, bool IncludeAllDefaultBindings) { … }

RegionBindingsRef
RegionStoreManager::removeSubRegionBindings(RegionBindingsConstRef B,
                                            const SubRegion *Top) { … }

namespace {
class InvalidateRegionsWorker : public ClusterAnalysis<InvalidateRegionsWorker>
{ … };
}

bool InvalidateRegionsWorker::AddToWorkList(const MemRegion *R) { … }

void InvalidateRegionsWorker::VisitBinding(SVal V) { … }

void InvalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
                                           const ClusterBindings *C) { … }

bool InvalidateRegionsWorker::isInitiallyIncludedGlobalRegion(
    const MemRegion *R) { … }

bool InvalidateRegionsWorker::includeEntireMemorySpace(const MemRegion *Base) { … }

RegionBindingsRef
RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K,
                                           const Expr *Ex,
                                           unsigned Count,
                                           const LocationContext *LCtx,
                                           RegionBindingsRef B,
                                           InvalidatedRegions *Invalidated) { … }

void RegionStoreManager::populateWorkList(InvalidateRegionsWorker &W,
                                          ArrayRef<SVal> Values,
                                          InvalidatedRegions *TopLevelRegions) { … }

StoreRef
RegionStoreManager::invalidateRegions(Store store,
                                     ArrayRef<SVal> Values,
                                     const Expr *Ex, unsigned Count,
                                     const LocationContext *LCtx,
                                     const CallEvent *Call,
                                     InvalidatedSymbols &IS,
                                     RegionAndSymbolInvalidationTraits &ITraits,
                                     InvalidatedRegions *TopLevelRegions,
                                     InvalidatedRegions *Invalidated) { … }

//===----------------------------------------------------------------------===//
// Location and region casting.
//===----------------------------------------------------------------------===//

/// ArrayToPointer - Emulates the "decay" of an array to a pointer
///  type.  'Array' represents the lvalue of the array being decayed
///  to a pointer, and the returned SVal represents the decayed
///  version of that lvalue (i.e., a pointer to the first element of
///  the array).  This is called by ExprEngine when evaluating casts
///  from arrays to pointers.
SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) { … }

//===----------------------------------------------------------------------===//
// Loading values from regions.
//===----------------------------------------------------------------------===//

SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) { … }

static QualType getUnderlyingType(const SubRegion *R) { … }

/// Checks to see if store \p B has a lazy binding for region \p R.
///
/// If \p AllowSubregionBindings is \c false, a lazy binding will be rejected
/// if there are additional bindings within \p R.
///
/// Note that unlike RegionStoreManager::findLazyBinding, this will not search
/// for lazy bindings for super-regions of \p R.
static std::optional<nonloc::LazyCompoundVal>
getExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B,
                       const SubRegion *R, bool AllowSubregionBindings) { … }

std::pair<Store, const SubRegion *>
RegionStoreManager::findLazyBinding(RegionBindingsConstRef B,
                                   const SubRegion *R,
                                   const SubRegion *originalRegion) { … }

/// This is a helper function for `getConstantValFromConstArrayInitializer`.
///
/// Return an array of extents of the declared array type.
///
/// E.g. for `int x[1][2][3];` returns { 1, 2, 3 }.
static SmallVector<uint64_t, 2>
getConstantArrayExtents(const ConstantArrayType *CAT) { … }

/// This is a helper function for `getConstantValFromConstArrayInitializer`.
///
/// Return an array of offsets from nested ElementRegions and a root base
/// region. The array is never empty and a base region is never null.
///
/// E.g. for `Element{Element{Element{VarRegion},1},2},3}` returns { 3, 2, 1 }.
/// This represents an access through indirection: `arr[1][2][3];`
///
/// \param ER The given (possibly nested) ElementRegion.
///
/// \note The result array is in the reverse order of indirection expression:
/// arr[1][2][3] -> { 3, 2, 1 }. This helps to provide complexity O(n), where n
/// is a number of indirections. It may not affect performance in real-life
/// code, though.
static std::pair<SmallVector<SVal, 2>, const MemRegion *>
getElementRegionOffsetsWithBase(const ElementRegion *ER) { … }

/// This is a helper function for `getConstantValFromConstArrayInitializer`.
///
/// Convert array of offsets from `SVal` to `uint64_t` in consideration of
/// respective array extents.
/// \param SrcOffsets [in]   The array of offsets of type `SVal` in reversed
///   order (expectedly received from `getElementRegionOffsetsWithBase`).
/// \param ArrayExtents [in] The array of extents.
/// \param DstOffsets [out]  The array of offsets of type `uint64_t`.
/// \returns:
/// - `std::nullopt` for successful convertion.
/// - `UndefinedVal` or `UnknownVal` otherwise. It's expected that this SVal
///   will be returned as a suitable value of the access operation.
///   which should be returned as a correct
///
/// \example:
///   const int arr[10][20][30] = {}; // ArrayExtents { 10, 20, 30 }
///   int x1 = arr[4][5][6]; // SrcOffsets { NonLoc(6), NonLoc(5), NonLoc(4) }
///                          // DstOffsets { 4, 5, 6 }
///                          // returns std::nullopt
///   int x2 = arr[42][5][-6]; // returns UndefinedVal
///   int x3 = arr[4][5][x2];  // returns UnknownVal
static std::optional<SVal>
convertOffsetsFromSvalToUnsigneds(const SmallVector<SVal, 2> &SrcOffsets,
                                  const SmallVector<uint64_t, 2> ArrayExtents,
                                  SmallVector<uint64_t, 2> &DstOffsets) { … }

std::optional<SVal> RegionStoreManager::getConstantValFromConstArrayInitializer(
    RegionBindingsConstRef B, const ElementRegion *R) { … }

/// Returns an SVal, if possible, for the specified position of an
/// initialization list.
///
/// \param ILE The given initialization list.
/// \param Offsets The array of unsigned offsets. E.g. for the expression
///  `int x = arr[1][2][3];` an array should be { 1, 2, 3 }.
/// \param ElemT The type of the result SVal expression.
/// \return Optional SVal for the particular position in the initialization
///   list. E.g. for the list `{{1, 2},[3, 4],{5, 6}, {}}` offsets:
///   - {1, 1} returns SVal{4}, because it's the second position in the second
///     sublist;
///   - {3, 0} returns SVal{0}, because there's no explicit value at this
///     position in the sublist.
///
/// NOTE: Inorder to get a valid SVal, a caller shall guarantee valid offsets
/// for the given initialization list. Otherwise SVal can be an equivalent to 0
/// or lead to assertion.
std::optional<SVal> RegionStoreManager::getSValFromInitListExpr(
    const InitListExpr *ILE, const SmallVector<uint64_t, 2> &Offsets,
    QualType ElemT) { … }

/// Returns an SVal, if possible, for the specified position in a string
/// literal.
///
/// \param SL The given string literal.
/// \param Offset The unsigned offset. E.g. for the expression
///   `char x = str[42];` an offset should be 42.
///   E.g. for the string "abc" offset:
///   - 1 returns SVal{b}, because it's the second position in the string.
///   - 42 returns SVal{0}, because there's no explicit value at this
///     position in the string.
/// \param ElemT The type of the result SVal expression.
///
/// NOTE: We return `0` for every offset >= the literal length for array
/// declarations, like:
///   const char str[42] = "123"; // Literal length is 4.
///   char c = str[41];           // Offset is 41.
/// FIXME: Nevertheless, we can't do the same for pointer declaraions, like:
///   const char * const str = "123"; // Literal length is 4.
///   char c = str[41];               // Offset is 41. Returns `0`, but Undef
///                                   // expected.
/// It should be properly handled before reaching this point.
/// The main problem is that we can't distinguish between these declarations,
/// because in case of array we can get the Decl from VarRegion, but in case
/// of pointer the region is a StringRegion, which doesn't contain a Decl.
/// Possible solution could be passing an array extent along with the offset.
SVal RegionStoreManager::getSValFromStringLiteral(const StringLiteral *SL,
                                                  uint64_t Offset,
                                                  QualType ElemT) { … }

static std::optional<SVal> getDerivedSymbolForBinding(
    RegionBindingsConstRef B, const TypedValueRegion *BaseRegion,
    const TypedValueRegion *SubReg, const ASTContext &Ctx, SValBuilder &SVB) { … }

SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B,
                                              const ElementRegion* R) { … }

SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B,
                                            const FieldRegion* R) { … }

std::optional<SVal> RegionStoreManager::getBindingForDerivedDefaultValue(
    RegionBindingsConstRef B, const MemRegion *superR,
    const TypedValueRegion *R, QualType Ty) { … }

SVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion,
                                        RegionBindingsRef LazyBinding) { … }

SVal
RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
                                                      const TypedValueRegion *R,
                                                      QualType Ty) { … }

SVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B,
                                               const ObjCIvarRegion* R) { … }

SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B,
                                          const VarRegion *R) { … }

SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) { … }

const RegionStoreManager::SValListTy &
RegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) { … }

NonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B,
                                             const TypedValueRegion *R) { … }

static bool isRecordEmpty(const RecordDecl *RD) { … }

SVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B,
                                             const TypedValueRegion *R) { … }

SVal RegionStoreManager::getBindingForArray(RegionBindingsConstRef B,
                                            const TypedValueRegion *R) { … }

bool RegionStoreManager::includedInBindings(Store store,
                                            const MemRegion *region) const { … }

//===----------------------------------------------------------------------===//
// Binding values to regions.
//===----------------------------------------------------------------------===//

StoreRef RegionStoreManager::killBinding(Store ST, Loc L) { … }

RegionBindingsRef
RegionStoreManager::bind(RegionBindingsConstRef B, Loc L, SVal V) { … }

RegionBindingsRef
RegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B,
                                            const MemRegion *R,
                                            QualType T) { … }

std::optional<RegionBindingsRef> RegionStoreManager::tryBindSmallArray(
    RegionBindingsConstRef B, const TypedValueRegion *R, const ArrayType *AT,
    nonloc::LazyCompoundVal LCV) { … }

RegionBindingsRef
RegionStoreManager::bindArray(RegionBindingsConstRef B,
                              const TypedValueRegion* R,
                              SVal Init) { … }

RegionBindingsRef RegionStoreManager::bindVector(RegionBindingsConstRef B,
                                                 const TypedValueRegion* R,
                                                 SVal V) { … }

std::optional<RegionBindingsRef> RegionStoreManager::tryBindSmallStruct(
    RegionBindingsConstRef B, const TypedValueRegion *R, const RecordDecl *RD,
    nonloc::LazyCompoundVal LCV) { … }

RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B,
                                                 const TypedValueRegion *R,
                                                 SVal V) { … }

RegionBindingsRef
RegionStoreManager::bindAggregate(RegionBindingsConstRef B,
                                  const TypedRegion *R,
                                  SVal Val) { … }

//===----------------------------------------------------------------------===//
// State pruning.
//===----------------------------------------------------------------------===//

namespace {
class RemoveDeadBindingsWorker
    : public ClusterAnalysis<RemoveDeadBindingsWorker> { … };
}

bool RemoveDeadBindingsWorker::AddToWorkList(const MemRegion *R) { … }

void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR,
                                                   const ClusterBindings &C) { … }

void RemoveDeadBindingsWorker::VisitCluster(const MemRegion *baseR,
                                            const ClusterBindings *C) { … }

void RemoveDeadBindingsWorker::VisitBinding(SVal V) { … }

bool RemoveDeadBindingsWorker::UpdatePostponed() { … }

StoreRef RegionStoreManager::removeDeadBindings(Store store,
                                                const StackFrameContext *LCtx,
                                                SymbolReaper& SymReaper) { … }

//===----------------------------------------------------------------------===//
// Utility methods.
//===----------------------------------------------------------------------===//

void RegionStoreManager::printJson(raw_ostream &Out, Store S, const char *NL,
                                   unsigned int Space, bool IsDot) const { … }