Analysis/FlowSensitive/DataflowEnvironment.h

//===-- DataflowEnvironment.h -----------------------------------*- 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 an Environment class that is used by dataflow analyses
//  that run over Control-Flow Graphs (CFGs) to keep track of the state of the
//  program at given program points.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H

#include "clang/AST/Decl.h"
#include "clang/AST/DeclBase.h"
#include "clang/AST/Expr.h"
#include "clang/AST/Type.h"
#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
#include "clang/Analysis/FlowSensitive/Formula.h"
#include "clang/Analysis/FlowSensitive/Logger.h"
#include "clang/Analysis/FlowSensitive/StorageLocation.h"
#include "clang/Analysis/FlowSensitive/Value.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/ErrorHandling.h"
#include <type_traits>
#include <utility>

namespace clang {
namespace dataflow {

/// Indicates the result of a tentative comparison.
enum class ComparisonResult {
  Same,
  Different,
  Unknown,
};

/// Holds the state of the program (store and heap) at a given program point.
///
/// WARNING: Symbolic values that are created by the environment for static
/// local and global variables are not currently invalidated on function calls.
/// This is unsound and should be taken into account when designing dataflow
/// analyses.
class Environment {
public:
  /// Supplements `Environment` with non-standard comparison and join
  /// operations.
  class ValueModel {
  public:
    virtual ~ValueModel() = default;

    /// Returns:
    ///   `Same`: `Val1` is equivalent to `Val2`, according to the model.
    ///   `Different`: `Val1` is distinct from `Val2`, according to the model.
    ///   `Unknown`: The model can't determine a relationship between `Val1` and
    ///    `Val2`.
    ///
    /// Requirements:
    ///
    ///  `Val1` and `Val2` must be distinct.
    ///
    ///  `Val1` and `Val2` must model values of type `Type`.
    ///
    ///  `Val1` and `Val2` must be assigned to the same storage location in
    ///  `Env1` and `Env2` respectively.
    virtual ComparisonResult compare(QualType Type, const Value &Val1,
                                     const Environment &Env1, const Value &Val2,
                                     const Environment &Env2) {
      // FIXME: Consider adding QualType to RecordValue and removing the Type
      // argument here.
      return ComparisonResult::Unknown;
    }

    /// Modifies `JoinedVal` to approximate both `Val1` and `Val2`. This should
    /// obey the properties of a lattice join.
    ///
    /// `Env1` and `Env2` can be used to query child values and path condition
    /// implications of `Val1` and `Val2` respectively.
    ///
    /// Requirements:
    ///
    ///  `Val1` and `Val2` must be distinct.
    ///
    ///  `Val1`, `Val2`, and `JoinedVal` must model values of type `Type`.
    ///
    ///  `Val1` and `Val2` must be assigned to the same storage location in
    ///  `Env1` and `Env2` respectively.
    virtual void join(QualType Type, const Value &Val1, const Environment &Env1,
                      const Value &Val2, const Environment &Env2,
                      Value &JoinedVal, Environment &JoinedEnv) {}

    /// This function may widen the current value -- replace it with an
    /// approximation that can reach a fixed point more quickly than iterated
    /// application of the transfer function alone. The previous value is
    /// provided to inform the choice of widened value. The function must also
    /// serve as a comparison operation, by indicating whether the widened value
    /// is equivalent to the previous value.
    ///
    /// Returns either:
    ///
    ///   `nullptr`, if this value is not of interest to the model, or
    ///
    ///   `&Prev`, if the widened value is equivalent to `Prev`, or
    ///
    ///   A non-null value that approximates `Current`. `Prev` is available to
    ///   inform the chosen approximation.
    ///
    /// `PrevEnv` and `CurrentEnv` can be used to query child values and path
    /// condition implications of `Prev` and `Current`, respectively.
    ///
    /// Requirements:
    ///
    ///  `Prev` and `Current` must model values of type `Type`.
    ///
    ///  `Prev` and `Current` must be assigned to the same storage location in
    ///  `PrevEnv` and `CurrentEnv`, respectively.
    virtual Value *widen(QualType Type, Value &Prev, const Environment &PrevEnv,
                         Value &Current, Environment &CurrentEnv) {
      // The default implementation reduces to just comparison, since comparison
      // is required by the API, even if no widening is performed.
      switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) {
        case ComparisonResult::Same:
          return &Prev;
        case ComparisonResult::Different:
          return &Current;
        case ComparisonResult::Unknown:
          return nullptr;
      }
      llvm_unreachable("all cases in switch covered");
    }
  };

  /// Creates an environment that uses `DACtx` to store objects that encompass
  /// the state of a program.
  explicit Environment(DataflowAnalysisContext &DACtx);

  // Copy-constructor is private, Environments should not be copied. See fork().
  Environment &operator=(const Environment &Other) = delete;

  Environment(Environment &&Other) = default;
  Environment &operator=(Environment &&Other) = default;

  /// Creates an environment that uses `DACtx` to store objects that encompass
  /// the state of a program.
  ///
  /// If `DeclCtx` is a function, initializes the environment with symbolic
  /// representations of the function parameters.
  ///
  /// If `DeclCtx` is a non-static member function, initializes the environment
  /// with a symbolic representation of the `this` pointee.
  Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx);

  /// Assigns storage locations and values to all parameters, captures, global
  /// variables, fields and functions referenced in the function currently being
  /// analyzed.
  ///
  /// Requirements:
  ///
  ///  The function must have a body, i.e.
  ///  `FunctionDecl::doesThisDecalarationHaveABody()` must be true.
  void initialize();

  /// Returns a new environment that is a copy of this one.
  ///
  /// The state of the program is initially the same, but can be mutated without
  /// affecting the original.
  ///
  /// However the original should not be further mutated, as this may interfere
  /// with the fork. (In practice, values are stored independently, but the
  /// forked flow condition references the original).
  Environment fork() const;

  /// Creates and returns an environment to use for an inline analysis  of the
  /// callee. Uses the storage location from each argument in the `Call` as the
  /// storage location for the corresponding parameter in the callee.
  ///
  /// Requirements:
  ///
  ///  The callee of `Call` must be a `FunctionDecl`.
  ///
  ///  The body of the callee must not reference globals.
  ///
  ///  The arguments of `Call` must map 1:1 to the callee's parameters.
  Environment pushCall(const CallExpr *Call) const;
  Environment pushCall(const CXXConstructExpr *Call) const;

  /// Moves gathered information back into `this` from a `CalleeEnv` created via
  /// `pushCall`.
  void popCall(const CallExpr *Call, const Environment &CalleeEnv);
  void popCall(const CXXConstructExpr *Call, const Environment &CalleeEnv);

  /// Returns true if and only if the environment is equivalent to `Other`, i.e
  /// the two environments:
  ///  - have the same mappings from declarations to storage locations,
  ///  - have the same mappings from expressions to storage locations,
  ///  - have the same or equivalent (according to `Model`) values assigned to
  ///    the same storage locations.
  ///
  /// Requirements:
  ///
  ///  `Other` and `this` must use the same `DataflowAnalysisContext`.
  bool equivalentTo(const Environment &Other,
                    Environment::ValueModel &Model) const;

  /// How to treat expression state (`ExprToLoc` and `ExprToVal`) in a join.
  /// If the join happens within a full expression, expression state should be
  /// kept; otherwise, we can discard it.
  enum ExprJoinBehavior {
    DiscardExprState,
    KeepExprState,
  };

  /// Joins two environments by taking the intersection of storage locations and
  /// values that are stored in them. Distinct values that are assigned to the
  /// same storage locations in `EnvA` and `EnvB` are merged using `Model`.
  ///
  /// Requirements:
  ///
  ///  `EnvA` and `EnvB` must use the same `DataflowAnalysisContext`.
  static Environment join(const Environment &EnvA, const Environment &EnvB,
                          Environment::ValueModel &Model,
                          ExprJoinBehavior ExprBehavior);

  /// Widens the environment point-wise, using `PrevEnv` as needed to inform the
  /// approximation.
  ///
  /// Requirements:
  ///
  ///  `PrevEnv` must be the immediate previous version of the environment.
  ///  `PrevEnv` and `this` must use the same `DataflowAnalysisContext`.
  LatticeJoinEffect widen(const Environment &PrevEnv,
                          Environment::ValueModel &Model);

  // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`,
  // `getStableStorageLocation`, or something more appropriate.

  /// Creates a storage location appropriate for `Type`. Does not assign a value
  /// to the returned storage location in the environment.
  ///
  /// Requirements:
  ///
  ///  `Type` must not be null.
  StorageLocation &createStorageLocation(QualType Type);

  /// Creates a storage location for `D`. Does not assign the returned storage
  /// location to `D` in the environment. Does not assign a value to the
  /// returned storage location in the environment.
  StorageLocation &createStorageLocation(const ValueDecl &D);

  /// Creates a storage location for `E`. Does not assign the returned storage
  /// location to `E` in the environment. Does not assign a value to the
  /// returned storage location in the environment.
  StorageLocation &createStorageLocation(const Expr &E);

  /// Assigns `Loc` as the storage location of `D` in the environment.
  ///
  /// Requirements:
  ///
  ///  `D` must not already have a storage location in the environment.
  void setStorageLocation(const ValueDecl &D, StorageLocation &Loc);

  /// Returns the storage location assigned to `D` in the environment, or null
  /// if `D` isn't assigned a storage location in the environment.
  StorageLocation *getStorageLocation(const ValueDecl &D) const;

  /// Removes the location assigned to `D` in the environment (if any).
  void removeDecl(const ValueDecl &D);

  /// Assigns `Loc` as the storage location of the glvalue `E` in the
  /// environment.
  ///
  /// Requirements:
  ///
  ///  `E` must not be assigned a storage location in the environment.
  ///  `E` must be a glvalue or a `BuiltinType::BuiltinFn`
  void setStorageLocation(const Expr &E, StorageLocation &Loc);

  /// Returns the storage location assigned to the glvalue `E` in the
  /// environment, or null if `E` isn't assigned a storage location in the
  /// environment.
  ///
  /// Requirements:
  ///  `E` must be a glvalue or a `BuiltinType::BuiltinFn`
  StorageLocation *getStorageLocation(const Expr &E) const;

  /// Returns the result of casting `getStorageLocation(...)` to a subclass of
  /// `StorageLocation` (using `cast_or_null<T>`).
  /// This assert-fails if the result of `getStorageLocation(...)` is not of
  /// type `T *`; if the storage location is not guaranteed to have type `T *`,
  /// consider using `dyn_cast_or_null<T>(getStorageLocation(...))` instead.
  template <typename T>
  std::enable_if_t<std::is_base_of_v<StorageLocation, T>, T *>
  get(const ValueDecl &D) const {
    return cast_or_null<T>(getStorageLocation(D));
  }
  template <typename T>
  std::enable_if_t<std::is_base_of_v<StorageLocation, T>, T *>
  get(const Expr &E) const {
    return cast_or_null<T>(getStorageLocation(E));
  }

  /// Returns the storage location assigned to the `this` pointee in the
  /// environment or null if the `this` pointee has no assigned storage location
  /// in the environment.
  RecordStorageLocation *getThisPointeeStorageLocation() const {
    return ThisPointeeLoc;
  }

  /// Sets the storage location assigned to the `this` pointee in the
  /// environment.
  void setThisPointeeStorageLocation(RecordStorageLocation &Loc) {
    ThisPointeeLoc = &Loc;
  }

  /// Returns the location of the result object for a record-type prvalue.
  ///
  /// In C++, prvalues of record type serve only a limited purpose: They can
  /// only be used to initialize a result object (e.g. a variable or a
  /// temporary). This function returns the location of that result object.
  ///
  /// When creating a prvalue of record type, we already need the storage
  /// location of the result object to pass in `this`, even though prvalues are
  /// otherwise not associated with storage locations.
  ///
  /// FIXME: Currently, this simply returns a stable storage location for `E`,
  /// but this doesn't do the right thing in scenarios like the following:
  /// ```
  /// MyClass c = some_condition()? MyClass(foo) : MyClass(bar);
  /// ```
  /// Here, `MyClass(foo)` and `MyClass(bar)` will have two different storage
  /// locations, when in fact their storage locations should be the same.
  /// Eventually, we want to propagate storage locations from result objects
  /// down to the prvalues that initialize them, similar to the way that this is
  /// done in Clang's CodeGen.
  ///
  /// Requirements:
  ///  `E` must be a prvalue of record type.
  RecordStorageLocation &
  getResultObjectLocation(const Expr &RecordPRValue) const;

  /// Returns the return value of the current function. This can be null if:
  /// - The function has a void return type
  /// - No return value could be determined for the function, for example
  ///   because it calls a function without a body.
  ///
  /// Requirements:
  ///  The current function must have a non-reference return type.
  Value *getReturnValue() const {
    assert(getCurrentFunc() != nullptr &&
           !getCurrentFunc()->getReturnType()->isReferenceType());
    return ReturnVal;
  }

  /// Returns the storage location for the reference returned by the current
  /// function. This can be null if function doesn't return a single consistent
  /// reference.
  ///
  /// Requirements:
  ///  The current function must have a reference return type.
  StorageLocation *getReturnStorageLocation() const {
    assert(getCurrentFunc() != nullptr &&
           getCurrentFunc()->getReturnType()->isReferenceType());
    return ReturnLoc;
  }

  /// Sets the return value of the current function.
  ///
  /// Requirements:
  ///  The current function must have a non-reference return type.
  void setReturnValue(Value *Val) {
    assert(getCurrentFunc() != nullptr &&
           !getCurrentFunc()->getReturnType()->isReferenceType());
    ReturnVal = Val;
  }

  /// Sets the storage location for the reference returned by the current
  /// function.
  ///
  /// Requirements:
  ///  The current function must have a reference return type.
  void setReturnStorageLocation(StorageLocation *Loc) {
    assert(getCurrentFunc() != nullptr &&
           getCurrentFunc()->getReturnType()->isReferenceType());
    ReturnLoc = Loc;
  }

  /// Returns a pointer value that represents a null pointer. Calls with
  /// `PointeeType` that are canonically equivalent will return the same result.
  PointerValue &getOrCreateNullPointerValue(QualType PointeeType);

  /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
  /// returns null.
  ///
  /// If `Type` is a pointer or reference type, creates all the necessary
  /// storage locations and values for indirections until it finds a
  /// non-pointer/non-reference type.
  ///
  /// If `Type` is a class, struct, or union type, creates values for all
  /// modeled fields (including synthetic fields) and calls `setValue()` to
  /// associate the `RecordValue` with its storage location
  /// (`RecordValue::getLoc()`).
  ///
  /// If `Type` is one of the following types, this function will always return
  /// a non-null pointer:
  /// - `bool`
  /// - Any integer type
  /// - Any class, struct, or union type
  ///
  /// Requirements:
  ///
  ///  `Type` must not be null.
  Value *createValue(QualType Type);

  /// Creates an object (i.e. a storage location with an associated value) of
  /// type `Ty`. If `InitExpr` is non-null and has a value associated with it,
  /// initializes the object with this value. Otherwise, initializes the object
  /// with a value created using `createValue()`.
  StorageLocation &createObject(QualType Ty, const Expr *InitExpr = nullptr) {
    return createObjectInternal(nullptr, Ty, InitExpr);
  }

  /// Creates an object for the variable declaration `D`. If `D` has an
  /// initializer and this initializer is associated with a value, initializes
  /// the object with this value.  Otherwise, initializes the object with a
  /// value created using `createValue()`. Uses the storage location returned by
  /// `DataflowAnalysisContext::getStableStorageLocation(D)`.
  StorageLocation &createObject(const VarDecl &D) {
    return createObjectInternal(&D, D.getType(), D.getInit());
  }

  /// Creates an object for the variable declaration `D`. If `InitExpr` is
  /// non-null and has a value associated with it, initializes the object with
  /// this value. Otherwise, initializes the object with a value created using
  /// `createValue()`.  Uses the storage location returned by
  /// `DataflowAnalysisContext::getStableStorageLocation(D)`.
  StorageLocation &createObject(const ValueDecl &D, const Expr *InitExpr) {
    return createObjectInternal(&D, D.getType(), InitExpr);
  }

  /// Initializes the fields (including synthetic fields) of `Loc` with values,
  /// unless values of the field type are not supported or we hit one of the
  /// limits at which we stop producing values.
  void initializeFieldsWithValues(RecordStorageLocation &Loc);

  /// Assigns `Val` as the value of `Loc` in the environment.
  void setValue(const StorageLocation &Loc, Value &Val);

  /// Clears any association between `Loc` and a value in the environment.
  void clearValue(const StorageLocation &Loc) { LocToVal.erase(&Loc); }

  /// Assigns `Val` as the value of the prvalue `E` in the environment.
  ///
  /// Requirements:
  ///
  ///  - `E` must be a prvalue
  ///  - If `Val` is a `RecordValue`, its `RecordStorageLocation` must be
  ///    `getResultObjectLocation(E)`. An exception to this is if `E` is an
  ///    expression that originally creates a `RecordValue` (such as a
  ///    `CXXConstructExpr` or `CallExpr`), as these establish the location of
  ///    the result object in the first place.
  void setValue(const Expr &E, Value &Val);

  /// Returns the value assigned to `Loc` in the environment or null if `Loc`
  /// isn't assigned a value in the environment.
  Value *getValue(const StorageLocation &Loc) const;

  /// Equivalent to `getValue(getStorageLocation(D))` if `D` is assigned a
  /// storage location in the environment, otherwise returns null.
  Value *getValue(const ValueDecl &D) const;

  /// Equivalent to `getValue(getStorageLocation(E, SP))` if `E` is assigned a
  /// storage location in the environment, otherwise returns null.
  Value *getValue(const Expr &E) const;

  /// Returns the result of casting `getValue(...)` to a subclass of `Value`
  /// (using `cast_or_null<T>`).
  /// This assert-fails if the result of `getValue(...)` is not of type `T *`;
  /// if the value is not guaranteed to have type `T *`, consider using
  /// `dyn_cast_or_null<T>(getValue(...))` instead.
  template <typename T>
  std::enable_if_t<std::is_base_of_v<Value, T>, T *>
  get(const StorageLocation &Loc) const {
    return cast_or_null<T>(getValue(Loc));
  }
  template <typename T>
  std::enable_if_t<std::is_base_of_v<Value, T>, T *>
  get(const ValueDecl &D) const {
    return cast_or_null<T>(getValue(D));
  }
  template <typename T>
  std::enable_if_t<std::is_base_of_v<Value, T>, T *> get(const Expr &E) const {
    return cast_or_null<T>(getValue(E));
  }

  // FIXME: should we deprecate the following & call arena().create() directly?

  /// Creates a `T` (some subclass of `Value`), forwarding `args` to the
  /// constructor, and returns a reference to it.
  ///
  /// The analysis context takes ownership of the created object. The object
  /// will be destroyed when the analysis context is destroyed.
  template <typename T, typename... Args>
  std::enable_if_t<std::is_base_of<Value, T>::value, T &>
  create(Args &&...args) {
    return arena().create<T>(std::forward<Args>(args)...);
  }

  /// Returns a symbolic integer value that models an integer literal equal to
  /// `Value`
  IntegerValue &getIntLiteralValue(llvm::APInt Value) const {
    return arena().makeIntLiteral(Value);
  }

  /// Returns a symbolic boolean value that models a boolean literal equal to
  /// `Value`
  BoolValue &getBoolLiteralValue(bool Value) const {
    return arena().makeBoolValue(arena().makeLiteral(Value));
  }

  /// Returns an atomic boolean value.
  BoolValue &makeAtomicBoolValue() const {
    return arena().makeAtomValue();
  }

  /// Returns a unique instance of boolean Top.
  BoolValue &makeTopBoolValue() const {
    return arena().makeTopValue();
  }

  /// Returns a boolean value that represents the conjunction of `LHS` and
  /// `RHS`. Subsequent calls with the same arguments, regardless of their
  /// order, will return the same result. If the given boolean values represent
  /// the same value, the result will be the value itself.
  BoolValue &makeAnd(BoolValue &LHS, BoolValue &RHS) const {
    return arena().makeBoolValue(
        arena().makeAnd(LHS.formula(), RHS.formula()));
  }

  /// Returns a boolean value that represents the disjunction of `LHS` and
  /// `RHS`. Subsequent calls with the same arguments, regardless of their
  /// order, will return the same result. If the given boolean values represent
  /// the same value, the result will be the value itself.
  BoolValue &makeOr(BoolValue &LHS, BoolValue &RHS) const {
    return arena().makeBoolValue(
        arena().makeOr(LHS.formula(), RHS.formula()));
  }

  /// Returns a boolean value that represents the negation of `Val`. Subsequent
  /// calls with the same argument will return the same result.
  BoolValue &makeNot(BoolValue &Val) const {
    return arena().makeBoolValue(arena().makeNot(Val.formula()));
  }

  /// Returns a boolean value represents `LHS` => `RHS`. Subsequent calls with
  /// the same arguments, will return the same result. If the given boolean
  /// values represent the same value, the result will be a value that
  /// represents the true boolean literal.
  BoolValue &makeImplication(BoolValue &LHS, BoolValue &RHS) const {
    return arena().makeBoolValue(
        arena().makeImplies(LHS.formula(), RHS.formula()));
  }

  /// Returns a boolean value represents `LHS` <=> `RHS`. Subsequent calls with
  /// the same arguments, regardless of their order, will return the same
  /// result. If the given boolean values represent the same value, the result
  /// will be a value that represents the true boolean literal.
  BoolValue &makeIff(BoolValue &LHS, BoolValue &RHS) const {
    return arena().makeBoolValue(
        arena().makeEquals(LHS.formula(), RHS.formula()));
  }

  /// Returns a boolean variable that identifies the flow condition (FC).
  ///
  /// The flow condition is a set of facts that are necessarily true when the
  /// program reaches the current point, expressed as boolean formulas.
  /// The flow condition token is equivalent to the AND of these facts.
  ///
  /// These may e.g. constrain the value of certain variables. A pointer
  /// variable may have a consistent modeled PointerValue throughout, but at a
  /// given point the Environment may tell us that the value must be non-null.
  ///
  /// The FC is necessary but not sufficient for this point to be reachable.
  /// In particular, where the FC token appears in flow conditions of successor
  /// environments, it means "point X may have been reached", not
  /// "point X was reached".
  Atom getFlowConditionToken() const { return FlowConditionToken; }

  /// Record a fact that must be true if this point in the program is reached.
  void assume(const Formula &);

  /// Returns true if the formula is always true when this point is reached.
  /// Returns false if the formula may be false (or the flow condition isn't
  /// sufficiently precise to prove that it is true) or if the solver times out.
  ///
  /// Note that there is an asymmetry between this function and `allows()` in
  /// that they both return false if the solver times out. The assumption is
  /// that if `proves()` or `allows()` returns true, this will result in a
  /// diagnostic, and we want to bias towards false negatives in the case where
  /// the solver times out.
  bool proves(const Formula &) const;

  /// Returns true if the formula may be true when this point is reached.
  /// Returns false if the formula is always false when this point is reached
  /// (or the flow condition is overly constraining) or if the solver times out.
  bool allows(const Formula &) const;

  /// Returns the `DeclContext` of the block being analysed, if any. Otherwise,
  /// returns null.
  const DeclContext *getDeclCtx() const { return CallStack.back(); }

  /// Returns the function currently being analyzed, or null if the code being
  /// analyzed isn't part of a function.
  const FunctionDecl *getCurrentFunc() const {
    return dyn_cast<FunctionDecl>(getDeclCtx());
  }

  /// Returns the size of the call stack.
  size_t callStackSize() const { return CallStack.size(); }

  /// Returns whether this `Environment` can be extended to analyze the given
  /// `Callee` (i.e. if `pushCall` can be used), with recursion disallowed and a
  /// given `MaxDepth`.
  bool canDescend(unsigned MaxDepth, const DeclContext *Callee) const;

  /// Returns the `DataflowAnalysisContext` used by the environment.
  DataflowAnalysisContext &getDataflowAnalysisContext() const { return *DACtx; }

  Arena &arena() const { return DACtx->arena(); }

  LLVM_DUMP_METHOD void dump() const;
  LLVM_DUMP_METHOD void dump(raw_ostream &OS) const;

private:
  // The copy-constructor is for use in fork() only.
  Environment(const Environment &) = default;

  /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
  /// return null.
  ///
  /// Recursively initializes storage locations and values until it sees a
  /// self-referential pointer or reference type. `Visited` is used to track
  /// which types appeared in the reference/pointer chain in order to avoid
  /// creating a cyclic dependency with self-referential pointers/references.
  ///
  /// Requirements:
  ///
  ///  `Type` must not be null.
  Value *createValueUnlessSelfReferential(QualType Type,
                                          llvm::DenseSet<QualType> &Visited,
                                          int Depth, int &CreatedValuesCount);

  /// Creates a storage location for `Ty`. Also creates and associates a value
  /// with the storage location, unless values of this type are not supported or
  /// we hit one of the limits at which we stop producing values (controlled by
  /// `Visited`, `Depth`, and `CreatedValuesCount`).
  StorageLocation &createLocAndMaybeValue(QualType Ty,
                                          llvm::DenseSet<QualType> &Visited,
                                          int Depth, int &CreatedValuesCount);

  /// Initializes the fields (including synthetic fields) of `Loc` with values,
  /// unless values of the field type are not supported or we hit one of the
  /// limits at which we stop producing values (controlled by `Visited`,
  /// `Depth`, and `CreatedValuesCount`).
  void initializeFieldsWithValues(RecordStorageLocation &Loc,
                                  llvm::DenseSet<QualType> &Visited, int Depth,
                                  int &CreatedValuesCount);

  /// Shared implementation of `createObject()` overloads.
  /// `D` and `InitExpr` may be null.
  StorageLocation &createObjectInternal(const ValueDecl *D, QualType Ty,
                                        const Expr *InitExpr);

  /// Shared implementation of `pushCall` overloads. Note that unlike
  /// `pushCall`, this member is invoked on the environment of the callee, not
  /// of the caller.
  void pushCallInternal(const FunctionDecl *FuncDecl,
                        ArrayRef<const Expr *> Args);

  /// Assigns storage locations and values to all global variables, fields
  /// and functions referenced in `FuncDecl`. `FuncDecl` must have a body.
  void initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl);

  // `DACtx` is not null and not owned by this object.
  DataflowAnalysisContext *DACtx;

  // FIXME: move the fields `CallStack`, `ReturnVal`, `ReturnLoc` and
  // `ThisPointeeLoc` into a separate call-context object, shared between
  // environments in the same call.
  // https://github.com/llvm/llvm-project/issues/59005

  // `DeclContext` of the block being analysed if provided.
  std::vector<const DeclContext *> CallStack;

  // Value returned by the function (if it has non-reference return type).
  Value *ReturnVal = nullptr;
  // Storage location of the reference returned by the function (if it has
  // reference return type).
  StorageLocation *ReturnLoc = nullptr;
  // The storage location of the `this` pointee. Should only be null if the
  // function being analyzed is only a function and not a method.
  RecordStorageLocation *ThisPointeeLoc = nullptr;

  // Maps from declarations and glvalue expression to storage locations that are
  // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these
  // include only storage locations that are in scope for a particular basic
  // block.
  llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
  llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
  // Maps from prvalue expressions and storage locations to the values that
  // are assigned to them.
  // We preserve insertion order so that join/widen process values in
  // deterministic sequence. This in turn produces deterministic SAT formulas.
  llvm::MapVector<const Expr *, Value *> ExprToVal;
  llvm::MapVector<const StorageLocation *, Value *> LocToVal;

  Atom FlowConditionToken;
};

/// Returns the storage location for the implicit object of a
/// `CXXMemberCallExpr`, or null if none is defined in the environment.
/// Dereferences the pointer if the member call expression was written using
/// `->`.
RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE,
                                                 const Environment &Env);

/// Returns the storage location for the base object of a `MemberExpr`, or null
/// if none is defined in the environment. Dereferences the pointer if the
/// member expression was written using `->`.
RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME,
                                             const Environment &Env);

/// Returns the fields of a `RecordDecl` that are initialized by an
/// `InitListExpr`, in the order in which they appear in
/// `InitListExpr::inits()`.
/// `Init->getType()` must be a record type.
std::vector<const FieldDecl *>
getFieldsForInitListExpr(const InitListExpr *InitList);

/// Associates a new `RecordValue` with `Loc` and returns the new value.
RecordValue &refreshRecordValue(RecordStorageLocation &Loc, Environment &Env);

/// Associates a new `RecordValue` with `Expr` and returns the new value.
RecordValue &refreshRecordValue(const Expr &Expr, Environment &Env);

} // namespace dataflow
} // namespace clang

#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H