resolver: Fix bug in dep graph SortGlobals()
If we encounter a global twice, the stack vector was not popped, which could trigger false cyclic-dependency errors. Because the cyclic dependency did not actually exist, later logic could break, expecting to find a global->global edge which did not exist.
Fixed: chromium:1273451
Change-Id: I9d99f1aeeaea042d9ed847a878c4717803122240
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/70980
Reviewed-by: David Neto <dneto@google.com>
Kokoro: Kokoro <noreply+kokoro@google.com>
Commit-Queue: Ben Clayton <bclayton@google.com>
diff --git a/src/resolver/dependency_graph.cc b/src/resolver/dependency_graph.cc
index 4cfb45d..947be99 100644
--- a/src/resolver/dependency_graph.cc
+++ b/src/resolver/dependency_graph.cc
@@ -305,8 +305,8 @@
auto global_it = globals_.find(ident->symbol);
if (global_it != globals_.end() &&
node == global_it->second->node) {
- ResolveGlobalDependency(ident, ident->symbol, "identifier",
- "references");
+ AddGlobalDependency(ident, ident->symbol, "identifier",
+ "references");
} else {
graph_.resolved_symbols.emplace(ident, node);
}
@@ -314,9 +314,9 @@
if (auto* call = expr->As<ast::CallExpression>()) {
if (call->target.name) {
if (!IsIntrinsic(call->target.name->symbol)) {
- ResolveGlobalDependency(call->target.name,
- call->target.name->symbol, "function",
- "calls");
+ AddGlobalDependency(call->target.name,
+ call->target.name->symbol, "function",
+ "calls");
graph_.resolved_symbols.emplace(
call,
utils::Lookup(graph_.resolved_symbols, call->target.name));
@@ -357,7 +357,7 @@
return;
}
if (auto* tn = ty->As<ast::TypeName>()) {
- ResolveGlobalDependency(tn, tn->name, "type", "references");
+ AddGlobalDependency(tn, tn->name, "type", "references");
return;
}
if (auto* vec = ty->As<ast::Vector>()) {
@@ -415,10 +415,10 @@
}
/// Adds the dependency to the currently processed global
- void ResolveGlobalDependency(const ast::Node* from,
- Symbol to,
- const char* use,
- const char* action) {
+ void AddGlobalDependency(const ast::Node* from,
+ Symbol to,
+ const char* use,
+ const char* action) {
auto global_it = globals_.find(to);
if (global_it != globals_.end()) {
auto* global = global_it->second;
@@ -482,9 +482,8 @@
// Sort the globals into dependency order
SortGlobals();
-#if TINT_DUMP_DEPENDENCY_GRAPH
+ // Dump the dependency graph if TINT_DUMP_DEPENDENCY_GRAPH is non-zero
DumpDependencyGraph();
-#endif
if (!allow_out_of_order_decls) {
// Prevent out-of-order declarations.
@@ -630,16 +629,26 @@
return false;
}
if (sorted_.contains(g->node)) {
- return false; // Visited this global already.
+ // Visited this global already.
+ // stack was pushed, but exit() will not be called when we return
+ // false, so pop here.
+ stack.pop_back();
+ return false;
}
return true;
},
- [&](const Global* g) { // Exit
+ [&](const Global* g) { // Exit. Only called if Enter returned true.
sorted_.add(g->node);
stack.pop_back();
});
sorted_.add(global->node);
+
+ if (!stack.empty()) {
+ // Each stack.push() must have a corresponding stack.pop_back().
+ TINT_ICE(Resolver, diagnostics_)
+ << "stack not empty after returning from TraverseDependencies()";
+ }
}
}
@@ -720,25 +729,28 @@
}
}
-#if TINT_DUMP_DEPENDENCY_GRAPH
void DumpDependencyGraph() {
+#if TINT_DUMP_DEPENDENCY_GRAPH == 0
+ if ((true)) {
+ return;
+ }
+#endif // TINT_DUMP_DEPENDENCY_GRAPH
printf("=========================\n");
printf("------ declaration ------ \n");
for (auto* global : declaration_order_) {
printf("%s\n", NameOf(global->node).c_str());
}
printf("------ dependencies ------ \n");
- for (auto* node : sorted) {
+ for (auto* node : sorted_) {
auto symbol = SymbolOf(node);
- auto* global = globals.at(symbol);
- printf("%s depends on:\n", symbols.NameFor(symbol).c_str());
- for (auto& dep : global->deps) {
- printf(" %s\n", NameOf(dep.global->node).c_str());
+ auto* global = globals_.at(symbol);
+ printf("%s depends on:\n", symbols_.NameFor(symbol).c_str());
+ for (auto* dep : global->deps) {
+ printf(" %s\n", NameOf(dep->node).c_str());
}
}
printf("=========================\n");
}
-#endif // TINT_DUMP_DEPENDENCY_GRAPH
/// Program symbols
const SymbolTable& symbols_;
diff --git a/src/resolver/dependency_graph_test.cc b/src/resolver/dependency_graph_test.cc
index e222b43..5fd048d 100644
--- a/src/resolver/dependency_graph_test.cc
+++ b/src/resolver/dependency_graph_test.cc
@@ -1339,6 +1339,19 @@
Build();
}
+// Reproduces an unbalanced stack push / pop bug in
+// DependencyAnalysis::SortGlobals(), found by clusterfuzz.
+// See: crbug.com/chromium/1273451
+TEST_F(ResolverDependencyGraphTraversalTest, chromium_1273451) {
+ Structure("A", {Member("a", ty.i32())});
+ Structure("B", {Member("b", ty.i32())});
+ Func("f", {Param("a", ty.type_name("A"))}, ty.type_name("B"),
+ {
+ Return(Construct(ty.type_name("B"))),
+ });
+ Build();
+}
+
} // namespace ast_traversal
} // namespace
diff --git a/src/utils/unique_vector.h b/src/utils/unique_vector.h
index 5cb754d..f64ed07 100644
--- a/src/utils/unique_vector.h
+++ b/src/utils/unique_vector.h
@@ -71,6 +71,9 @@
/// @returns the element at the index `i`
const T& operator[](size_t i) const { return vector[i]; }
+ /// @returns true if the vector is empty
+ size_t empty() const { return vector.empty(); }
+
/// @returns the number of items in the vector
size_t size() const { return vector.size(); }
diff --git a/src/utils/unique_vector_test.cc b/src/utils/unique_vector_test.cc
index fc16784..3ec78fa 100644
--- a/src/utils/unique_vector_test.cc
+++ b/src/utils/unique_vector_test.cc
@@ -24,12 +24,14 @@
TEST(UniqueVectorTest, Empty) {
UniqueVector<int> unique_vec;
EXPECT_EQ(unique_vec.size(), 0u);
+ EXPECT_EQ(unique_vec.empty(), true);
EXPECT_EQ(unique_vec.begin(), unique_vec.end());
}
TEST(UniqueVectorTest, MoveConstructor) {
UniqueVector<int> unique_vec(std::vector<int>{0, 3, 2, 1, 2});
EXPECT_EQ(unique_vec.size(), 4u);
+ EXPECT_EQ(unique_vec.empty(), false);
EXPECT_EQ(unique_vec[0], 0);
EXPECT_EQ(unique_vec[1], 3);
EXPECT_EQ(unique_vec[2], 2);
@@ -42,6 +44,7 @@
unique_vec.add(1);
unique_vec.add(2);
EXPECT_EQ(unique_vec.size(), 3u);
+ EXPECT_EQ(unique_vec.empty(), false);
int i = 0;
for (auto n : unique_vec) {
EXPECT_EQ(n, i);
@@ -65,6 +68,7 @@
unique_vec.add(1);
unique_vec.add(2);
EXPECT_EQ(unique_vec.size(), 3u);
+ EXPECT_EQ(unique_vec.empty(), false);
int i = 0;
for (auto n : unique_vec) {
EXPECT_EQ(n, i);
@@ -90,6 +94,7 @@
const std::vector<int>& vec = unique_vec;
EXPECT_EQ(vec.size(), 3u);
+ EXPECT_EQ(unique_vec.empty(), false);
int i = 0;
for (auto n : vec) {
EXPECT_EQ(n, i);
@@ -109,18 +114,30 @@
EXPECT_EQ(unique_vec.pop_back(), 1);
EXPECT_EQ(unique_vec.size(), 2u);
+ EXPECT_EQ(unique_vec.empty(), false);
EXPECT_EQ(unique_vec[0], 0);
EXPECT_EQ(unique_vec[1], 2);
EXPECT_EQ(unique_vec.pop_back(), 2);
EXPECT_EQ(unique_vec.size(), 1u);
+ EXPECT_EQ(unique_vec.empty(), false);
EXPECT_EQ(unique_vec[0], 0);
unique_vec.add(1);
EXPECT_EQ(unique_vec.size(), 2u);
+ EXPECT_EQ(unique_vec.empty(), false);
EXPECT_EQ(unique_vec[0], 0);
EXPECT_EQ(unique_vec[1], 1);
+
+ EXPECT_EQ(unique_vec.pop_back(), 1);
+ EXPECT_EQ(unique_vec.size(), 1u);
+ EXPECT_EQ(unique_vec.empty(), false);
+ EXPECT_EQ(unique_vec[0], 0);
+
+ EXPECT_EQ(unique_vec.pop_back(), 0);
+ EXPECT_EQ(unique_vec.size(), 0u);
+ EXPECT_EQ(unique_vec.empty(), true);
}
} // namespace
diff --git a/test/bug/chromium/1273451.wgsl b/test/bug/chromium/1273451.wgsl
new file mode 100644
index 0000000..2289c10
--- /dev/null
+++ b/test/bug/chromium/1273451.wgsl
@@ -0,0 +1,11 @@
+struct A {
+ a : i32;
+};
+
+struct B {
+ b : i32;
+};
+
+fn f(a : A) -> B {
+ return B();
+}
