Add utils/unique_vector.h from TypeDeterminer
Add tests.
Change-Id: I064fbbe2387ebe980776ee99ed2ff48d6ea5d5b5
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/41621
Commit-Queue: Ben Clayton <bclayton@google.com>
Reviewed-by: David Neto <dneto@google.com>
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 008ce14..2a9376c 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -269,6 +269,7 @@
type/vector_type.h
type/void_type.cc
type/void_type.h
+ utils/unique_vector.h
validator/validator.cc
validator/validator.h
validator/validator_impl.cc
@@ -492,6 +493,7 @@
type/type_manager_test.cc
type/u32_type_test.cc
type/vector_type_test.cc
+ utils/unique_vector_test.cc
validator/validator_builtins_test.cc
validator/validator_control_block_test.cc
validator/validator_function_test.cc
diff --git a/src/type_determiner.cc b/src/type_determiner.cc
index a72c3ab..3e0a797 100644
--- a/src/type_determiner.cc
+++ b/src/type_determiner.cc
@@ -125,9 +125,9 @@
return;
}
- current_function_->referenced_module_vars.Add(var);
+ current_function_->referenced_module_vars.add(var);
if (local) {
- current_function_->local_referenced_module_vars.Add(var);
+ current_function_->local_referenced_module_vars.add(var);
}
}
@@ -172,7 +172,7 @@
void TypeDeterminer::set_entry_points(const Symbol& fn_sym, Symbol ep_sym) {
auto* info = symbol_to_function_.at(fn_sym);
- info->ancestor_entry_points.Add(ep_sym);
+ info->ancestor_entry_points.add(ep_sym);
for (const auto& callee : caller_to_callee_[fn_sym]) {
set_entry_points(callee, ep_sym);
diff --git a/src/type_determiner.h b/src/type_determiner.h
index b03b1d5..f661c27 100644
--- a/src/type_determiner.h
+++ b/src/type_determiner.h
@@ -28,6 +28,7 @@
#include "src/scope_stack.h"
#include "src/semantic/intrinsic.h"
#include "src/type/storage_texture_type.h"
+#include "src/utils/unique_vector.h"
namespace tint {
@@ -78,26 +79,6 @@
static semantic::IntrinsicType MatchIntrinsicType(const std::string& name);
private:
- template <typename T>
- struct UniqueVector {
- using ConstIterator = typename std::vector<T>::const_iterator;
-
- void Add(const T& val) {
- if (set.count(val) == 0) {
- vector.emplace_back(val);
- set.emplace(val);
- }
- }
- size_t size() const { return vector.size(); }
- ConstIterator begin() const { return vector.begin(); }
- ConstIterator end() const { return vector.end(); }
- operator const std::vector<T> &() const { return vector; }
-
- private:
- std::vector<T> vector;
- std::unordered_set<T> set;
- };
-
/// Structure holding semantic information about a variable.
/// Used to build the semantic::Variable nodes at the end of resolving.
struct VariableInfo {
diff --git a/src/utils/unique_vector.h b/src/utils/unique_vector.h
new file mode 100644
index 0000000..36016ee
--- /dev/null
+++ b/src/utils/unique_vector.h
@@ -0,0 +1,59 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 SRC_UTILS_UNIQUE_VECTOR_H_
+#define SRC_UTILS_UNIQUE_VECTOR_H_
+
+#include <unordered_set>
+#include <vector>
+
+namespace tint {
+
+/// UniqueVector is an ordered container that only contains unique items.
+/// Attempting to add a duplicate is a no-op.
+template <typename T>
+struct UniqueVector {
+ /// The iterator returned by begin() and end()
+ using ConstIterator = typename std::vector<T>::const_iterator;
+
+ /// add appends the item to the end of the vector, if the vector does not
+ /// already contain the given item.
+ /// @param item the item to append to the end of the vector
+ void add(const T& item) {
+ if (set.count(item) == 0) {
+ vector.emplace_back(item);
+ set.emplace(item);
+ }
+ }
+
+ /// @returns the number of items in the vector
+ size_t size() const { return vector.size(); }
+
+ /// @returns an iterator to the beginning of the vector
+ ConstIterator begin() const { return vector.begin(); }
+
+ /// @returns an iterator to the end of the vector
+ ConstIterator end() const { return vector.end(); }
+
+ /// @returns a const reference to the internal vector
+ operator const std::vector<T> &() const { return vector; }
+
+ private:
+ std::vector<T> vector;
+ std::unordered_set<T> set;
+};
+
+} // namespace tint
+
+#endif // SRC_UTILS_UNIQUE_VECTOR_H_
diff --git a/src/utils/unique_vector_test.cc b/src/utils/unique_vector_test.cc
new file mode 100644
index 0000000..83f19e5
--- /dev/null
+++ b/src/utils/unique_vector_test.cc
@@ -0,0 +1,76 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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.
+
+#include "src/utils/unique_vector.h"
+
+#include "gtest/gtest.h"
+
+namespace tint {
+namespace {
+
+TEST(UniqueVectorTest, Empty) {
+ UniqueVector<int> unique_vec;
+ EXPECT_EQ(unique_vec.size(), 0u);
+ EXPECT_EQ(unique_vec.begin(), unique_vec.end());
+}
+
+TEST(UniqueVectorTest, AddUnique) {
+ UniqueVector<int> unique_vec;
+ unique_vec.add(0);
+ unique_vec.add(1);
+ unique_vec.add(2);
+ EXPECT_EQ(unique_vec.size(), 3u);
+ int i = 0;
+ for (auto n : unique_vec) {
+ EXPECT_EQ(n, i);
+ i++;
+ }
+}
+
+TEST(UniqueVectorTest, AddDuplicates) {
+ UniqueVector<int> unique_vec;
+ unique_vec.add(0);
+ unique_vec.add(0);
+ unique_vec.add(0);
+ unique_vec.add(1);
+ unique_vec.add(1);
+ unique_vec.add(2);
+ EXPECT_EQ(unique_vec.size(), 3u);
+ int i = 0;
+ for (auto n : unique_vec) {
+ EXPECT_EQ(n, i);
+ i++;
+ }
+}
+
+TEST(UniqueVectorTest, AsVector) {
+ UniqueVector<int> unique_vec;
+ unique_vec.add(0);
+ unique_vec.add(0);
+ unique_vec.add(0);
+ unique_vec.add(1);
+ unique_vec.add(1);
+ unique_vec.add(2);
+
+ const std::vector<int>& vec = unique_vec;
+ EXPECT_EQ(vec.size(), 3u);
+ int i = 0;
+ for (auto n : vec) {
+ EXPECT_EQ(n, i);
+ i++;
+ }
+}
+
+} // namespace
+} // namespace tint
