text: /*
   * Licensed to the Apache Software Foundation (ASF) under one
   * or more contributor license agreements.  See the NOTICE file
   * distributed with this work for additional information
   * regarding copyright ownership.  The ASF licenses this file
   * to you under the Apache License, Version 2.0 (the
   * "License"); you may not use this file except in compliance
   * with the License.  You may obtain a copy of the License at
   *
   *   http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing,
   * software distributed under the License is distributed on an
   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
   * KIND, either express or implied.  See the License for the
   * specific language governing permissions and limitations
   * under the License.
   */
  
  /*!
   * \file tvm/runtime/container.h
   * \brief Common POD(plain old data) container types.
   */
  #ifndef TVM_RUNTIME_CONTAINER_H_
  #define TVM_RUNTIME_CONTAINER_H_
  
  #include <dmlc/logging.h>
  #include <tvm/runtime/memory.h>
  #include <tvm/runtime/object.h>
  #include <tvm/runtime/packed_func.h>
  
  #include <cstring>
  #include <initializer_list>
  #include <string>
  // We use c++14 std::experimental::string_view for optimizing hash computation
  // only right now, its usage is limited in this file. Any broader usage of
  // std::experiment in our core codebase is discouraged and needs community
  // discussion for each use case. Reference for feature test macros of
  // string_view:
  // https://isocpp.org/std/standing-documents/sd-6-sg10-feature-test-recommendations
  // https://en.cppreference.com/w/User:D41D8CD98F/feature_testing_macros
  #if defined(__cpp_lib_experimental_string_view) && \
      __cpp_lib_experimental_string_view >= 201411
  #define TVM_USE_CXX14_STRING_VIEW_HASH 1
  #else
  #define TVM_USE_CXX14_STRING_VIEW_HASH 0
  #endif
  
  // Tested with clang version 9.0.1 and c++17. It will detect string_view support
  // correctly.
  #if defined(__cpp_lib_string_view) && __cpp_lib_string_view >= 201606
  #define TVM_USE_CXX17_STRING_VIEW_HASH 1
  #else
  #define TVM_USE_CXX17_STRING_VIEW_HASH 0
  #endif
  
  #if TVM_USE_CXX17_STRING_VIEW_HASH
  #include <string_view>
  #elif TVM_USE_CXX14_STRING_VIEW_HASH
  #include <experimental/string_view>
  #endif
  
  #include <type_traits>
  #include <utility>
  #include <vector>
  
  namespace tvm {
  namespace runtime {
  
  /*!
   * \brief Base template for classes with array like memory layout.
   *
   *        It provides general methods to access the memory. The memory
   *        layout is ArrayType + [ElemType]. The alignment of ArrayType
   *        and ElemType is handled by the memory allocator.
   *
   * \tparam ArrayType The array header type, contains object specific metadata.
   * \tparam ElemType The type of objects stored in the array right after
   * ArrayType.
   *
   * \code
   * // Example usage of the template to define a simple array wrapper
   * class ArrayObj : public InplaceArrayBase<ArrayObj, Elem> {
   * public:
   *  // Wrap EmplaceInit to initialize the elements
   *  template <typename Iterator>
   *  void Init(Iterator begin, Iterator end) {
   *   size_t num_elems = std::distance(begin, end);
   *   auto it = begin;
   *   this->size = 0;
   *   for (size_t i = 0; i < num_elems; ++i) {
   *     InplaceArrayBase::EmplaceInit(i, *it++);
   *     this->size++;
   *   }
   *  }
   * }
   *
   * void test_function() {
   *   vector<Elem> fields;
   *   auto ptr = make_inplace_array_object<ArrayObj, Elem>(fields.size());
   *   ptr->Init(fields.begin(), fields.end());
   *
   *   // Access the 0th element in the array.
   *   assert(ptr->operator[](0) == fields[0]);
   * }
   *
   * \endcode
   */
  template <typename ArrayType, typename ElemType>
  class InplaceArrayBase {
   public:
    /*!
     * \brief Access element at index
     * \param idx The index of the element.
     * \return Const reference to ElemType at the index.
     */
    const ElemType& operator[](size_t idx) const {
      size_t size = Self()->GetSize();
      CHECK_LT(idx, size) << "Index " << idx << " out of bounds " << size << "\n";
      return *(reinterpret_cast<ElemType*>(AddressOf(idx)));
    }
  
    /*!
     * \brief Access element at index
     * \param idx The index of the element.
     * \return Reference to ElemType at the index.
     */
    ElemType& operator[](size_t idx) {
      size_t size = Self()->GetSize();
      CHECK_LT(idx, size) << "Index " << idx << " out of bounds " << size << "\n";
      return *(reinterpret_cast<ElemType*>(AddressOf(idx)));
    }
  
    /*!
     * \brief Destroy the Inplace Array Base object
     */
    ~InplaceArrayBase() {
      if (!(std::is_standard_layout<ElemType>::value &&
            std::is_trivial<ElemType>::value)) {
        size_t size = Self()->GetSize();
        for (size_t i = 0; i < size; ++i) {
          ElemType* fp = reinterpret_cast<ElemType*>(AddressOf(i));
          fp->ElemType::~ElemType();
        }
      }
    }
  
   protected:
    /*!
     * \brief Construct a value in place with the arguments.
     *
     * \tparam Args Type parameters of the arguments.
     * \param idx Index of the element.
     * \param args Arguments to construct the new value.
     *
     * \note Please make sure ArrayType::GetSize returns 0 before first call of
     * EmplaceInit, and increment GetSize by 1 each time EmplaceInit succeeds.
     */
    template <typename... Args>
    void EmplaceInit(size_t idx, Args&&... args) {
      void* field_ptr = AddressOf(idx);
      new (field_ptr) ElemType(std::forward<Args>(args)...);
    }
  
   private:
    /*!
     * \brief Return the self object for the array.
     *
     * \return Pointer to ArrayType.
     */
    inline ArrayType* Self() const {
      return static_cast<ArrayType*>(const_cast<InplaceArrayBase*>(this));
    }
  
    /*!
     * \brief Return the raw pointer to the element at idx.
     *
     * \param idx The index of the element.
     * \return Raw pointer to the element.
     */
    void* AddressOf(size_t idx) const {
      static_assert(alignof(ArrayType) % alignof(ElemType) == 0 &&
                        sizeof(ArrayType) % alignof(ElemType) == 0,
                    "The size and alignment of ArrayType should respect "
                    "ElemType's alignment.");
  
      size_t kDataStart = sizeof(ArrayType);
      ArrayType* self = Self();
      char* data_start = reinterpret_cast<char*>(self) + kDataStart;
      return data_start + idx * sizeof(ElemType);
    }
  };
  
  /*! \brief An object representing a structure or enumeration. */
  class ADTObj : public Object, public InplaceArrayBase<ADTObj, ObjectRef> {
   public:
    /*! \brief The tag representing the constructor used. */
    int32_t tag;
    /*! \brief Number of fields in the ADT object. */
    uint32_t size;
    // The fields of the structure follows directly in memory.
  
    static constexpr const uint32_t _type_index = TypeIndex::kRuntimeADT;
    static constexpr const char* _type_key = "runtime.ADT";
    TVM_DECLARE_FINAL_OBJECT_INFO(ADTObj, Object);
  
   private:
    /*!
     * \return The number of elements in the array.
     */
    size_t GetSize() const { return size; }
  
    /*!
     * \brief Initialize the elements in the array.
     *
     * \tparam Iterator Iterator type of the array.
     * \param begin The begin iterator.
     * \param end The end iterator.
     */
    template <typename Iterator>
    void Init(Iterator begin, Iterator end) {
      size_t num_elems = std::distance(begin, end);
      this->size = 0;
      auto it = begin;
      for (size_t i = 0; i < num_elems; ++i) {
        InplaceArrayBase::EmplaceInit(i, *it++);
        // Only increment size after the initialization succeeds
        this->size++;
      }
    }
  
    friend class ADT;
    friend InplaceArrayBase<ADTObj, ObjectRef>;
  };
  
  /*! \brief reference to algebraic data type objects. */
  class ADT : public ObjectRef {
   public:
    /*!
     * \brief construct an ADT object reference.
     * \param tag The tag of the ADT object.
     * \param fields The fields of the ADT object.
     * \return The constructed ADT object reference.
     */
    ADT(int32_t tag, std::vector<ObjectRef> fields)
        : ADT(tag, fields.begin(), fields.end()){};
  
    /*!
     * \brief construct an ADT object reference.
     * \param tag The tag of the ADT object.
     * \param begin The begin iterator to the start of the fields array.
     * \param end The end iterator to the end of the fields array.
     * \return The constructed ADT object reference.
     */
    template <typename Iterator>
    ADT(int32_t tag, Iterator begin, Iterator end) {
      size_t num_elems = std::distance(begin, end);
      auto ptr = make_inplace_array_object<ADTObj, ObjectRef>(num_elems);
      ptr->tag = tag;
      ptr->Init(begin, end);
      data_ = std::move(ptr);
    }
  
    /*!
     * \brief construct an ADT object reference.
     * \param tag The tag of the ADT object.
     * \param init The initializer list of fields.
     * \return The constructed ADT object reference.
     */
    ADT(int32_t tag, std::initializer_list<ObjectRef> init)
        : ADT(tag, init.begin(), init.end()){};
  
    /*!
     * \brief Access element at index.
     *
     * \param idx The array index
     * \return const ObjectRef
     */
    const ObjectRef& operator[](size_t idx) const {
      return operator->()->operator[](idx);
    }
  
    /*!
     * \brief Return the ADT tag.
     */
    int32_t tag() const { return operator->()->tag; }
  
    /*!
     * \brief Return the number of fields.
     */
    size_t size() const { return operator->()->size; }
  
    /*!
     * \brief Construct a tuple object.
     *
     * \tparam Args Type params of tuple feilds.
     * \param args Tuple fields.
     * \return ADT The tuple object reference.
     */
    template <typename... Args>
    static ADT Tuple(Args&&... args) {
      return ADT(0, std::forward<Args>(args)...);
    }
  
    TVM_DEFINE_OBJECT_REF_METHODS(ADT, ObjectRef, ADTObj);
  };
  
  /*! \brief An object representing string. It's POD type. */
  class StringObj : public Object {
   public:
    /*! \brief The pointer to string data. */
    const char* data;
  
    /*! \brief The length of the string object. */
    uint64_t size;
  
    static constexpr const uint32_t _type_index = TypeIndex::kRuntimeString;
    static constexpr const char* _type_key = "runtime.String";
    TVM_DECLARE_FINAL_OBJECT_INFO(StringObj, Object);
  
   private:
    /*! \brief String object which is moved from std::string container. */
    class FromStd;
  
    friend class String;
  };
  
  /*!
   * \brief Reference to string objects.
   *
   * \code
   *
   * // Example to create runtime String reference object from std::string
   * std::string s = "hello world";
   *
   * // You can create the reference from existing std::string
   * String ref{std::move(s)};
   *
   * // You can rebind the reference to another string.
   * ref = std::string{"hello world2"};
   *
   * // You can use the reference as hash map key
   * std::unordered_map<String, int32_t> m;
   * m[ref] = 1;
   *
   * // You can compare the reference object with other string objects
   * assert(ref == "hello world", true);
   *
   * // You can convert the reference to std::string again
   * string s2 = (string)ref;
   *
   * \endcode
   */
  class String : public ObjectRef {
   public:
    /*!
     * \brief Construct an empty string.
     */
    String() : String(std::string()) {}
    /*!
     * \brief Construct a new String object
     *
     * \param other The moved/copied std::string object
     *
     * \note If user passes const reference, it will trigger copy. If it's rvalue,
     * it will be moved into other.
     */
    String(std::string other);  // NOLINT(*)
  
    /*!
     * \brief Construct a new String object
     *
     * \param other a char array.
     */
    String(const char* other)  // NOLINT(*)
        : String(std::string(other)) {}
  
    /*!
     * \brief Change the value the reference object points to.
     *
     * \param other The value for the new String
     *
     */
    inline String operator=(std::string other);
  
    /*!
     * \brief Compare is equal to other std::string
     *
     * \param other The other string
     *
     * \return the comparison result
     */
    bool operator==(const std::string& other) const {
      return this->compare(other) == 0;
    }
  
    /*!
     * \brief Compare is not equal to other std::string
     *
     * \param other The other string
     *
     * \return the comparison result
     */
    bool operator!=(const std::string& other) const { return !operator==(other); }
  
    /*!
     * \brief Compare is equal to other char string
     *
     * \param other The other char string
     *
     * \return the comparison result
     */
    bool operator==(const char* other) const { return compare(other) == 0; }
  
    /*!
     * \brief Compare is not equal to other char string
     *
     * \param other The other char string
     *
     * \return the comparison result
     */
    bool operator!=(const char* other) const { return !operator==(other); }
  
    /*!
     * \brief Compares this String object to other
     *
     * \param other The String to compare with.
     *
     * \return zero if both char sequences compare equal. negative if this appear
     * before other, positive otherwise.
     */
    int compare(const String& other) const {
      return memncmp(data(), other.data(), size(), other.size());
    }
  
    /*!
     * \brief Compares this String object to other
     *
     * \param other The string to compare with.
     *
     * \return zero if both char sequences compare equal. negative if this appear
     * before other, positive otherwise.
     */
    int compare(const std::string& other) const {
      return memncmp(data(), other.data(), size(), other.size());
    }
  
    /*!
     * \brief Compares this to other
     *
     * \param other The character array to compare with.
     *
     * \return zero if both char sequences compare equal. negative if this appear
     * before other, positive otherwise.
     */
    int compare(const char* other) const {
      return memncmp(data(), other, size(), std::strlen(other));
    }
  
    /*!
     * \brief Returns a pointer to the char array in the string.
     *
     * \return const char*
     */
    const char* c_str() const { return get()->data; }
  
    /*!
     * \brief Return the length of the string
     *
     * \return size_t string length
     */
    size_t size() const {
      const auto* ptr = get();
      return ptr->size;
    }
  
    /*!
     * \brief Return the length of the string
     *
     * \return size_t string length
     */
    size_t length() const { return size(); }
  
    /*!
     * \brief Retun if the string is empty
     *
     * \return true if empty, false otherwise.
     */
    bool empty() const { return size() == 0; }
  
    /*!
     * \brief Return the data pointer
     *
     * \return const char* data pointer
     */
    const char* data() const { return get()->data; }
  
    /*!
     * \brief Convert String to an std::sting object
     *
     * \return std::string
     */
    operator std::string() const { return std::string{get()->data, size()}; }
  
    /*!
     * \brief Hash the binary bytes
     * \param data The data pointer
     * \param size The size of the bytes.
     * \return the hash value.
     */
    static size_t HashBytes(const char* data, size_t size) {
      // This function falls back to string copy with c++11 compiler and is
      // recommended to be compiled with c++14
  #if TVM_USE_CXX17_STRING_VIEW_HASH
      return std::hash<std::string_view>()(
          std::string_view(data, size));
  #elif TVM_USE_CXX14_STRING_VIEW_HASH
      return std::hash<std::experimental::string_view>()(
          std::experimental::string_view(data, size));
  #else
      return std::hash<std::string>()(std::string(data, size));
  #endif
    }
  
    /*! \return the internal StringObj pointer */
    const StringObj* get() const { return operator->(); }
  
    TVM_DEFINE_NOTNULLABLE_OBJECT_REF_METHODS(String, ObjectRef, StringObj);
  
   private:
    /*!
     * \brief Compare two char sequence
     *
     * \param lhs Pointers to the char array to compare
     * \param rhs Pointers to the char array to compare
     * \param lhs_count Length of the char array to compare
     * \param rhs_count Length of the char array to compare
     * \return int zero if both char sequences compare equal. negative if this
     * appear before other, positive otherwise.
     */
    static int memncmp(const char* lhs, const char* rhs, size_t lhs_count,
                       size_t rhs_count);
  };
  
  /*! \brief An object representing string moved from std::string. */
  class StringObj::FromStd : public StringObj {
   public:
    /*!
     * \brief Construct a new FromStd object
     *
     * \param other The moved/copied std::string object
     *
     * \note If user passes const reference, it will trigger copy. If it's rvalue,
     * it will be moved into other.
     */
    explicit FromStd(std::string other) : data_container{other} {}
  
   private:
    /*! \brief Container that holds the memory. */
    std::string data_container;
  
    friend class String;
  };
  
  inline String::String(std::string other) {
    auto ptr = make_object<StringObj::FromStd>(std::move(other));
    ptr->size = ptr->data_container.size();
    ptr->data = ptr->data_container.data();
    data_ = std::move(ptr);
  }
  
  inline String String::operator=(std::string other) {
    String replace{std::move(other)};
    data_.swap(replace.data_);
    return Downcast<String>(*this);
  }
  
  inline int String::memncmp(const char* lhs, const char* rhs, size_t lhs_count,
                             size_t rhs_count) {
    if (lhs == rhs && lhs_count == rhs_count) return 0;
  
    for (size_t i = 0; i < lhs_count && i < rhs_count; ++i) {
      if (lhs[i] < rhs[i]) return -1;
      if (lhs[i] > rhs[i]) return 1;
    }
    if (lhs_count < rhs_count) {
      return -1;
    } else if (lhs_count > rhs_count) {
      return 1;
    } else {
      return 0;
    }
  }
  
  template<>
  struct PackedFuncValueConverter<::tvm::runtime::String> {
    static String From(const TVMArgValue& val) {
      if (val.IsObjectRef<tvm::runtime::String>()) {
        return val.AsObjectRef<tvm::runtime::String>();
      } else {
        return tvm::runtime::String(val.operator std::string());
      }
    }
  
    static String From(const TVMRetValue& val) {
      if (val.IsObjectRef<tvm::runtime::String>()) {
        return val.AsObjectRef<tvm::runtime::String>();
      } else {
        return tvm::runtime::String(val.operator std::string());
      }
    }
  };
  
  /*! \brief Helper to represent nullptr for optional. */
  struct NullOptType {
  };
  
  /*!
   * \brief Optional container that to represent to a Nullable variant of T.
   * \tparam T The original ObjectRef.
   *
   * \code
   *
   *  Optional<String> opt0 = nullptr;
   *  Optional<String> opt1 = String("xyz");
   *  CHECK(opt0 == nullptr);
   *  CHECK(opt1 == "xyz");
   *
   * \endcode
   */
  template<typename T>
  class Optional : public ObjectRef {
   public:
    using ContainerType = typename T::ContainerType;
    static_assert(std::is_base_of<ObjectRef, T>::value,
                  "Optional is only defined for ObjectRef.");
    // default constructors.
    Optional() = default;
    Optional(const Optional<T>&) = default;
    Optional(Optional<T>&&) = default;
    Optional<T>& operator=(const Optional<T>&) = default;
    Optional<T>& operator=(Optional<T>&&) = default;
    /*!
     * \brief Construct from an ObjectPtr
     *        whose type already matches the ContainerType.
     * \param ptr
     */
    explicit Optional(ObjectPtr<Object> ptr) : ObjectRef(ptr) {}
    /*! \brief Nullopt handling */
    Optional(NullOptType) {}  // NOLINT(*)
    // nullptr handling.
    // disallow implicit conversion as 0 can be implicitly converted to nullptr_t
    explicit Optional(std::nullptr_t) {}
    Optional<T>& operator=(std::nullptr_t) {
      data_ = nullptr;
      return *this;
    }
    // normal value handling.
    Optional(T other)             // NOLINT(*)
        : ObjectRef(std::move(other)) {
    }
    Optional<T>& operator=(T other) {
      ObjectRef::operator=(std::move(other));
      return *this;
    }
    // delete the int constructor
    // since Optional<Integer>(0) is ambiguious
    // 0 can be implicitly casted to nullptr_t
    explicit Optional(int val) = delete;
    Optional<T>& operator=(int val) = delete;
    /*!
     * \return A not-null container value in the optional.
     * \note This function performs not-null checking.
     */
    T value() const {
      CHECK(data_ != nullptr);
      return T(data_);
    }
    /*!
     * \return The contained value if the Optional is not null
     *         otherwise return the default_value.
     */
    T value_or(T default_value) const {
      return data_ != nullptr ? T(data_) : default_value;
    }
    /*! \return Whether the container is not nullptr.*/
    explicit operator bool() const {
      return *this != nullptr;
    }
    // operator overloadings
    bool operator==(std::nullptr_t) const {
      return data_ == nullptr;
    }
    bool operator!=(std::nullptr_t) const {
      return data_ != nullptr;
    }
    auto operator==(const Optional<T>& other) const {
      // support case where sub-class returns a symbolic ref type.
      using RetType = decltype(value() == other.value());
      if (same_as(other)) return RetType(true);
      if (*this != nullptr && other != nullptr) {
        return value() == other.value();
      } else {
        // one of them is nullptr.
        return RetType(false);
      }
    }
    auto operator!=(const Optional<T>& other) const {
      // support case where sub-class returns a symbolic ref type.
      using RetType = decltype(value() != other.value());
      if (same_as(other)) return RetType(false);
      if (*this != nullptr && other != nullptr) {
        return value() != other.value();
      } else {
        // one of them is nullptr.
        return RetType(true);
      }
    }
    auto operator==(const T& other) const {
      using RetType = decltype(value() == other);
      if (same_as(other)) return RetType(true);
      if (*this != nullptr) return value() == other;
      return RetType(false);
    }
    auto operator!=(const T& other) const {
      return !(*this == other);
    }
    template<typename U>
    auto operator==(const U& other) const {
      using RetType = decltype(value() == other);
      if (*this == nullptr) return RetType(false);
      return value() == other;
    }
    template<typename U>
    auto operator!=(const U& other) const {
      using RetType = decltype(value() != other);
      if (*this == nullptr) return RetType(true);
      return value() != other;
    }
    static constexpr bool _type_is_nullable = true;
  };
  
  template<typename T>
  struct PackedFuncValueConverter<Optional<T>> {
    static Optional<T> From(const TVMArgValue& val) {
      if (val.type_code() == kTVMNullptr) return Optional<T>(nullptr);
      return PackedFuncValueConverter<T>::From(val);
    }
    static Optional<T> From(const TVMRetValue& val) {
      if (val.type_code() == kTVMNullptr) return Optional<T>(nullptr);
      return PackedFuncValueConverter<T>::From(val);
    }
  };
  
  }  // namespace runtime
  
  // expose the functions to the root namespace.
  using runtime::String;
  using runtime::Optional;
  constexpr runtime::NullOptType NullOpt{};
  }  // namespace tvm
  
  namespace std {
  
  template <>
  struct hash<::tvm::runtime::String> {
    std::size_t operator()(const ::tvm::runtime::String& str) const {
      return ::tvm::runtime::String::HashBytes(str.data(), str.size());
    }
  };
  }  // namespace std
  
  #endif  // TVM_RUNTIME_CONTAINER_H_
  