1// Copyright 2020 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/wasm/wasm-subtyping.h"
6
7#include "src/base/platform/mutex.h"
8#include "src/wasm/canonical-types.h"
9#include "src/wasm/wasm-module.h"
10#include "src/zone/zone-containers.h"
11
12namespace v8 {
13namespace internal {
14namespace wasm {
15
16namespace {
17
18V8_INLINE bool EquivalentIndices(uint32_t index1, uint32_t index2,
19                                 const WasmModule* module1,
20                                 const WasmModule* module2) {
21  DCHECK(index1 != index2 || module1 != module2);
22  if (!FLAG_wasm_type_canonicalization) return false;
23  return module1->isorecursive_canonical_type_ids[index1] ==
24         module2->isorecursive_canonical_type_ids[index2];
25}
26
27bool ValidStructSubtypeDefinition(uint32_t subtype_index,
28                                  uint32_t supertype_index,
29                                  const WasmModule* sub_module,
30                                  const WasmModule* super_module) {
31  const StructType* sub_struct = sub_module->types[subtype_index].struct_type;
32  const StructType* super_struct =
33      super_module->types[supertype_index].struct_type;
34
35  if (sub_struct->field_count() < super_struct->field_count()) {
36    return false;
37  }
38
39  for (uint32_t i = 0; i < super_struct->field_count(); i++) {
40    bool sub_mut = sub_struct->mutability(i);
41    bool super_mut = super_struct->mutability(i);
42    if (sub_mut != super_mut ||
43        (sub_mut &&
44         !EquivalentTypes(sub_struct->field(i), super_struct->field(i),
45                          sub_module, super_module)) ||
46        (!sub_mut && !IsSubtypeOf(sub_struct->field(i), super_struct->field(i),
47                                  sub_module, super_module))) {
48      return false;
49    }
50  }
51  return true;
52}
53
54bool ValidArraySubtypeDefinition(uint32_t subtype_index,
55                                 uint32_t supertype_index,
56                                 const WasmModule* sub_module,
57                                 const WasmModule* super_module) {
58  const ArrayType* sub_array = sub_module->types[subtype_index].array_type;
59  const ArrayType* super_array =
60      super_module->types[supertype_index].array_type;
61  bool sub_mut = sub_array->mutability();
62  bool super_mut = super_array->mutability();
63
64  return (sub_mut && super_mut &&
65          EquivalentTypes(sub_array->element_type(),
66                          super_array->element_type(), sub_module,
67                          super_module)) ||
68         (!sub_mut && !super_mut &&
69          IsSubtypeOf(sub_array->element_type(), super_array->element_type(),
70                      sub_module, super_module));
71}
72
73bool ValidFunctionSubtypeDefinition(uint32_t subtype_index,
74                                    uint32_t supertype_index,
75                                    const WasmModule* sub_module,
76                                    const WasmModule* super_module) {
77  const FunctionSig* sub_func = sub_module->types[subtype_index].function_sig;
78  const FunctionSig* super_func =
79      super_module->types[supertype_index].function_sig;
80
81  if (sub_func->parameter_count() != super_func->parameter_count() ||
82      sub_func->return_count() != super_func->return_count()) {
83    return false;
84  }
85
86  for (uint32_t i = 0; i < sub_func->parameter_count(); i++) {
87    // Contravariance for params.
88    if (!IsSubtypeOf(super_func->parameters()[i], sub_func->parameters()[i],
89                     super_module, sub_module)) {
90      return false;
91    }
92  }
93  for (uint32_t i = 0; i < sub_func->return_count(); i++) {
94    // Covariance for returns.
95    if (!IsSubtypeOf(sub_func->returns()[i], super_func->returns()[i],
96                     sub_module, super_module)) {
97      return false;
98    }
99  }
100
101  return true;
102}
103
104}  // namespace
105
106bool ValidSubtypeDefinition(uint32_t subtype_index, uint32_t supertype_index,
107                            const WasmModule* sub_module,
108                            const WasmModule* super_module) {
109  TypeDefinition::Kind sub_kind = sub_module->types[subtype_index].kind;
110  TypeDefinition::Kind super_kind = super_module->types[supertype_index].kind;
111  if (sub_kind != super_kind) return false;
112  switch (sub_kind) {
113    case TypeDefinition::kFunction:
114      return ValidFunctionSubtypeDefinition(subtype_index, supertype_index,
115                                            sub_module, super_module);
116    case TypeDefinition::kStruct:
117      return ValidStructSubtypeDefinition(subtype_index, supertype_index,
118                                          sub_module, super_module);
119    case TypeDefinition::kArray:
120      return ValidArraySubtypeDefinition(subtype_index, supertype_index,
121                                         sub_module, super_module);
122  }
123}
124
125V8_NOINLINE V8_EXPORT_PRIVATE bool IsSubtypeOfImpl(
126    ValueType subtype, ValueType supertype, const WasmModule* sub_module,
127    const WasmModule* super_module) {
128  DCHECK(subtype != supertype || sub_module != super_module);
129
130  switch (subtype.kind()) {
131    case kI32:
132    case kI64:
133    case kF32:
134    case kF64:
135    case kS128:
136    case kI8:
137    case kI16:
138    case kVoid:
139    case kBottom:
140      return subtype == supertype;
141    case kRtt:
142      return supertype.kind() == kRtt &&
143             EquivalentIndices(subtype.ref_index(), supertype.ref_index(),
144                               sub_module, super_module);
145    case kRef:
146    case kOptRef:
147      break;
148  }
149
150  DCHECK(subtype.is_object_reference());
151
152  bool compatible_references = subtype.is_nullable()
153                                   ? supertype.is_nullable()
154                                   : supertype.is_object_reference();
155  if (!compatible_references) return false;
156
157  DCHECK(supertype.is_object_reference());
158
159  // Now check that sub_heap and super_heap are subtype-related.
160
161  HeapType sub_heap = subtype.heap_type();
162  HeapType super_heap = supertype.heap_type();
163
164  switch (sub_heap.representation()) {
165    case HeapType::kFunc:
166      // funcref is a subtype of anyref (aka externref) under wasm-gc.
167      return sub_heap == super_heap ||
168             (FLAG_experimental_wasm_gc && super_heap == HeapType::kAny);
169    case HeapType::kEq:
170      return sub_heap == super_heap || super_heap == HeapType::kAny;
171    case HeapType::kAny:
172      return super_heap == HeapType::kAny;
173    case HeapType::kI31:
174    case HeapType::kData:
175      return super_heap == sub_heap || super_heap == HeapType::kEq ||
176             super_heap == HeapType::kAny;
177    case HeapType::kArray:
178      return super_heap == HeapType::kArray || super_heap == HeapType::kData ||
179             super_heap == HeapType::kEq || super_heap == HeapType::kAny;
180    case HeapType::kBottom:
181      UNREACHABLE();
182    default:
183      break;
184  }
185
186  DCHECK(sub_heap.is_index());
187  uint32_t sub_index = sub_heap.ref_index();
188  DCHECK(sub_module->has_type(sub_index));
189
190  switch (super_heap.representation()) {
191    case HeapType::kFunc:
192      return sub_module->has_signature(sub_index);
193    case HeapType::kEq:
194    case HeapType::kData:
195      return !sub_module->has_signature(sub_index);
196    case HeapType::kArray:
197      return sub_module->has_array(sub_index);
198    case HeapType::kI31:
199      return false;
200    case HeapType::kAny:
201      return true;
202    case HeapType::kBottom:
203      UNREACHABLE();
204    default:
205      break;
206  }
207
208  DCHECK(super_heap.is_index());
209  uint32_t super_index = super_heap.ref_index();
210  DCHECK(super_module->has_type(super_index));
211  // The {IsSubtypeOf} entry point already has a fast path checking ValueType
212  // equality; here we catch (ref $x) being a subtype of (ref null $x).
213  if (sub_module == super_module && sub_index == super_index) return true;
214
215  if (FLAG_wasm_type_canonicalization) {
216    return GetTypeCanonicalizer()->IsCanonicalSubtype(sub_index, super_index,
217                                                      sub_module, super_module);
218  } else {
219    uint32_t explicit_super = sub_module->supertype(sub_index);
220    while (true) {
221      if (explicit_super == super_index) return true;
222      // Reached the end of the explicitly defined inheritance chain.
223      if (explicit_super == kNoSuperType) return false;
224      explicit_super = sub_module->supertype(explicit_super);
225    }
226  }
227}
228
229V8_NOINLINE bool EquivalentTypes(ValueType type1, ValueType type2,
230                                 const WasmModule* module1,
231                                 const WasmModule* module2) {
232  if (type1 == type2 && module1 == module2) return true;
233  if (!type1.has_index()) return type1 == type2;
234  if (type1.kind() != type2.kind()) return false;
235
236  DCHECK(type1.has_index() && type2.has_index() &&
237         (type1 != type2 || module1 != module2));
238
239  DCHECK(type1.has_index() && module1->has_type(type1.ref_index()) &&
240         type2.has_index() && module2->has_type(type2.ref_index()));
241
242  return EquivalentIndices(type1.ref_index(), type2.ref_index(), module1,
243                           module2);
244}
245
246}  // namespace wasm
247}  // namespace internal
248}  // namespace v8
249