wasm-subtyping.cc 19.8 KB
Newer Older
1 2 3 4 5 6
// 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"

7
#include "src/wasm/canonical-types.h"
8 9 10 11 12 13 14 15
#include "src/wasm/wasm-module.h"

namespace v8 {
namespace internal {
namespace wasm {

namespace {

16 17 18 19
V8_INLINE bool EquivalentIndices(uint32_t index1, uint32_t index2,
                                 const WasmModule* module1,
                                 const WasmModule* module2) {
  DCHECK(index1 != index2 || module1 != module2);
20
  if (!v8_flags.wasm_type_canonicalization) return false;
21 22
  return module1->isorecursive_canonical_type_ids[index1] ==
         module2->isorecursive_canonical_type_ids[index2];
23 24
}

25 26 27 28
bool ValidStructSubtypeDefinition(uint32_t subtype_index,
                                  uint32_t supertype_index,
                                  const WasmModule* sub_module,
                                  const WasmModule* super_module) {
29 30 31
  const StructType* sub_struct = sub_module->types[subtype_index].struct_type;
  const StructType* super_struct =
      super_module->types[supertype_index].struct_type;
32 33 34 35 36 37 38 39 40 41

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

  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 &&
42 43 44 45
         !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))) {
46 47 48 49 50 51
      return false;
    }
  }
  return true;
}

52 53 54 55
bool ValidArraySubtypeDefinition(uint32_t subtype_index,
                                 uint32_t supertype_index,
                                 const WasmModule* sub_module,
                                 const WasmModule* super_module) {
56 57 58
  const ArrayType* sub_array = sub_module->types[subtype_index].array_type;
  const ArrayType* super_array =
      super_module->types[supertype_index].array_type;
59 60
  bool sub_mut = sub_array->mutability();
  bool super_mut = super_array->mutability();
61 62 63 64 65 66 67 68

  return (sub_mut && super_mut &&
          EquivalentTypes(sub_array->element_type(),
                          super_array->element_type(), sub_module,
                          super_module)) ||
         (!sub_mut && !super_mut &&
          IsSubtypeOf(sub_array->element_type(), super_array->element_type(),
                      sub_module, super_module));
69
}
70

71 72 73 74
bool ValidFunctionSubtypeDefinition(uint32_t subtype_index,
                                    uint32_t supertype_index,
                                    const WasmModule* sub_module,
                                    const WasmModule* super_module) {
75 76 77 78 79 80 81 82
  const FunctionSig* sub_func = sub_module->types[subtype_index].function_sig;
  const FunctionSig* super_func =
      super_module->types[supertype_index].function_sig;

  if (sub_func->parameter_count() != super_func->parameter_count() ||
      sub_func->return_count() != super_func->return_count()) {
    return false;
  }
83

84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
  for (uint32_t i = 0; i < sub_func->parameter_count(); i++) {
    // Contravariance for params.
    if (!IsSubtypeOf(super_func->parameters()[i], sub_func->parameters()[i],
                     super_module, sub_module)) {
      return false;
    }
  }
  for (uint32_t i = 0; i < sub_func->return_count(); i++) {
    // Covariance for returns.
    if (!IsSubtypeOf(sub_func->returns()[i], super_func->returns()[i],
                     sub_module, super_module)) {
      return false;
    }
  }

  return true;
}
101

102 103
HeapType::Representation NullSentinelImpl(TypeInModule type) {
  switch (type.type.heap_type().representation()) {
104 105 106 107 108 109 110 111 112 113 114
    case HeapType::kI31:
    case HeapType::kNone:
    case HeapType::kEq:
    case HeapType::kData:
    case HeapType::kArray:
    case HeapType::kAny:
    case HeapType::kString:
    case HeapType::kStringViewWtf8:
    case HeapType::kStringViewWtf16:
    case HeapType::kStringViewIter:
      return HeapType::kNone;
115 116 117
    case HeapType::kExtern:
    case HeapType::kNoExtern:
      return HeapType::kNoExtern;
118 119 120 121
    case HeapType::kFunc:
    case HeapType::kNoFunc:
      return HeapType::kNoFunc;
    default:
122 123 124
      return type.module->has_signature(type.type.ref_index())
                 ? HeapType::kNoFunc
                 : HeapType::kNone;
125 126 127 128 129 130
  }
}

bool IsNullSentinel(HeapType type) {
  switch (type.representation()) {
    case HeapType::kNone:
131
    case HeapType::kNoExtern:
132 133 134 135 136 137 138
    case HeapType::kNoFunc:
      return true;
    default:
      return false;
  }
}

139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
}  // namespace

bool ValidSubtypeDefinition(uint32_t subtype_index, uint32_t supertype_index,
                            const WasmModule* sub_module,
                            const WasmModule* super_module) {
  TypeDefinition::Kind sub_kind = sub_module->types[subtype_index].kind;
  TypeDefinition::Kind super_kind = super_module->types[supertype_index].kind;
  if (sub_kind != super_kind) return false;
  switch (sub_kind) {
    case TypeDefinition::kFunction:
      return ValidFunctionSubtypeDefinition(subtype_index, supertype_index,
                                            sub_module, super_module);
    case TypeDefinition::kStruct:
      return ValidStructSubtypeDefinition(subtype_index, supertype_index,
                                          sub_module, super_module);
    case TypeDefinition::kArray:
      return ValidArraySubtypeDefinition(subtype_index, supertype_index,
                                         sub_module, super_module);
  }
}

160 161 162 163 164
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);

165
  switch (subtype.kind()) {
166 167 168 169 170 171 172
    case kI32:
    case kI64:
    case kF32:
    case kF64:
    case kS128:
    case kI8:
    case kI16:
173
    case kVoid:
174
    case kBottom:
175
      return subtype == supertype;
176 177
    case kRtt:
      return supertype.kind() == kRtt &&
178 179
             EquivalentIndices(subtype.ref_index(), supertype.ref_index(),
                               sub_module, super_module);
180
    case kRef:
181
    case kRefNull:
182
      break;
183 184
  }

185
  DCHECK(subtype.is_object_reference());
186

187 188
  bool compatible_references = subtype.is_nullable()
                                   ? supertype.is_nullable()
189
                                   : supertype.is_object_reference();
190 191
  if (!compatible_references) return false;

192
  DCHECK(supertype.is_object_reference());
193 194 195

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

196 197 198
  HeapType sub_heap = subtype.heap_type();
  HeapType super_heap = supertype.heap_type();

199 200 201 202 203 204
  return IsHeapSubtypeOfImpl(sub_heap, super_heap, sub_module, super_module);
}

V8_NOINLINE V8_EXPORT_PRIVATE bool IsHeapSubtypeOfImpl(
    HeapType sub_heap, HeapType super_heap, const WasmModule* sub_module,
    const WasmModule* super_module) {
205 206
  switch (sub_heap.representation()) {
    case HeapType::kFunc:
207
      return sub_heap == super_heap;
208 209 210 211
    case HeapType::kEq:
      return sub_heap == super_heap || super_heap == HeapType::kAny;
    case HeapType::kAny:
      return super_heap == HeapType::kAny;
212 213
    case HeapType::kExtern:
      return super_heap == HeapType::kExtern;
214
    case HeapType::kI31:
215 216
    case HeapType::kData:
      return super_heap == sub_heap || super_heap == HeapType::kEq ||
217
             super_heap == HeapType::kAny;
218 219 220
    case HeapType::kArray:
      return super_heap == HeapType::kArray || super_heap == HeapType::kData ||
             super_heap == HeapType::kEq || super_heap == HeapType::kAny;
221 222 223 224 225 226
    case HeapType::kString:
    case HeapType::kStringViewWtf8:
    case HeapType::kStringViewWtf16:
    case HeapType::kStringViewIter:
      // stringref is a subtype of anyref (aka externref) under wasm-gc.
      return sub_heap == super_heap ||
227
             (v8_flags.experimental_wasm_gc && super_heap == HeapType::kAny);
228 229
    case HeapType::kBottom:
      UNREACHABLE();
230
    case HeapType::kNone:
231 232 233 234 235
      // none is a subtype of every non-func, non-extern reference type under
      // wasm-gc.
      if (super_heap.is_index()) {
        return !super_module->has_signature(super_heap.ref_index());
      }
236 237 238 239 240 241
      return super_heap != HeapType::kFunc && super_heap != HeapType::kNoFunc &&
             super_heap != HeapType::kExtern &&
             super_heap != HeapType::kNoExtern;
    case HeapType::kNoExtern:
      return super_heap == HeapType::kNoExtern ||
             super_heap == HeapType::kExtern;
242 243 244 245 246 247
    case HeapType::kNoFunc:
      // nofunc is a subtype of every funcref type under wasm-gc.
      if (super_heap.is_index()) {
        return super_module->has_signature(super_heap.ref_index());
      }
      return super_heap == HeapType::kNoFunc || super_heap == HeapType::kFunc;
248 249
    default:
      break;
250
  }
251 252 253 254 255

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

256 257 258 259
  switch (super_heap.representation()) {
    case HeapType::kFunc:
      return sub_module->has_signature(sub_index);
    case HeapType::kEq:
260
    case HeapType::kData:
261
    case HeapType::kAny:
262
      return !sub_module->has_signature(sub_index);
263 264
    case HeapType::kArray:
      return sub_module->has_array(sub_index);
265 266
    case HeapType::kI31:
      return false;
267 268
    case HeapType::kExtern:
      return false;
269 270 271 272 273
    case HeapType::kString:
    case HeapType::kStringViewWtf8:
    case HeapType::kStringViewWtf16:
    case HeapType::kStringViewIter:
      return false;
274 275
    case HeapType::kBottom:
      UNREACHABLE();
276
    case HeapType::kNone:
277
    case HeapType::kNoExtern:
278 279
    case HeapType::kNoFunc:
      // Abstract null types are not supertypes for any index type.
280
      return false;
281 282
    default:
      break;
283 284
  }

285 286 287
  DCHECK(super_heap.is_index());
  uint32_t super_index = super_heap.ref_index();
  DCHECK(super_module->has_type(super_index));
288 289 290
  // The {IsSubtypeOf} entry point already has a fast path checking ValueType
  // equality; here we catch (ref $x) being a subtype of (ref null $x).
  if (sub_module == super_module && sub_index == super_index) return true;
291

292
  if (v8_flags.wasm_type_canonicalization) {
293 294 295 296 297 298 299 300 301 302
    return GetTypeCanonicalizer()->IsCanonicalSubtype(sub_index, super_index,
                                                      sub_module, super_module);
  } else {
    uint32_t explicit_super = sub_module->supertype(sub_index);
    while (true) {
      if (explicit_super == super_index) return true;
      // Reached the end of the explicitly defined inheritance chain.
      if (explicit_super == kNoSuperType) return false;
      explicit_super = sub_module->supertype(explicit_super);
    }
303 304 305 306 307 308 309
  }
}

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

313
  DCHECK(type1 != type2 || module1 != module2);
314 315 316 317 318
  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);
319 320
}

321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355
namespace {
// Returns the least common ancestor of two type indices, as a type index in
// {module1}.
HeapType::Representation CommonAncestor(uint32_t type_index1,
                                        uint32_t type_index2,
                                        const WasmModule* module1,
                                        const WasmModule* module2) {
  TypeDefinition::Kind kind1 = module1->types[type_index1].kind;
  TypeDefinition::Kind kind2 = module2->types[type_index2].kind;
  {
    int depth1 = GetSubtypingDepth(module1, type_index1);
    int depth2 = GetSubtypingDepth(module2, type_index2);
    while (depth1 > depth2) {
      type_index1 = module1->supertype(type_index1);
      depth1--;
    }
    while (depth2 > depth1) {
      type_index2 = module2->supertype(type_index2);
      depth2--;
    }
  }
  DCHECK_NE(type_index1, kNoSuperType);
  DCHECK_NE(type_index2, kNoSuperType);
  while (type_index1 != kNoSuperType &&
         !(type_index1 == type_index2 && module1 == module2) &&
         !EquivalentIndices(type_index1, type_index2, module1, module2)) {
    type_index1 = module1->supertype(type_index1);
    type_index2 = module2->supertype(type_index2);
  }
  DCHECK_EQ(type_index1 == kNoSuperType, type_index2 == kNoSuperType);
  if (type_index1 != kNoSuperType) {
    return static_cast<HeapType::Representation>(type_index1);
  }
  switch (kind1) {
    case TypeDefinition::kFunction:
356 357
      DCHECK_EQ(kind2, kind1);
      return HeapType::kFunc;
358
    case TypeDefinition::kStruct:
359 360
      DCHECK_NE(kind2, TypeDefinition::kFunction);
      return HeapType::kData;
361 362 363
    case TypeDefinition::kArray:
      switch (kind2) {
        case TypeDefinition::kFunction:
364
          UNREACHABLE();
365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380
        case TypeDefinition::kStruct:
          return HeapType::kData;
        case TypeDefinition::kArray:
          return HeapType::kArray;
      }
  }
}

// Returns the least common ancestor of a generic HeapType {heap1}, and
// another HeapType {heap2}.
HeapType::Representation CommonAncestorWithGeneric(HeapType heap1,
                                                   HeapType heap2,
                                                   const WasmModule* module2) {
  DCHECK(heap1.is_generic());
  switch (heap1.representation()) {
    case HeapType::kFunc:
381 382
      DCHECK(IsHeapSubtypeOf(heap2, heap1, module2, module2));
      return HeapType::kFunc;
383 384 385 386 387 388 389 390
    case HeapType::kEq: {
      return IsHeapSubtypeOf(heap2, heap1, module2, module2)
                 ? heap1.representation()
                 : HeapType::kAny;
    }
    case HeapType::kI31:
      switch (heap2.representation()) {
        case HeapType::kI31:
391
        case HeapType::kNone:
392 393 394 395 396 397 398
          return HeapType::kI31;
        case HeapType::kEq:
        case HeapType::kData:
        case HeapType::kArray:
          return HeapType::kEq;
        case HeapType::kAny:
          return HeapType::kAny;
399
        case HeapType::kFunc:
400
        case HeapType::kExtern:
401
        case HeapType::kNoExtern:
402
        case HeapType::kNoFunc:
403
          UNREACHABLE();
404
        default:
405
          return module2->has_signature(heap2.ref_index()) ? HeapType::kBottom
406 407 408 409 410 411
                                                           : HeapType::kEq;
      }
    case HeapType::kData:
      switch (heap2.representation()) {
        case HeapType::kData:
        case HeapType::kArray:
412
        case HeapType::kNone:
413 414 415 416 417 418
          return HeapType::kData;
        case HeapType::kI31:
        case HeapType::kEq:
          return HeapType::kEq;
        case HeapType::kAny:
          return HeapType::kAny;
419
        case HeapType::kFunc:
420
        case HeapType::kExtern:
421
        case HeapType::kNoExtern:
422
        case HeapType::kNoFunc:
423
          UNREACHABLE();
424
        default:
425
          return module2->has_signature(heap2.ref_index()) ? HeapType::kBottom
426 427 428 429 430
                                                           : HeapType::kData;
      }
    case HeapType::kArray:
      switch (heap2.representation()) {
        case HeapType::kArray:
431
        case HeapType::kNone:
432 433 434 435 436 437 438 439
          return HeapType::kArray;
        case HeapType::kData:
          return HeapType::kData;
        case HeapType::kI31:
        case HeapType::kEq:
          return HeapType::kEq;
        case HeapType::kAny:
          return HeapType::kAny;
440
        case HeapType::kFunc:
441
        case HeapType::kExtern:
442
        case HeapType::kNoExtern:
443
        case HeapType::kNoFunc:
444
          UNREACHABLE();
445 446 447
        default:
          return module2->has_array(heap2.ref_index())    ? HeapType::kArray
                 : module2->has_struct(heap2.ref_index()) ? HeapType::kData
448
                                                          : HeapType::kBottom;
449 450 451 452 453
      }
    case HeapType::kAny:
      return HeapType::kAny;
    case HeapType::kBottom:
      return HeapType::kBottom;
454 455
    case HeapType::kNone:
      return heap2.representation();
456 457 458 459 460 461 462 463 464
    case HeapType::kNoFunc:
      switch (heap2.representation()) {
        case HeapType::kArray:
        case HeapType::kNone:
        case HeapType::kData:
        case HeapType::kI31:
        case HeapType::kEq:
        case HeapType::kAny:
        case HeapType::kExtern:
465
        case HeapType::kNoExtern:
466 467 468 469 470 471 472 473 474 475
          UNREACHABLE();
        case HeapType::kNoFunc:
          return HeapType::kNoFunc;
        case HeapType::kFunc:
          return HeapType::kFunc;
        default:
          return module2->has_signature(heap2.ref_index())
                     ? heap2.representation()
                     : HeapType::kBottom;
      }
476 477 478 479 480
    case HeapType::kNoExtern:
      return heap2.representation() == HeapType::kExtern ? HeapType::kExtern
                                                         : HeapType::kNoExtern;
    case HeapType::kExtern:
      return HeapType::kExtern;
481 482 483 484 485 486
    default:
      UNREACHABLE();
  }
}
}  // namespace

487 488 489
V8_EXPORT_PRIVATE TypeInModule Union(ValueType type1, ValueType type2,
                                     const WasmModule* module1,
                                     const WasmModule* module2) {
490 491 492 493 494 495 496 497 498 499
  if (!type1.is_object_reference() || !type2.is_object_reference()) {
    return {
        EquivalentTypes(type1, type2, module1, module2) ? type1 : kWasmBottom,
        module1};
  }
  Nullability nullability =
      type1.is_nullable() || type2.is_nullable() ? kNullable : kNonNullable;
  HeapType heap1 = type1.heap_type();
  HeapType heap2 = type2.heap_type();
  if (heap1 == heap2 && module1 == module2) {
500
    return {ValueType::RefMaybeNull(heap1, nullability), module1};
501 502
  }
  if (heap1.is_generic()) {
503 504
    return {ValueType::RefMaybeNull(
                CommonAncestorWithGeneric(heap1, heap2, module2), nullability),
505 506
            module1};
  } else if (heap2.is_generic()) {
507 508
    return {ValueType::RefMaybeNull(
                CommonAncestorWithGeneric(heap2, heap1, module1), nullability),
509 510
            module1};
  } else {
511 512 513 514
    return {ValueType::RefMaybeNull(
                CommonAncestor(heap1.ref_index(), heap2.ref_index(), module1,
                               module2),
                nullability),
515 516 517 518 519 520 521 522 523 524 525 526 527 528
            module1};
  }
}

TypeInModule Intersection(ValueType type1, ValueType type2,
                          const WasmModule* module1,
                          const WasmModule* module2) {
  if (!type1.is_object_reference() || !type2.is_object_reference()) {
    return {
        EquivalentTypes(type1, type2, module1, module2) ? type1 : kWasmBottom,
        module1};
  }
  Nullability nullability =
      type1.is_nullable() && type2.is_nullable() ? kNullable : kNonNullable;
529 530 531
  // non-nullable null type is not a valid type.
  if (nullability == kNonNullable && (IsNullSentinel(type1.heap_type()) ||
                                      IsNullSentinel(type2.heap_type()))) {
532 533 534 535 536 537 538 539 540 541
    return {kWasmBottom, module1};
  }
  if (IsHeapSubtypeOf(type1.heap_type(), type2.heap_type(), module1, module2)) {
    return TypeInModule{ValueType::RefMaybeNull(type1.heap_type(), nullability),
                        module1};
  }
  if (IsHeapSubtypeOf(type2.heap_type(), type1.heap_type(), module2, module1)) {
    return TypeInModule{ValueType::RefMaybeNull(type2.heap_type(), nullability),
                        module2};
  }
542 543 544 545
  if (nullability == kNonNullable) {
    return {kWasmBottom, module1};
  }
  // Check for common null representation.
546 547 548
  ValueType null_type1 = ToNullSentinel({type1, module1});
  if (null_type1 == ToNullSentinel({type2, module2})) {
    return {null_type1, module1};
549 550
  }
  return {kWasmBottom, module1};
551 552
}

553 554 555 556 557 558 559
ValueType ToNullSentinel(TypeInModule type) {
  HeapType::Representation null_heap = NullSentinelImpl(type);
  DCHECK(
      IsHeapSubtypeOf(HeapType(null_heap), type.type.heap_type(), type.module));
  return ValueType::RefNull(null_heap);
}

560 561 562
}  // namespace wasm
}  // namespace internal
}  // namespace v8