From 2d70ee0d1d2620a676bdf82779187cf0ee5bd0cf Mon Sep 17 00:00:00 2001 From: Thomas Lively Date: Fri, 6 Sep 2024 17:24:52 -0700 Subject: [NFC] Rename the old topological sort utility (#6914) This will allow both the old and new topological sort utilities to be included into the same .cpp file while we phase out the old utility. --- src/ir/subtypes.h | 4 +- src/ir/type-updating.cpp | 1 - src/support/old_topological_sort.h | 119 +++++++++++++++++++++++++++++++++++++ src/support/topological_sort.h | 118 ------------------------------------ src/tools/wasm-ctor-eval.cpp | 4 +- src/wasm-type-ordering.h | 4 +- 6 files changed, 125 insertions(+), 125 deletions(-) create mode 100644 src/support/old_topological_sort.h delete mode 100644 src/support/topological_sort.h (limited to 'src') diff --git a/src/ir/subtypes.h b/src/ir/subtypes.h index 203772055..47ee51ac3 100644 --- a/src/ir/subtypes.h +++ b/src/ir/subtypes.h @@ -18,7 +18,7 @@ #define wasm_ir_subtypes_h #include "ir/module-utils.h" -#include "support/topological_sort.h" +#include "support/old_topological_sort.h" #include "wasm.h" namespace wasm { @@ -80,7 +80,7 @@ struct SubTypes { // A topological sort that visits subtypes first. auto getSubTypesFirstSort() const { - struct SubTypesFirstSort : TopologicalSort { + struct SubTypesFirstSort : OldTopologicalSort { const SubTypes& parent; SubTypesFirstSort(const SubTypes& parent) : parent(parent) { diff --git a/src/ir/type-updating.cpp b/src/ir/type-updating.cpp index 123b13119..17437cf2e 100644 --- a/src/ir/type-updating.cpp +++ b/src/ir/type-updating.cpp @@ -20,7 +20,6 @@ #include "ir/module-utils.h" #include "ir/names.h" #include "ir/utils.h" -#include "support/topological_sort.h" #include "wasm-type-ordering.h" #include "wasm-type.h" #include "wasm.h" diff --git a/src/support/old_topological_sort.h b/src/support/old_topological_sort.h new file mode 100644 index 000000000..2f7277412 --- /dev/null +++ b/src/support/old_topological_sort.h @@ -0,0 +1,119 @@ +/* + * Copyright 2022 WebAssembly Community Group participants + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef wasm_support_old_topological_sort_h +#define wasm_support_old_topological_sort_h + +#include +#include +#include +#include + +namespace wasm { + +// CRTP utility that provides an iterator through arbitrary directed acyclic +// graphs of data that will visit the data in a topologically sorted order +// (https://en.wikipedia.org/wiki/Topological_sorting). In other words, the +// iterator will produce each item only after all that item's predecessors have +// been produced. +// +// Subclasses should call `push` on all the root items in their constructors and +// implement a `void pushPredecessors(T item)` method that calls `push` on all +// the immediate predecessors of `item`. +// +// Cycles in the graph are not detected and will result in an infinite loop. +template struct OldTopologicalSort { +private: + // The DFS work list. + std::vector workStack; + + // Remember which items we have finished so we don't visit them again. + std::unordered_set finished; + + // Should be overridden by `Subtype`. + void pushPredecessors(T item) { + static_assert( + &OldTopologicalSort::pushPredecessors != + &Subtype::pushPredecessors, + "OldTopologicalSort subclass must implement `pushPredecessors`"); + } + + // Pop until the stack is empty or it has an unfinished item on top. + void finishCurr() { + finished.insert(workStack.back()); + workStack.pop_back(); + while (!workStack.empty() && finished.count(workStack.back())) { + workStack.pop_back(); + } + } + + // Advance until the next item to be finished is on top of the stack or the + // stack is empty. + void stepToNext() { + while (!workStack.empty()) { + T item = workStack.back(); + static_cast(this)->pushPredecessors(item); + if (workStack.back() == item) { + // No unfinished predecessors, so this is the next item in the sort. + break; + } + } + } + +protected: + // Call this from the `Subtype` constructor to add the root items and from + // `Subtype::pushPredecessors` to add predecessors. + void push(T item) { + if (finished.count(item)) { + return; + } + workStack.push_back(item); + } + +public: + struct Iterator { + using value_type = T; + using difference_type = std::ptrdiff_t; + using reference = T&; + using pointer = T*; + using iterator_category = std::input_iterator_tag; + + OldTopologicalSort* parent; + + bool isEnd() const { return !parent || parent->workStack.empty(); } + bool operator==(Iterator& other) const { return isEnd() == other.isEnd(); } + bool operator!=(Iterator& other) const { return !(*this == other); } + T operator*() { return parent->workStack.back(); } + void operator++(int) { + parent->finishCurr(); + parent->stepToNext(); + } + Iterator& operator++() { + (*this)++; + return *this; + } + }; + + Iterator begin() { + stepToNext(); + return {this}; + } + Iterator end() { return {nullptr}; } +}; + +} // namespace wasm + +#endif // wasm_support_old_topological_sort_h diff --git a/src/support/topological_sort.h b/src/support/topological_sort.h deleted file mode 100644 index 3594617eb..000000000 --- a/src/support/topological_sort.h +++ /dev/null @@ -1,118 +0,0 @@ -/* - * Copyright 2022 WebAssembly Community Group participants - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef wasm_support_topological_sort_h -#define wasm_support_topological_sort_h - -#include -#include -#include -#include - -namespace wasm { - -// CRTP utility that provides an iterator through arbitrary directed acyclic -// graphs of data that will visit the data in a topologically sorted order -// (https://en.wikipedia.org/wiki/Topological_sorting). In other words, the -// iterator will produce each item only after all that item's predecessors have -// been produced. -// -// Subclasses should call `push` on all the root items in their constructors and -// implement a `void pushPredecessors(T item)` method that calls `push` on all -// the immediate predecessors of `item`. -// -// Cycles in the graph are not detected and will result in an infinite loop. -template struct TopologicalSort { -private: - // The DFS work list. - std::vector workStack; - - // Remember which items we have finished so we don't visit them again. - std::unordered_set finished; - - // Should be overridden by `Subtype`. - void pushPredecessors(T item) { - static_assert(&TopologicalSort::pushPredecessors != - &Subtype::pushPredecessors, - "TopologicalSort subclass must implement `pushPredecessors`"); - } - - // Pop until the stack is empty or it has an unfinished item on top. - void finishCurr() { - finished.insert(workStack.back()); - workStack.pop_back(); - while (!workStack.empty() && finished.count(workStack.back())) { - workStack.pop_back(); - } - } - - // Advance until the next item to be finished is on top of the stack or the - // stack is empty. - void stepToNext() { - while (!workStack.empty()) { - T item = workStack.back(); - static_cast(this)->pushPredecessors(item); - if (workStack.back() == item) { - // No unfinished predecessors, so this is the next item in the sort. - break; - } - } - } - -protected: - // Call this from the `Subtype` constructor to add the root items and from - // `Subtype::pushPredecessors` to add predecessors. - void push(T item) { - if (finished.count(item)) { - return; - } - workStack.push_back(item); - } - -public: - struct Iterator { - using value_type = T; - using difference_type = std::ptrdiff_t; - using reference = T&; - using pointer = T*; - using iterator_category = std::input_iterator_tag; - - TopologicalSort* parent; - - bool isEnd() const { return !parent || parent->workStack.empty(); } - bool operator==(Iterator& other) const { return isEnd() == other.isEnd(); } - bool operator!=(Iterator& other) const { return !(*this == other); } - T operator*() { return parent->workStack.back(); } - void operator++(int) { - parent->finishCurr(); - parent->stepToNext(); - } - Iterator& operator++() { - (*this)++; - return *this; - } - }; - - Iterator begin() { - stepToNext(); - return {this}; - } - Iterator end() { return {nullptr}; } -}; - -} // namespace wasm - -#endif // wasm_support_topological_sort_h diff --git a/src/tools/wasm-ctor-eval.cpp b/src/tools/wasm-ctor-eval.cpp index 9cf552450..6809fa32a 100644 --- a/src/tools/wasm-ctor-eval.cpp +++ b/src/tools/wasm-ctor-eval.cpp @@ -36,9 +36,9 @@ #include "support/colors.h" #include "support/file.h" #include "support/insert_ordered.h" +#include "support/old_topological_sort.h" #include "support/small_set.h" #include "support/string.h" -#include "support/topological_sort.h" #include "tool-options.h" #include "wasm-builder.h" #include "wasm-interpreter.h" @@ -678,7 +678,7 @@ private: if (!mustBeAfter.empty()) { // We found constraints that require reordering, so do so. - struct MustBeAfterSort : TopologicalSort { + struct MustBeAfterSort : OldTopologicalSort { MustBeAfter& mustBeAfter; MustBeAfterSort(MustBeAfter& mustBeAfter) : mustBeAfter(mustBeAfter) { diff --git a/src/wasm-type-ordering.h b/src/wasm-type-ordering.h index 981ac004d..9ccf4c568 100644 --- a/src/wasm-type-ordering.h +++ b/src/wasm-type-ordering.h @@ -20,7 +20,7 @@ #include #include "support/insert_ordered.h" -#include "support/topological_sort.h" +#include "support/old_topological_sort.h" #include "wasm-type.h" namespace wasm::HeapTypeOrdering { @@ -30,7 +30,7 @@ namespace wasm::HeapTypeOrdering { // visited. template struct SupertypesFirstBase - : TopologicalSort> { + : OldTopologicalSort> { // For each type in the input collection, whether it is a supertype. Used to // track membership in the input collection. InsertOrderedMap typeSet; -- cgit v1.2.3