text: //===--- SILConstants.h - SIL constant representation -----------*- C++ -*-===//
  //
  // This source file is part of the Swift.org open source project
  //
  // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
  // Licensed under Apache License v2.0 with Runtime Library Exception
  //
  // See https://swift.org/LICENSE.txt for license information
  // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
  //
  //===----------------------------------------------------------------------===//
  //
  // This defines an interface to represent SIL level structured constants in a
  // memory efficient way.
  //
  //===----------------------------------------------------------------------===//
  
  #ifndef SWIFT_SIL_CONSTANTS_H
  #define SWIFT_SIL_CONSTANTS_H
  
  #include "swift/SIL/SILValue.h"
  #include "llvm/Support/CommandLine.h"
  
  
  namespace swift {
  class SingleValueInstruction;
  class SILValue;
  class SILBuilder;
  class SerializedSILLoader;
  
  struct SymbolicArrayStorage;
  struct DerivedAddressValue;
  struct EnumWithPayloadSymbolicValue;
  struct SymbolicValueMemoryObject;
  struct UnknownSymbolicValue;
  struct SymbolicClosure;
  
  extern llvm::cl::opt<unsigned> ConstExprLimit;
  
  /// An abstract class that exposes functions for allocating symbolic values.
  /// The implementors of this class have to determine where to allocate them and
  /// and manage the lifetime of the allocated symbolic values.
  class SymbolicValueAllocator {
  public:
    virtual ~SymbolicValueAllocator() {}
  
    /// Allocate raw bytes.
    /// \param byteSize number of bytes to allocate.
    /// \param alignment alignment for the allocated bytes.
    virtual void *allocate(unsigned long byteSize, unsigned alignment) = 0;
  
    /// Allocate storage for a given number of elements of a specific type
    /// provided as a template parameter. Precondition: \c T must have an
    /// accesible zero argument constructor.
    /// \param numElts number of elements of the type to allocate.
    template <typename T> T *allocate(unsigned numElts) {
      T *res = (T *)allocate(sizeof(T) * numElts, alignof(T));
      for (unsigned i = 0; i != numElts; ++i)
        new (res + i) T();
      return res;
    }
  };
  
  /// A class that allocates symbolic values in a local bump allocator. The
  /// lifetime of the bump allocator is same as the lifetime of \c this object.
  class SymbolicValueBumpAllocator : public SymbolicValueAllocator {
  private:
    llvm::BumpPtrAllocator bumpAllocator;
  
  public:
    SymbolicValueBumpAllocator() {}
    ~SymbolicValueBumpAllocator() {}
  
    void *allocate(unsigned long byteSize, unsigned alignment) {
      return bumpAllocator.Allocate(byteSize, alignment);
    }
  };
  
  /// When we fail to constant fold a value, this captures a reason why,
  /// allowing the caller to produce a specific diagnostic.  The "Unknown"
  /// SymbolicValue representation also includes a pointer to the SILNode in
  /// question that was problematic.
  class UnknownReason {
  public:
    enum UnknownKind {
      // TODO: Eliminate the default kind, by making classifications for each
      // failure mode.
      Default,
  
      /// The constant expression was too big.  This is reported on a random
      /// instruction within the constexpr that triggered the issue.
      TooManyInstructions,
  
      /// A control flow loop was found.
      Loop,
  
      /// Integer overflow detected.
      Overflow,
  
      /// Trap detected. Traps will a message as a payload.
      Trap,
  
      /// An operation was applied over operands whose symbolic values were
      /// constants but were not valid for the operation.
      InvalidOperandValue,
  
      /// Encountered an instruction not supported by the interpreter.
      UnsupportedInstruction,
  
      /// Encountered a function call where the body of the called function is
      /// not available.
      CalleeImplementationUnknown,
  
      /// Attempted to load from/store into a SIL value that was not tracked by
      /// the interpreter.
      UntrackedSILValue,
  
      /// Attempted to find a concrete protocol conformance for a witness method
      /// and failed.
      UnknownWitnessMethodConformance,
  
      /// Attempted to determine the SIL function of a witness method  and failed.
      NoWitnesTableEntry,
  
      /// The value of a top-level variable cannot be determined to be a constant.
      /// This is only relevant in the backward evaluation mode, which is used by
      /// #assert.
      NotTopLevelConstant,
  
      /// A top-level value has multiple writers. This is only relevant in the
      /// non-flow-sensitive evaluation mode,  which is used by #assert.
      MutipleTopLevelWriters,
  
      /// Indicates the return value of an instruction that was not evaluated
      /// during interpretation.
      ReturnedByUnevaluatedInstruction,
  
      /// Indicates that the value was possibly modified by an instruction
      /// that was not evaluated during the interpretation.
      MutatedByUnevaluatedInstruction,
    };
  
  private:
    UnknownKind kind;
  
    // Auxiliary information for different unknown kinds.
    union {
      SILFunction *function;
      const char *trapMessage;
    } payload;
  
  public:
    UnknownKind getKind() { return kind; }
  
    static bool isUnknownKindWithPayload(UnknownKind kind) {
      switch (kind) {
      case UnknownKind::CalleeImplementationUnknown:
      case UnknownKind::Trap:
        return true;
      default:
        return false;
      }
    }
  
    static UnknownReason create(UnknownKind kind) {
      assert(!isUnknownKindWithPayload(kind));
      UnknownReason reason;
      reason.kind = kind;
      return reason;
    }
  
    static UnknownReason createCalleeImplementationUnknown(SILFunction *callee) {
      assert(callee);
      UnknownReason reason;
      reason.kind = UnknownKind::CalleeImplementationUnknown;
      reason.payload.function = callee;
      return reason;
    }
  
    SILFunction *getCalleeWithoutImplmentation() {
      assert(kind == UnknownKind::CalleeImplementationUnknown);
      return payload.function;
    }
  
    static UnknownReason createTrap(StringRef message,
                                    SymbolicValueAllocator &allocator) {
      // Copy and null terminate the string.
      size_t size = message.size();
      char *messagePtr = allocator.allocate<char>(size + 1);
      std::uninitialized_copy(message.begin(), message.end(), messagePtr);
      messagePtr[size] = '\0';
  
      UnknownReason reason;
      reason.kind = UnknownKind::Trap;
      reason.payload.trapMessage = messagePtr;
      return reason;
    }
  
    const char *getTrapMessage() {
      assert(kind == UnknownKind::Trap);
      return payload.trapMessage;
    }
  };
  
  /// This is the symbolic value tracked for each SILValue in a scope.  We
  /// support multiple representational forms for the constant node in order to
  /// avoid pointless memory bloat + copying.  This is intended to be a
  /// light-weight POD type we can put in hash tables and pass around by-value.
  ///
  /// Internally, this value has multiple ways to represent the same sorts of
  /// symbolic values (e.g. to save memory).  It provides a simpler public
  /// interface though.
  class SymbolicValue {
  private:
    enum RepresentationKind {
      /// This value is an alloc stack that has not (yet) been initialized
      /// by flow-sensitive analysis.
      RK_UninitMemory,
  
      /// This symbolic value cannot be determined, carries multiple values
      /// (i.e., varies dynamically at the top level), or is of some type that
      /// we cannot analyze and propagate (e.g. NSObject).
      ///
      RK_Unknown,
  
      /// This value is known to be a metatype reference.  The type is stored
      /// in the "metatype" member.
      RK_Metatype,
  
      /// This value is known to be a function reference, e.g. through
      /// function_ref directly, or a devirtualized method reference.
      RK_Function,
  
      /// This value is represented with a bump-pointer allocated APInt.
      RK_Integer,
  
      /// This value is represented with an inline integer representation.
      RK_IntegerInline,
  
      /// This value is represented with a bump-pointer allocated char array
      /// representing a UTF-8 encoded string.
      RK_String,
  
      /// This value is a struct or tuple of constants.  This is tracked by the
      /// "aggregate" member of the value union.
      RK_Aggregate,
  
      /// This value is an enum with no payload.
      RK_Enum,
  
      /// This value is an enum with a payload.
      RK_EnumWithPayload,
  
      /// This represents the address of a memory object.
      RK_DirectAddress,
  
      /// This represents an index *into* a memory object.
      RK_DerivedAddress,
  
      /// This represents the internal storage of an array.
      RK_ArrayStorage,
  
      /// This represents an array.
      RK_Array,
  
      /// This represents a closure.
      RK_Closure,
    };
  
    union {
      /// When the value is Unknown, this contains information about the
      /// unfoldable part of the computation.
      UnknownSymbolicValue *unknown;
  
      /// This is always a SILType with an object category.  This is the value
      /// of the underlying instance type, not the MetatypeType.
      TypeBase *metatype;
  
      SILFunction *function;
  
      /// When this SymbolicValue is of "Integer" kind, this pointer stores
      /// the words of the APInt value it holds.
      uint64_t *integer;
  
      /// This holds the bits of an integer for an inline representation.
      uint64_t integerInline;
  
      /// When this SymbolicValue is of "String" kind, this pointer stores
      /// information about the StringRef value it holds.
      const char *string;
  
      /// When this SymbolicValue is of "Aggregate" kind, this pointer stores
      /// information about the array elements and count.
      const SymbolicValue *aggregate;
  
      /// When this SymbolicValue is of "Enum" kind, this pointer stores
      /// information about the enum case type.
      EnumElementDecl *enumVal;
  
      /// When this SymbolicValue is of "EnumWithPayload" kind, this pointer
      /// stores information about the enum case type and its payload.
      EnumWithPayloadSymbolicValue *enumValWithPayload;
  
      /// When the representationKind is "DirectAddress", this pointer is the
      /// memory object referenced.
      SymbolicValueMemoryObject *directAddress;
  
      /// When this SymbolicValue is of "DerivedAddress" kind, this pointer stores
      /// information about the memory object and access path of the access.
      DerivedAddressValue *derivedAddress;
  
      // The following two fields are for representing an Array.
      //
      // In Swift, an array is a non-trivial struct that stores a reference to an
      // internal storage: _ContiguousArrayStorage. Though arrays have value
      // semantics in Swift, it is not the case in SIL. In SIL, an array can be
      // mutated by taking the address of the internal storage i.e., through a
      // shared, mutable pointer to the internal storage of the array. In fact,
      // this is how an array initialization is lowered in SIL. Therefore, the
      // symbolic representation of an array is an addressable "memory cell"
      // (i.e., a SymbolicValueMemoryObject) containing the array storage. The
      // array storage is modeled by the type: SymbolicArrayStorage. This
      // representation of the array enables obtaining the address of the internal
      // storage and modifying the array through that address. Array operations
      // such as `append` that mutate an array must clone the internal storage of
      // the array, following the semantics of the Swift implementation of those
      // operations.
  
      /// Representation of array storage (RK_ArrayStorage). SymbolicArrayStorage
      /// is a container for a sequence of symbolic values.
      SymbolicArrayStorage *arrayStorage;
  
      /// When this symbolic value is of an "Array" kind, this stores a memory
      /// object that contains a SymbolicArrayStorage value.
      SymbolicValueMemoryObject *array;
  
      /// When this symbolic value is of "Closure" kind, store a pointer to the
      /// symbolic representation of the closure.
      SymbolicClosure *closure;
    } value;
  
    RepresentationKind representationKind : 8;
  
    union {
      /// This is the number of bits in an RK_Integer or RK_IntegerInline
      /// representation, which makes the number of entries in the list derivable.
      unsigned integerBitwidth;
  
      /// This is the number of bytes for an RK_String representation.
      unsigned stringNumBytes;
  
      /// This is the number of elements for an RK_Aggregate representation.
      unsigned aggregateNumElements;
    } auxInfo;
  
  public:
    /// This enum is used to indicate the sort of value held by a SymbolicValue
    /// independent of its concrete representation.  This is the public
    /// interface to SymbolicValue.
    enum Kind {
      /// This is a value that isn't a constant.
      Unknown,
  
      /// This is a known metatype value.
      Metatype,
  
      /// This is a function, represented as a SILFunction.
      Function,
  
      /// This is an integer constant.
      Integer,
  
      /// String values may have SIL type of Builtin.RawPointer or Builtin.Word
      /// type.
      String,
  
      /// This can be an array, struct, tuple, etc.
      Aggregate,
  
      /// This is an enum without payload.
      Enum,
  
      /// This is an enum with payload (formally known as "associated value").
      EnumWithPayload,
  
      /// This value represents the address of, or into, a memory object.
      Address,
  
      /// This represents an internal array storage.
      ArrayStorage,
  
      /// This represents an array value.
      Array,
  
      /// This represents a closure.
      Closure,
  
      /// These values are generally only seen internally to the system, external
      /// clients shouldn't have to deal with them.
      UninitMemory
    };
  
    /// For constant values, return the type classification of this value.
    Kind getKind() const;
  
    /// Return true if this represents a constant value.
    bool isConstant() const {
      auto kind = getKind();
      return kind != Unknown && kind != UninitMemory;
    }
  
    static SymbolicValue getUnknown(SILNode *node, UnknownReason reason,
                                    llvm::ArrayRef<SourceLoc> callStack,
                                    SymbolicValueAllocator &allocator);
  
    /// Return true if this represents an unknown result.
    bool isUnknown() const { return getKind() == Unknown; }
  
    /// Return the call stack for an unknown result.
    ArrayRef<SourceLoc> getUnknownCallStack() const;
  
    /// Return the node that triggered an unknown result.
    SILNode *getUnknownNode() const;
  
    /// Return the reason an unknown result was generated.
    UnknownReason getUnknownReason() const;
  
    static SymbolicValue getUninitMemory() {
      SymbolicValue result;
      result.representationKind = RK_UninitMemory;
      return result;
    }
  
    static SymbolicValue getMetatype(CanType type) {
      SymbolicValue result;
      result.representationKind = RK_Metatype;
      result.value.metatype = type.getPointer();
      return result;
    }
  
    CanType getMetatypeValue() const {
      assert(representationKind == RK_Metatype);
      return CanType(value.metatype);
    }
  
    static SymbolicValue getFunction(SILFunction *fn) {
      assert(fn && "Function cannot be null");
      SymbolicValue result;
      result.representationKind = RK_Function;
      result.value.function = fn;
      return result;
    }
  
    SILFunction *getFunctionValue() const {
      assert(getKind() == Function);
      return value.function;
    }
  
    static SymbolicValue getInteger(int64_t value, unsigned bitWidth);
    static SymbolicValue getInteger(const APInt &value,
                                    SymbolicValueAllocator &allocator);
  
    APInt getIntegerValue() const;
    unsigned getIntegerValueBitWidth() const;
  
    /// Returns a SymbolicValue representing a UTF-8 encoded string.
    static SymbolicValue getString(StringRef string,
                                   SymbolicValueAllocator &allocator);
  
    /// Returns the UTF-8 encoded string underlying a SymbolicValue.
    StringRef getStringValue() const;
  
    /// This returns an aggregate value with the specified elements in it.  This
    /// copies the elements into the specified Allocator.
    static SymbolicValue getAggregate(ArrayRef<SymbolicValue> elements,
                                      SymbolicValueAllocator &allocator);
  
    ArrayRef<SymbolicValue> getAggregateValue() const;
  
    /// This returns a constant Symbolic value for the enum case in `decl`, which
    /// must not have an associated value.
    static SymbolicValue getEnum(EnumElementDecl *decl) {
      assert(decl);
      SymbolicValue result;
      result.representationKind = RK_Enum;
      result.value.enumVal = decl;
      return result;
    }
  
    /// `payload` must be a constant.
    static SymbolicValue getEnumWithPayload(EnumElementDecl *decl,
                                            SymbolicValue payload,
                                            SymbolicValueAllocator &allocator);
  
    EnumElementDecl *getEnumValue() const;
  
    SymbolicValue getEnumPayloadValue() const;
  
    /// Return a symbolic value that represents the address of a memory object.
    static SymbolicValue getAddress(SymbolicValueMemoryObject *memoryObject) {
      SymbolicValue result;
      result.representationKind = RK_DirectAddress;
      result.value.directAddress = memoryObject;
      return result;
    }
  
    /// Return a symbolic value that represents the address of a memory object
    /// indexed by a path.
    static SymbolicValue getAddress(SymbolicValueMemoryObject *memoryObject,
                                    ArrayRef<unsigned> indices,
                                    SymbolicValueAllocator &allocator);
  
    /// Return the memory object of this reference along with any access path
    /// indices involved.
    SymbolicValueMemoryObject *
    getAddressValue(SmallVectorImpl<unsigned> &accessPath) const;
  
    /// Return just the memory object for an address value.
    SymbolicValueMemoryObject *getAddressValueMemoryObject() const;
  
    /// Create a symbolic array storage containing \c elements.
    static SymbolicValue
    getSymbolicArrayStorage(ArrayRef<SymbolicValue> elements, CanType elementType,
                            SymbolicValueAllocator &allocator);
  
    /// Create a symbolic array using the given symbolic array storage, which
    /// contains the array elements.
    static SymbolicValue getArray(Type arrayType, SymbolicValue arrayStorage,
                                  SymbolicValueAllocator &allocator);
  
    /// Return the elements stored in this SymbolicValue of "ArrayStorage" kind.
    ArrayRef<SymbolicValue> getStoredElements(CanType &elementType) const;
  
    /// Return the symbolic value representing the internal storage of this array.
    SymbolicValue getStorageOfArray() const;
  
    /// Return the symbolic value representing the address of the element of this
    /// array at the given \c index. The return value is a derived address whose
    /// base is the memory object \c value.array (which contains the array
    /// storage) and whose accesspath is \c index.
    SymbolicValue getAddressOfArrayElement(SymbolicValueAllocator &allocator,
                                           unsigned index) const;
  
    /// Return the type of this array symbolic value.
    Type getArrayType() const;
  
    /// Create and return a symbolic value that represents a closure.
    /// \param target SILFunction corresponding the target of the closure.
    /// \param capturedArguments an array consisting of SILValues of captured
    /// arguments along with their symbolic values when available.
    /// \param allocator the allocator to use for storing the contents of this
    /// symbolic value.
    static SymbolicValue makeClosure(
        SILFunction *target,
        ArrayRef<std::pair<SILValue, Optional<SymbolicValue>>> capturedArguments,
        SymbolicValueAllocator &allocator);
  
    SymbolicClosure *getClosure() const {
      assert(getKind() == Closure);
      return value.closure;
    }
  
    //===--------------------------------------------------------------------===//
    // Helpers
  
    /// Dig through single element aggregates, return the ultimate thing inside of
    /// it.  This is useful when dealing with integers and floats, because they
    /// are often wrapped in single-element struct wrappers.
    SymbolicValue lookThroughSingleElementAggregates() const;
  
    /// Given that this is an 'Unknown' value, emit diagnostic notes providing
    /// context about what the problem is.  If there is no location for some
    /// reason, we fall back to using the specified location.
    void emitUnknownDiagnosticNotes(SILLocation fallbackLoc);
  
    bool isUnknownDueToUnevaluatedInstructions();
  
    /// Clone this SymbolicValue into the specified Allocator and return the new
    /// version. This only works for valid constants.
    SymbolicValue cloneInto(SymbolicValueAllocator &allocator) const;
  
    void print(llvm::raw_ostream &os, unsigned indent = 0) const;
    void dump() const;
  };
  
  static_assert(sizeof(SymbolicValue) == 2 * sizeof(uint64_t),
                "SymbolicValue should stay small");
  static_assert(std::is_pod<SymbolicValue>::value,
                "SymbolicValue should stay POD");
  
  inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os, SymbolicValue val) {
    val.print(os);
    return os;
  }
  
  /// This is a representation of a memory object referred to by an address.
  /// Memory objects may be mutated over their lifetime, but their overall type
  /// remains the same.
  struct SymbolicValueMemoryObject {
    Type getType() const { return type; }
  
    SymbolicValue getValue() const { return value; }
    void setValue(SymbolicValue newValue) { value = newValue; }
  
    /// Create a new memory object whose overall type is as specified.
    static SymbolicValueMemoryObject *create(Type type, SymbolicValue value,
                                             SymbolicValueAllocator &allocator);
  
    /// Given that this memory object contains an aggregate value like
    /// {{1, 2}, 3}, and given an access path like [0,1], return the indexed
    /// element, e.g. "2" in this case.
    ///
    /// Returns uninit memory if the access path points at or into uninit memory.
    ///
    /// Precondition: The access path must be valid for this memory object's type.
    SymbolicValue getIndexedElement(ArrayRef<unsigned> accessPath);
  
    /// Given that this memory object contains an aggregate value like
    /// {{1, 2}, 3}, given an access path like [0,1], and given a new element like
    /// "4", set the indexed element to the specified scalar, producing {{1, 4},
    /// 3} in this case.
    ///
    /// Precondition: The access path must be valid for this memory object's type.
    void setIndexedElement(ArrayRef<unsigned> accessPath,
                           SymbolicValue newElement,
                           SymbolicValueAllocator &allocator);
  
  private:
    const Type type;
    SymbolicValue value;
  
    SymbolicValueMemoryObject(Type type, SymbolicValue value)
        : type(type), value(value) {}
    SymbolicValueMemoryObject(const SymbolicValueMemoryObject &) = delete;
    void operator=(const SymbolicValueMemoryObject &) = delete;
  };
  
  using SymbolicClosureArgument = std::pair<SILValue, Optional<SymbolicValue>>;
  
  /// Representation of a symbolic closure. A symbolic closure consists of a
  /// SILFunction and an array of SIL values, corresponding to the captured
  /// arguments, and (optional) symbolic values representing the constant values
  /// of the captured arguments. The symbolic values are optional as it is not
  /// necessary for every captured argument to be a constant, which enables
  /// representing closures whose captured arguments are not compile-time
  /// constants.
  struct SymbolicClosure final
    : private llvm::TrailingObjects<SymbolicClosure, SymbolicClosureArgument> {
  
    friend class llvm::TrailingObjects<SymbolicClosure, SymbolicClosureArgument>;
  
  private:
  
    SILFunction *target;
  
    // The number of SIL values captured by the closure.
    unsigned numCaptures;
  
    // True iff there exists captured arguments whose constant value is not known.
    bool hasNonConstantCaptures = true;
  
    SymbolicClosure() = delete;
    SymbolicClosure(const SymbolicClosure &) = delete;
    SymbolicClosure(SILFunction *callee, unsigned numArguments,
                    bool nonConstantCaptures)
        : target(callee), numCaptures(numArguments),
          hasNonConstantCaptures(nonConstantCaptures) {}
  
  public:
    static SymbolicClosure *create(SILFunction *callee,
                                   ArrayRef<SymbolicClosureArgument> args,
                                   SymbolicValueAllocator &allocator);
  
    ArrayRef<SymbolicClosureArgument> getCaptures() const {
      return {getTrailingObjects<SymbolicClosureArgument>(), numCaptures};
    }
  
    // This is used by the llvm::TrailingObjects base class.
    size_t numTrailingObjects(OverloadToken<SymbolicClosureArgument>) const {
      return numCaptures;
    }
  
    SILFunction *getTarget() {
      return target;
    }
  };
  
  } // end namespace swift
  
  #endif
  