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 | |