// Copyright 2020 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/wasm/wasm-subtyping.h"

#include "src/base/platform/mutex.h"
#include "src/wasm/wasm-module.h"
#include "src/zone/zone-containers.h"

namespace v8 {
namespace internal {
namespace wasm {

namespace {

using CacheKey =
    std::tuple<uint32_t, uint32_t, const WasmModule*, const WasmModule*>;

struct CacheKeyHasher {
  size_t operator()(CacheKey key) const {
    static constexpr size_t large_prime = 14887;
    return std::get<0>(key) + (std::get<1>(key) * large_prime) +
           (reinterpret_cast<size_t>(std::get<2>(key)) * large_prime *
            large_prime) +
           (reinterpret_cast<size_t>(std::get<3>(key)) * large_prime *
            large_prime * large_prime);
  }
};

class TypeJudgementCache {
 public:
  TypeJudgementCache()
      : zone_(new AccountingAllocator(), "type judgement zone"),
        subtyping_cache_(&zone_),
        type_equivalence_cache_(&zone_) {}

  static TypeJudgementCache* instance() {
    static base::LazyInstance<TypeJudgementCache>::type instance_ =
        LAZY_INSTANCE_INITIALIZER;
    return instance_.Pointer();
  }

  base::RecursiveMutex* type_cache_mutex() { return &type_cache_mutex_; }
  bool is_cached_subtype(uint32_t subtype, uint32_t supertype,
                         const WasmModule* sub_module,
                         const WasmModule* super_module) const {
    return subtyping_cache_.count(std::make_tuple(
               subtype, supertype, sub_module, super_module)) == 1;
  }
  void cache_subtype(uint32_t subtype, uint32_t supertype,
                     const WasmModule* sub_module,
                     const WasmModule* super_module) {
    subtyping_cache_.emplace(subtype, supertype, sub_module, super_module);
  }
  void uncache_subtype(uint32_t subtype, uint32_t supertype,
                       const WasmModule* sub_module,
                       const WasmModule* super_module) {
    subtyping_cache_.erase(
        std::make_tuple(subtype, supertype, sub_module, super_module));
  }
  bool is_cached_equivalent_type(uint32_t type1, uint32_t type2,
                                 const WasmModule* module1,
                                 const WasmModule* module2) const {
    if (type1 > type2) std::swap(type1, type2);
    if (reinterpret_cast<uintptr_t>(module1) >
        reinterpret_cast<uintptr_t>(module2)) {
      std::swap(module1, module2);
    }
    return type_equivalence_cache_.count(
               std::make_tuple(type1, type2, module1, module2)) == 1;
  }
  void cache_type_equivalence(uint32_t type1, uint32_t type2,
                              const WasmModule* module1,
                              const WasmModule* module2) {
    if (type1 > type2) std::swap(type1, type2);
    if (reinterpret_cast<uintptr_t>(module1) >
        reinterpret_cast<uintptr_t>(module2)) {
      std::swap(module1, module2);
    }
    type_equivalence_cache_.emplace(type1, type2, module1, module2);
  }
  void uncache_type_equivalence(uint32_t type1, uint32_t type2,
                                const WasmModule* module1,
                                const WasmModule* module2) {
    if (type1 > type2) std::swap(type1, type2);
    if (reinterpret_cast<uintptr_t>(module1) >
        reinterpret_cast<uintptr_t>(module2)) {
      std::swap(module1, module2);
    }
    type_equivalence_cache_.erase(
        std::make_tuple(type1, type2, module1, module2));
  }

 private:
  Zone zone_;
  ZoneUnorderedSet<CacheKey, CacheKeyHasher>
      // Cache for discovered subtyping pairs.
      subtyping_cache_,
      // Cache for discovered equivalent type pairs.
      // Indexes and modules are stored in increasing order.
      type_equivalence_cache_;
  // The above two caches are used from background compile jobs, so they
  // must be protected from concurrent modifications:
  base::RecursiveMutex type_cache_mutex_;
};

bool ArrayEquivalentIndices(uint32_t type_index_1, uint32_t type_index_2,
                            const WasmModule* module1,
                            const WasmModule* module2) {
  const ArrayType* sub_array = module1->types[type_index_1].array_type;
  const ArrayType* super_array = module2->types[type_index_2].array_type;
  if (sub_array->mutability() != super_array->mutability()) return false;

  // Temporarily cache type equivalence for the recursive call.
  TypeJudgementCache::instance()->cache_type_equivalence(
      type_index_1, type_index_2, module1, module2);
  if (EquivalentTypes(sub_array->element_type(), super_array->element_type(),
                      module1, module2)) {
    return true;
  } else {
    TypeJudgementCache::instance()->uncache_type_equivalence(
        type_index_1, type_index_2, module1, module2);
    // TODO(7748): Consider caching negative results as well.
    return false;
  }
}

bool StructEquivalentIndices(uint32_t type_index_1, uint32_t type_index_2,
                             const WasmModule* module1,
                             const WasmModule* module2) {
  const StructType* sub_struct = module1->types[type_index_1].struct_type;
  const StructType* super_struct = module2->types[type_index_2].struct_type;

  if (sub_struct->field_count() != super_struct->field_count()) {
    return false;
  }

  // Temporarily cache type equivalence for the recursive call.
  TypeJudgementCache::instance()->cache_type_equivalence(
      type_index_1, type_index_2, module1, module2);
  for (uint32_t i = 0; i < sub_struct->field_count(); i++) {
    if (sub_struct->mutability(i) != super_struct->mutability(i) ||
        !EquivalentTypes(sub_struct->field(i), super_struct->field(i), module1,
                         module2)) {
      TypeJudgementCache::instance()->uncache_type_equivalence(
          type_index_1, type_index_2, module1, module2);
      return false;
    }
  }
  return true;
}

bool FunctionEquivalentIndices(uint32_t type_index_1, uint32_t type_index_2,
                               const WasmModule* module1,
                               const WasmModule* module2) {
  const FunctionSig* sig1 = module1->types[type_index_1].function_sig;
  const FunctionSig* sig2 = module2->types[type_index_2].function_sig;

  if (sig1->parameter_count() != sig2->parameter_count() ||
      sig1->return_count() != sig2->return_count()) {
    return false;
  }

  auto iter1 = sig1->all();
  auto iter2 = sig2->all();

  // Temporarily cache type equivalence for the recursive call.
  TypeJudgementCache::instance()->cache_type_equivalence(
      type_index_1, type_index_2, module1, module2);
  for (int i = 0; i < iter1.size(); i++) {
    if (!EquivalentTypes(iter1[i], iter2[i], module1, module2)) {
      TypeJudgementCache::instance()->uncache_type_equivalence(
          type_index_1, type_index_2, module1, module2);
      return false;
    }
  }
  return true;
}

V8_INLINE bool EquivalentIndices(uint32_t index1, uint32_t index2,
                                 const WasmModule* module1,
                                 const WasmModule* module2) {
  DCHECK(index1 != index2 || module1 != module2);
  uint8_t kind1 = module1->type_kinds[index1];

  if (kind1 != module2->type_kinds[index2]) return false;

  base::RecursiveMutexGuard type_cache_access(
      TypeJudgementCache::instance()->type_cache_mutex());
  if (TypeJudgementCache::instance()->is_cached_equivalent_type(
          index1, index2, module1, module2)) {
    return true;
  }

  if (kind1 == kWasmStructTypeCode) {
    return StructEquivalentIndices(index1, index2, module1, module2);
  } else if (kind1 == kWasmArrayTypeCode) {
    return ArrayEquivalentIndices(index1, index2, module1, module2);
  } else {
    DCHECK_EQ(kind1, kWasmFunctionTypeCode);
    return FunctionEquivalentIndices(index1, index2, module1, module2);
  }
}

bool StructIsSubtypeOf(uint32_t subtype_index, uint32_t supertype_index,
                       const WasmModule* sub_module,
                       const WasmModule* super_module) {
  const StructType* sub_struct = sub_module->types[subtype_index].struct_type;
  const StructType* super_struct =
      super_module->types[supertype_index].struct_type;

  if (sub_struct->field_count() < super_struct->field_count()) {
    return false;
  }

  TypeJudgementCache::instance()->cache_subtype(subtype_index, supertype_index,
                                                sub_module, super_module);
  for (uint32_t i = 0; i < super_struct->field_count(); i++) {
    bool sub_mut = sub_struct->mutability(i);
    bool super_mut = super_struct->mutability(i);
    if (sub_mut != super_mut ||
        (sub_mut &&
         !EquivalentTypes(sub_struct->field(i), super_struct->field(i),
                          sub_module, super_module)) ||
        (!sub_mut && !IsSubtypeOf(sub_struct->field(i), super_struct->field(i),
                                  sub_module, super_module))) {
      TypeJudgementCache::instance()->uncache_subtype(
          subtype_index, supertype_index, sub_module, super_module);
      return false;
    }
  }
  return true;
}

bool ArrayIsSubtypeOf(uint32_t subtype_index, uint32_t supertype_index,
                      const WasmModule* sub_module,
                      const WasmModule* super_module) {
  const ArrayType* sub_array = sub_module->types[subtype_index].array_type;
  const ArrayType* super_array =
      super_module->types[supertype_index].array_type;
  bool sub_mut = sub_array->mutability();
  bool super_mut = super_array->mutability();
  TypeJudgementCache::instance()->cache_subtype(subtype_index, supertype_index,
                                                sub_module, super_module);
  if (sub_mut != super_mut ||
      (sub_mut &&
       !EquivalentTypes(sub_array->element_type(), super_array->element_type(),
                        sub_module, super_module)) ||
      (!sub_mut &&
       !IsSubtypeOf(sub_array->element_type(), super_array->element_type(),
                    sub_module, super_module))) {
    TypeJudgementCache::instance()->uncache_subtype(
        subtype_index, supertype_index, sub_module, super_module);
    return false;
  } else {
    return true;
  }
}

// TODO(7748): Expand this with function subtyping once the hiccups
// with 'exact types' have been cleared.
bool FunctionIsSubtypeOf(uint32_t subtype_index, uint32_t supertype_index,
                         const WasmModule* sub_module,
                         const WasmModule* super_module) {
  return FunctionEquivalentIndices(subtype_index, supertype_index, sub_module,
                                   super_module);
}

}  // namespace

// TODO(7748): Extend this with any-heap subtyping.
V8_NOINLINE V8_EXPORT_PRIVATE bool IsSubtypeOfImpl(
    ValueType subtype, ValueType supertype, const WasmModule* sub_module,
    const WasmModule* super_module) {
  DCHECK(subtype != supertype || sub_module != super_module);

  // This function checks for subtyping based on the kind of subtype.

  if (!subtype.is_reference_type()) return subtype == supertype;

  if (subtype.kind() == ValueType::kRtt) {
    return subtype.heap_type().is_generic()
               ? subtype == supertype
               : (supertype.kind() == ValueType::kRtt &&
                  subtype.depth() == supertype.depth() &&
                  EquivalentIndices(subtype.ref_index(), supertype.ref_index(),
                                    sub_module, super_module));
  }

  DCHECK(subtype.is_object_reference_type());

  bool compatible_references = subtype.kind() == ValueType::kOptRef
                                   ? supertype.kind() == ValueType::kOptRef
                                   : supertype.is_object_reference_type();
  if (!compatible_references) return false;

  DCHECK(supertype.is_object_reference_type());

  // Now check that sub_heap and super_heap are subtype-related.

  HeapType sub_heap = subtype.heap_type();
  HeapType super_heap = supertype.heap_type();

  if (sub_heap.representation() == HeapType::kI31 &&
      super_heap.representation() == HeapType::kEq) {
    return true;
  }
  if (sub_heap.is_generic()) return sub_heap == super_heap;

  DCHECK(sub_heap.is_index());
  uint32_t sub_index = sub_heap.ref_index();
  DCHECK(sub_module->has_type(sub_index));

  if (super_heap.representation() == HeapType::kEq) {
    return !sub_module->has_signature(sub_heap.ref_index());
  }
  if (super_heap.representation() == HeapType::kFunc) {
    return sub_module->has_signature(sub_heap.ref_index());
  }
  if (super_heap.is_generic()) return false;

  DCHECK(super_heap.is_index());
  uint32_t super_index = super_heap.ref_index();
  DCHECK(super_module->has_type(super_index));

  uint8_t sub_kind = sub_module->type_kinds[sub_index];

  if (sub_kind != super_module->type_kinds[super_index]) return false;

  // Accessing the caches for subtyping and equivalence from multiple background
  // threads is protected by a lock.
  base::RecursiveMutexGuard type_cache_access(
      TypeJudgementCache::instance()->type_cache_mutex());
  if (TypeJudgementCache::instance()->is_cached_subtype(
          sub_index, super_index, sub_module, super_module)) {
    return true;
  }

  if (sub_kind == kWasmStructTypeCode) {
    return StructIsSubtypeOf(sub_index, super_index, sub_module, super_module);
  } else if (sub_kind == kWasmArrayTypeCode) {
    return ArrayIsSubtypeOf(sub_index, super_index, sub_module, super_module);
  } else {
    DCHECK_EQ(sub_kind, kWasmFunctionTypeCode);
    return FunctionIsSubtypeOf(sub_index, super_index, sub_module,
                               super_module);
  }
}

V8_NOINLINE bool EquivalentTypes(ValueType type1, ValueType type2,
                                 const WasmModule* module1,
                                 const WasmModule* module2) {
  if (type1 == type2 && module1 == module2) return true;
  if (!type1.has_index()) return type1 == type2;
  if (type1.kind() != type2.kind()) return false;

  DCHECK(type1.has_index() && type2.has_index() &&
         (type1 != type2 || module1 != module2));

  DCHECK_IMPLIES(type1.has_depth(), type2.has_depth());  // Due to 'if' above
  if (type1.has_depth() && type1.depth() != type2.depth()) return false;

  DCHECK(type1.has_index() && module1->has_type(type1.ref_index()) &&
         type2.has_index() && module2->has_type(type2.ref_index()));

  return EquivalentIndices(type1.ref_index(), type2.ref_index(), module1,
                           module2);
}

ValueType CommonSubtype(ValueType a, ValueType b, const WasmModule* module) {
  if (a == b) return a;
  if (IsSubtypeOf(a, b, module)) return a;
  if (IsSubtypeOf(b, a, module)) return b;
  return kWasmBottom;
}

}  // namespace wasm
}  // namespace internal
}  // namespace v8