| 1 | /* |
|---|
| 2 | * Copyright 2023 WebAssembly Community Group participants |
|---|
| 3 | * |
|---|
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
|---|
| 5 | * you may not use this file except in compliance with the License. |
|---|
| 6 | * You may obtain a copy of the License at |
|---|
| 7 | * |
|---|
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
|---|
| 9 | * |
|---|
| 10 | * Unless required by applicable law or agreed to in writing, software |
|---|
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
|---|
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
|---|
| 13 | * See the License for the specific language governing permissions and |
|---|
| 14 | * limitations under the License. |
|---|
| 15 | */ |
|---|
| 16 | |
|---|
| 17 | #ifndef wasm_wasm_type_ordering_h |
|---|
| 18 | #define wasm_wasm_type_ordering_h |
|---|
| 19 | |
|---|
| 20 | #include <unordered_set> |
|---|
| 21 | |
|---|
| 22 | #include "support/insert_ordered.h" |
|---|
| 23 | #include "support/topological_sort.h" |
|---|
| 24 | #include "wasm-type.h" |
|---|
| 25 | |
|---|
| 26 | namespace wasm::HeapTypeOrdering { |
|---|
| 27 | |
|---|
| 28 | // Given a collection of types, iterate through it such that each type in the |
|---|
| 29 | // collection is visited only after its immediate supertype in the collection is |
|---|
| 30 | // visited. |
|---|
| 31 | template<typename SupertypeProvider> |
|---|
| 32 | struct SupertypesFirstBase |
|---|
| 33 | : TopologicalSort<HeapType, SupertypesFirstBase<SupertypeProvider>> { |
|---|
| 34 | // For each type in the input collection, whether it is a supertype. Used to |
|---|
| 35 | // track membership in the input collection. |
|---|
| 36 | InsertOrderedMap<HeapType, bool> typeSet; |
|---|
| 37 | |
|---|
| 38 | template<typename T> SupertypesFirstBase(const T& types) { |
|---|
| 39 | for (auto type : types) { |
|---|
| 40 | typeSet[type] = false; |
|---|
| 41 | } |
|---|
| 42 | // Find the supertypes that are in the collection. |
|---|
| 43 | for (auto [type, _] : typeSet) { |
|---|
| 44 | if (auto super = type.getSuperType()) { |
|---|
| 45 | if (auto it = typeSet.find(*super); it != typeSet.end()) { |
|---|
| 46 | it->second = true; |
|---|
| 47 | } |
|---|
| 48 | } |
|---|
| 49 | } |
|---|
| 50 | // Types that are not supertypes of others are the roots. |
|---|
| 51 | for (auto [type, isSuper] : typeSet) { |
|---|
| 52 | if (!isSuper) { |
|---|
| 53 | this->push(type); |
|---|
| 54 | } |
|---|
| 55 | } |
|---|
| 56 | } |
|---|
| 57 | |
|---|
| 58 | void pushPredecessors(HeapType type) { |
|---|
| 59 | // Do not visit types that weren't in the input collection. |
|---|
| 60 | if (auto super = static_cast<SupertypeProvider*>(this)->getSuperType(type); |
|---|
| 61 | super && typeSet.count(*super)) { |
|---|
| 62 | this->push(*super); |
|---|
| 63 | } |
|---|
| 64 | } |
|---|
| 65 | }; |
|---|
| 66 | |
|---|
| 67 | struct SupertypesFirst : SupertypesFirstBase<SupertypesFirst> { |
|---|
| 68 | template<typename T> |
|---|
| 69 | SupertypesFirst(const T& types) : SupertypesFirstBase(types) {} |
|---|
| 70 | |
|---|
| 71 | std::optional<HeapType> getSuperType(HeapType type) { |
|---|
| 72 | return type.getSuperType(); |
|---|
| 73 | } |
|---|
| 74 | }; |
|---|
| 75 | |
|---|
| 76 | } // namespace wasm::HeapTypeOrdering |
|---|
| 77 | |
|---|
| 78 | #endif // wasm_wasm_type_ordering_h |
|---|
| 79 | |
|---|
