Add a symbol table.
This CL adds a table which maps symbols to strings. This will allow us
to remove the use of std::string in the various AST nodes and refer to
the symbols instead.
Change-Id: I902641b3e546a2a44b3b2a39ce4f019cdcbeacc7
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/35100
Commit-Queue: dan sinclair <dsinclair@chromium.org>
Reviewed-by: Ben Clayton <bclayton@google.com>
Auto-Submit: dan sinclair <dsinclair@chromium.org>
diff --git a/BUILD.gn b/BUILD.gn
index 6e11dae..32f7177 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -411,6 +411,10 @@
"src/scope_stack.h",
"src/source.cc",
"src/source.h",
+ "src/symbol.cc",
+ "src/symbol.h",
+ "src/symbol_table.cc",
+ "src/symbol_table.h",
"src/transform/bound_array_accessors.cc",
"src/transform/bound_array_accessors.h",
"src/transform/emit_vertex_point_size.cc",
@@ -821,6 +825,8 @@
"src/inspector/inspector_test.cc",
"src/namer_test.cc",
"src/scope_stack_test.cc",
+ "src/symbol_table_test.cc",
+ "src/symbol_test.cc",
"src/transform/bound_array_accessors_test.cc",
"src/transform/emit_vertex_point_size_test.cc",
"src/transform/first_index_offset_test.cc",
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 328c203..cd7797e 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -232,6 +232,10 @@
scope_stack.h
source.cc
source.h
+ symbol.cc
+ symbol.h
+ symbol_table.cc
+ symbol_table.h
transform/emit_vertex_point_size.cc
transform/emit_vertex_point_size.h
transform/bound_array_accessors.cc
@@ -458,6 +462,8 @@
inspector/inspector_test.cc
namer_test.cc
scope_stack_test.cc
+ symbol_table_test.cc
+ symbol_test.cc
transform/emit_vertex_point_size_test.cc
transform/bound_array_accessors_test.cc
transform/first_index_offset_test.cc
diff --git a/src/ast/module.cc b/src/ast/module.cc
index 266e043..1e458c0 100644
--- a/src/ast/module.cc
+++ b/src/ast/module.cc
@@ -25,6 +25,7 @@
Module::Module() = default;
Module::Module(Module&&) = default;
+
Module& Module::operator=(Module&& rhs) = default;
Module::~Module() = default;
@@ -76,6 +77,10 @@
return false;
}
+Symbol Module::RegisterSymbol(const std::string& name) {
+ return symbol_table_.Register(name);
+}
+
bool Module::IsValid() const {
for (auto* var : global_variables_) {
if (var == nullptr || !var->IsValid()) {
diff --git a/src/ast/module.h b/src/ast/module.h
index bcd95c0..6b08b4f 100644
--- a/src/ast/module.h
+++ b/src/ast/module.h
@@ -26,6 +26,7 @@
#include "src/ast/type/alias_type.h"
#include "src/ast/type_manager.h"
#include "src/ast/variable.h"
+#include "src/symbol_table.h"
namespace tint {
namespace ast {
@@ -158,9 +159,16 @@
/// @returns all the declared nodes in the module
const std::vector<std::unique_ptr<ast::Node>>& nodes() { return ast_nodes_; }
+ /// Registers `name` as a symbol
+ /// @param name the name to register
+ /// @returns the symbol for the `name`. If `name` is already registered the
+ /// previously generated symbol will be returned.
+ Symbol RegisterSymbol(const std::string& name);
+
private:
Module(const Module&) = delete;
+ SymbolTable symbol_table_;
VariableList global_variables_;
// The constructed types are owned by the type manager
std::vector<type::Type*> constructed_types_;
diff --git a/src/symbol.cc b/src/symbol.cc
new file mode 100644
index 0000000..91efe28
--- /dev/null
+++ b/src/symbol.cc
@@ -0,0 +1,41 @@
+// Copyright 2020 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/symbol.h"
+
+namespace tint {
+
+Symbol::Symbol() = default;
+
+Symbol::Symbol(uint32_t val) : val_(val) {}
+
+Symbol::Symbol(const Symbol& o) = default;
+
+Symbol::Symbol(Symbol&& o) = default;
+
+Symbol::~Symbol() = default;
+
+Symbol& Symbol::operator=(const Symbol& o) = default;
+
+Symbol& Symbol::operator=(Symbol&& o) = default;
+
+bool Symbol::operator==(const Symbol& other) const {
+ return val_ == other.val_;
+}
+
+std::string Symbol::to_str() const {
+ return "tint_symbol_" + std::to_string(val_);
+}
+
+} // namespace tint
diff --git a/src/symbol.h b/src/symbol.h
new file mode 100644
index 0000000..c5ab39b
--- /dev/null
+++ b/src/symbol.h
@@ -0,0 +1,70 @@
+// Copyright 2020 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_SYMBOL_H_
+#define SRC_SYMBOL_H_
+
+#include <string>
+
+namespace tint {
+
+/// A symbol representing a string in the system
+class Symbol {
+ public:
+ /// Constructor
+ /// An invalid symbol
+ Symbol();
+ /// Constructor
+ /// @param val the symbol value
+ explicit Symbol(uint32_t val);
+ /// Copy constructor
+ /// @param o the symbol to copy
+ Symbol(const Symbol& o);
+ /// Move constructor
+ /// @param o the symbol to move
+ Symbol(Symbol&& o);
+ /// Destructor
+ ~Symbol();
+
+ /// Copy assignment
+ /// @param o the other symbol
+ /// @returns the symbol after doing the copy
+ Symbol& operator=(const Symbol& o);
+ /// Move assignment
+ /// @param o the other symbol
+ /// @returns teh symbol after doing the move
+ Symbol& operator=(Symbol&& o);
+
+ /// Comparison operator
+ /// @param o the other symbol
+ /// @returns true if the symbols are the same
+ bool operator==(const Symbol& o) const;
+
+ /// @returns true if the symbol is valid
+ bool IsValid() const { return val_ != static_cast<uint32_t>(-1); }
+
+ /// @returns the value for the symbol
+ uint32_t value() const { return val_; }
+
+ /// Convert the symbol to a string
+ /// @return the string representation of the symbol
+ std::string to_str() const;
+
+ private:
+ uint32_t val_ = static_cast<uint32_t>(-1);
+};
+
+} // namespace tint
+
+#endif // SRC_SYMBOL_H_
diff --git a/src/symbol_table.cc b/src/symbol_table.cc
new file mode 100644
index 0000000..13fe13f
--- /dev/null
+++ b/src/symbol_table.cc
@@ -0,0 +1,52 @@
+// Copyright 2020 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/symbol_table.h"
+
+namespace tint {
+
+SymbolTable::SymbolTable() = default;
+
+SymbolTable::SymbolTable(SymbolTable&&) = default;
+
+SymbolTable::~SymbolTable() = default;
+
+SymbolTable& SymbolTable::operator=(SymbolTable&&) = default;
+
+Symbol SymbolTable::Register(const std::string& name) {
+ if (name == "")
+ return Symbol();
+
+ auto it = name_to_symbol_.find(name);
+ if (it != name_to_symbol_.end())
+ return it->second;
+
+ Symbol sym(next_symbol_);
+ ++next_symbol_;
+
+ name_to_symbol_[name] = sym;
+ symbol_to_name_[sym.value()] = name;
+
+ return sym;
+}
+
+std::string SymbolTable::NameFor(const Symbol symbol) const {
+ auto it = symbol_to_name_.find(symbol.value());
+ if (it == symbol_to_name_.end())
+ return "";
+
+ return it->second;
+}
+
+} // namespace tint
diff --git a/src/symbol_table.h b/src/symbol_table.h
new file mode 100644
index 0000000..e3351e1
--- /dev/null
+++ b/src/symbol_table.h
@@ -0,0 +1,60 @@
+// Copyright 2020 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_SYMBOL_TABLE_H_
+#define SRC_SYMBOL_TABLE_H_
+
+#include <string>
+#include <unordered_map>
+
+#include "src/symbol.h"
+
+namespace tint {
+
+/// Holds mappings from symbols to their associated string names
+class SymbolTable {
+ public:
+ /// Constructor
+ SymbolTable();
+ /// Move Constructor
+ SymbolTable(SymbolTable&&);
+ /// Destructor
+ ~SymbolTable();
+
+ /// Move assignment
+ /// @param other the symbol table to move
+ /// @returns the symbol table
+ SymbolTable& operator=(SymbolTable&& other);
+
+ /// Registers a name into the symbol table, returning the Symbol.
+ /// @param name the name to register
+ /// @returns the symbol representing the given name
+ Symbol Register(const std::string& name);
+
+ /// Returns the name for the given symbol
+ /// @param symbol the symbol to retrieve the name for
+ /// @returns the symbol name or "" if not found
+ std::string NameFor(const Symbol symbol) const;
+
+ private:
+ // The value to be associated to the next registered symbol table entry.
+ uint32_t next_symbol_ = 1;
+
+ std::unordered_map<uint32_t, std::string> symbol_to_name_;
+ std::unordered_map<std::string, Symbol> name_to_symbol_;
+};
+
+} // namespace tint
+
+#endif // SRC_SYMBOL_TABLE_H_
diff --git a/src/symbol_table_test.cc b/src/symbol_table_test.cc
new file mode 100644
index 0000000..306127b
--- /dev/null
+++ b/src/symbol_table_test.cc
@@ -0,0 +1,54 @@
+// Copyright 2020 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/symbol_table.h"
+
+#include "gtest/gtest.h"
+
+namespace tint {
+namespace {
+
+using SymbolTableTest = testing::Test;
+
+TEST_F(SymbolTableTest, GeneratesSymbolForName) {
+ SymbolTable s;
+ EXPECT_EQ(Symbol(1), s.Register("name"));
+ EXPECT_EQ(Symbol(2), s.Register("another_name"));
+}
+
+TEST_F(SymbolTableTest, DeduplicatesNames) {
+ SymbolTable s;
+ EXPECT_EQ(Symbol(1), s.Register("name"));
+ EXPECT_EQ(Symbol(2), s.Register("another_name"));
+ EXPECT_EQ(Symbol(1), s.Register("name"));
+}
+
+TEST_F(SymbolTableTest, ReturnsNameForSymbol) {
+ SymbolTable s;
+ auto sym = s.Register("name");
+ EXPECT_EQ("name", s.NameFor(sym));
+}
+
+TEST_F(SymbolTableTest, ReturnsBlankForMissingSymbol) {
+ SymbolTable s;
+ EXPECT_EQ("", s.NameFor(Symbol(2)));
+}
+
+TEST_F(SymbolTableTest, ReturnsInvalidForBlankString) {
+ SymbolTable s;
+ EXPECT_FALSE(s.Register("").IsValid());
+}
+
+} // namespace
+} // namespace tint
diff --git a/src/symbol_test.cc b/src/symbol_test.cc
new file mode 100644
index 0000000..71c352b
--- /dev/null
+++ b/src/symbol_test.cc
@@ -0,0 +1,50 @@
+// Copyright 2020 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/symbol.h"
+
+#include "gtest/gtest.h"
+
+namespace tint {
+namespace {
+
+using SymbolTest = testing::Test;
+
+TEST_F(SymbolTest, ToStr) {
+ Symbol sym(1);
+ EXPECT_EQ("tint_symbol_1", sym.to_str());
+}
+
+TEST_F(SymbolTest, CopyAssign) {
+ Symbol sym1(1);
+ Symbol sym2;
+
+ EXPECT_FALSE(sym2.IsValid());
+ sym2 = sym1;
+ EXPECT_TRUE(sym2.IsValid());
+ EXPECT_EQ(sym2, sym1);
+}
+
+TEST_F(SymbolTest, Comparison) {
+ Symbol sym1(1);
+ Symbol sym2(2);
+ Symbol sym3(1);
+
+ EXPECT_TRUE(sym1 == sym3);
+ EXPECT_FALSE(sym1 == sym2);
+ EXPECT_FALSE(sym3 == sym2);
+}
+
+} // namespace
+} // namespace tint