blob: 504e8ac566f07148deed650b44666f8aa5995a5e [file] [log] [blame]
Ryan Harrisondbc13af2022-02-21 15:19:07 +00001// Copyright 2021 The Tint Authors.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include "src/tint/resolver/dependency_graph.h"
16
17#include <string>
Ryan Harrisondbc13af2022-02-21 15:19:07 +000018#include <utility>
19#include <vector>
20
Ben Clayton72876c12022-06-29 10:58:41 +000021#include "src/tint/ast/alias.h"
Ben Clayton72876c12022-06-29 10:58:41 +000022#include "src/tint/ast/assignment_statement.h"
Ben Clayton72876c12022-06-29 10:58:41 +000023#include "src/tint/ast/block_statement.h"
dan sinclairb8b0c212022-10-20 22:45:50 +000024#include "src/tint/ast/break_if_statement.h"
Ben Clayton72876c12022-06-29 10:58:41 +000025#include "src/tint/ast/break_statement.h"
26#include "src/tint/ast/call_statement.h"
27#include "src/tint/ast/compound_assignment_statement.h"
Ben Clayton0ddddb02023-02-09 15:35:27 +000028#include "src/tint/ast/const.h"
Ryan Harrisondbc13af2022-02-21 15:19:07 +000029#include "src/tint/ast/continue_statement.h"
James Price098e3d82023-01-24 21:01:36 +000030#include "src/tint/ast/diagnostic_attribute.h"
Ryan Harrisondbc13af2022-02-21 15:19:07 +000031#include "src/tint/ast/discard_statement.h"
Ben Clayton72876c12022-06-29 10:58:41 +000032#include "src/tint/ast/for_loop_statement.h"
Ben Clayton72876c12022-06-29 10:58:41 +000033#include "src/tint/ast/id_attribute.h"
Ben Clayton999db742023-02-02 15:16:28 +000034#include "src/tint/ast/identifier.h"
Ben Clayton72876c12022-06-29 10:58:41 +000035#include "src/tint/ast/if_statement.h"
36#include "src/tint/ast/increment_decrement_statement.h"
37#include "src/tint/ast/internal_attribute.h"
38#include "src/tint/ast/interpolate_attribute.h"
39#include "src/tint/ast/invariant_attribute.h"
Ben Claytonc0c8abc2023-03-02 17:36:37 +000040#include "src/tint/ast/let.h"
Ben Clayton72876c12022-06-29 10:58:41 +000041#include "src/tint/ast/location_attribute.h"
42#include "src/tint/ast/loop_statement.h"
dan sinclaira79c6602023-02-21 18:49:40 +000043#include "src/tint/ast/must_use_attribute.h"
Ben Clayton0ddddb02023-02-09 15:35:27 +000044#include "src/tint/ast/override.h"
Ben Clayton72876c12022-06-29 10:58:41 +000045#include "src/tint/ast/return_statement.h"
Ben Clayton72876c12022-06-29 10:58:41 +000046#include "src/tint/ast/stage_attribute.h"
Ben Clayton72876c12022-06-29 10:58:41 +000047#include "src/tint/ast/stride_attribute.h"
48#include "src/tint/ast/struct.h"
49#include "src/tint/ast/struct_member_align_attribute.h"
50#include "src/tint/ast/struct_member_offset_attribute.h"
51#include "src/tint/ast/struct_member_size_attribute.h"
52#include "src/tint/ast/switch_statement.h"
Ben Clayton2cdf1342023-02-03 13:24:18 +000053#include "src/tint/ast/templated_identifier.h"
Ryan Harrisondbc13af2022-02-21 15:19:07 +000054#include "src/tint/ast/traverse_expressions.h"
Ben Clayton0ddddb02023-02-09 15:35:27 +000055#include "src/tint/ast/var.h"
Ben Clayton72876c12022-06-29 10:58:41 +000056#include "src/tint/ast/variable_decl_statement.h"
Ben Clayton72876c12022-06-29 10:58:41 +000057#include "src/tint/ast/while_statement.h"
58#include "src/tint/ast/workgroup_attribute.h"
dan sinclairef30aa42023-02-19 04:28:04 +000059#include "src/tint/builtin/builtin.h"
Ben Clayton4d3ff972023-02-21 17:33:54 +000060#include "src/tint/builtin/builtin_value.h"
Ryan Harrisondbc13af2022-02-21 15:19:07 +000061#include "src/tint/scope_stack.h"
62#include "src/tint/sem/builtin.h"
Ben Clayton23946b32023-03-09 16:50:19 +000063#include "src/tint/switch.h"
Ben Clayton72876c12022-06-29 10:58:41 +000064#include "src/tint/utils/block_allocator.h"
Ben Clayton884f9522023-01-12 22:52:57 +000065#include "src/tint/utils/compiler_macros.h"
Ryan Harrisondbc13af2022-02-21 15:19:07 +000066#include "src/tint/utils/defer.h"
67#include "src/tint/utils/map.h"
68#include "src/tint/utils/scoped_assignment.h"
Ben Claytonca0b9ef2023-05-26 21:20:36 +000069#include "src/tint/utils/string.h"
dan sinclairb23cda42023-02-28 17:31:54 +000070#include "src/tint/utils/string_stream.h"
Ryan Harrisondbc13af2022-02-21 15:19:07 +000071#include "src/tint/utils/unique_vector.h"
72
73#define TINT_DUMP_DEPENDENCY_GRAPH 0
74
dan sinclaird2093792022-04-07 17:45:45 +000075namespace tint::resolver {
Ryan Harrisondbc13af2022-02-21 15:19:07 +000076namespace {
77
78// Forward declaration
79struct Global;
80
81/// Dependency describes how one global depends on another global
82struct DependencyInfo {
dan sinclair41e4d9a2022-05-01 14:40:55 +000083 /// The source of the symbol that forms the dependency
84 Source source;
Ryan Harrisondbc13af2022-02-21 15:19:07 +000085};
86
87/// DependencyEdge describes the two Globals used to define a dependency
88/// relationship.
89struct DependencyEdge {
dan sinclair41e4d9a2022-05-01 14:40:55 +000090 /// The Global that depends on #to
91 const Global* from;
92 /// The Global that is depended on by #from
93 const Global* to;
Ryan Harrisondbc13af2022-02-21 15:19:07 +000094};
95
96/// DependencyEdgeCmp implements the contracts of std::equal_to<DependencyEdge>
97/// and std::hash<DependencyEdge>.
98struct DependencyEdgeCmp {
dan sinclair41e4d9a2022-05-01 14:40:55 +000099 /// Equality operator
100 bool operator()(const DependencyEdge& lhs, const DependencyEdge& rhs) const {
101 return lhs.from == rhs.from && lhs.to == rhs.to;
102 }
103 /// Hashing operator
104 inline std::size_t operator()(const DependencyEdge& d) const {
105 return utils::Hash(d.from, d.to);
106 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000107};
108
109/// A map of DependencyEdge to DependencyInfo
dan sinclair41e4d9a2022-05-01 14:40:55 +0000110using DependencyEdges =
Ben Clayton94181522022-11-09 20:55:33 +0000111 utils::Hashmap<DependencyEdge, DependencyInfo, 64, DependencyEdgeCmp, DependencyEdgeCmp>;
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000112
113/// Global describes a module-scope variable, type or function.
114struct Global {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000115 explicit Global(const ast::Node* n) : node(n) {}
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000116
dan sinclair41e4d9a2022-05-01 14:40:55 +0000117 /// The declaration ast::Node
118 const ast::Node* node;
119 /// A list of dependencies that this global depends on
Ben Clayton94181522022-11-09 20:55:33 +0000120 utils::Vector<Global*, 8> deps;
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000121};
122
123/// A map of global name to Global
Ben Clayton94181522022-11-09 20:55:33 +0000124using GlobalMap = utils::Hashmap<Symbol, Global*, 16>;
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000125
126/// Raises an ICE that a global ast::Node type was not handled by this system.
127void UnhandledNode(diag::List& diagnostics, const ast::Node* node) {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000128 TINT_ICE(Resolver, diagnostics) << "unhandled node type: " << node->TypeInfo().name;
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000129}
130
131/// Raises an error diagnostic with the given message and source.
dan sinclair41e4d9a2022-05-01 14:40:55 +0000132void AddError(diag::List& diagnostics, const std::string& msg, const Source& source) {
133 diagnostics.add_error(diag::System::Resolver, msg, source);
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000134}
135
136/// Raises a note diagnostic with the given message and source.
dan sinclair41e4d9a2022-05-01 14:40:55 +0000137void AddNote(diag::List& diagnostics, const std::string& msg, const Source& source) {
138 diagnostics.add_note(diag::System::Resolver, msg, source);
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000139}
140
141/// DependencyScanner is used to traverse a module to build the list of
142/// global-to-global dependencies.
143class DependencyScanner {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000144 public:
145 /// Constructor
dan sinclair41e4d9a2022-05-01 14:40:55 +0000146 /// @param globals_by_name map of global symbol to Global pointer
147 /// @param diagnostics diagnostic messages, appended with any errors found
148 /// @param graph the dependency graph to populate with resolved symbols
149 /// @param edges the map of globals-to-global dependency edges, which will
150 /// be populated by calls to Scan()
dan sinclaird026e132023-04-18 19:38:25 +0000151 DependencyScanner(const GlobalMap& globals_by_name,
dan sinclair41e4d9a2022-05-01 14:40:55 +0000152 diag::List& diagnostics,
153 DependencyGraph& graph,
154 DependencyEdges& edges)
dan sinclaird026e132023-04-18 19:38:25 +0000155 : globals_(globals_by_name),
dan sinclair41e4d9a2022-05-01 14:40:55 +0000156 diagnostics_(diagnostics),
157 graph_(graph),
158 dependency_edges_(edges) {
159 // Register all the globals at global-scope
160 for (auto it : globals_by_name) {
Ben Clayton94181522022-11-09 20:55:33 +0000161 scope_stack_.Set(it.key, it.value->node);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000162 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000163 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000164
dan sinclair41e4d9a2022-05-01 14:40:55 +0000165 /// Walks the global declarations, resolving symbols, and determining the
166 /// dependencies of each global.
167 void Scan(Global* global) {
168 TINT_SCOPED_ASSIGNMENT(current_global_, global);
169 Switch(
170 global->node,
171 [&](const ast::Struct* str) {
Ben Claytonb75252b2023-02-09 10:34:14 +0000172 Declare(str->name->symbol, str);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000173 for (auto* member : str->members) {
dan sinclaircb41b8f2022-09-26 15:54:55 +0000174 TraverseAttributes(member->attributes);
Ben Claytonafc53fa2023-02-22 17:15:53 +0000175 TraverseExpression(member->type);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000176 }
177 },
178 [&](const ast::Alias* alias) {
Ben Claytonb75252b2023-02-09 10:34:14 +0000179 Declare(alias->name->symbol, alias);
Ben Claytonafc53fa2023-02-22 17:15:53 +0000180 TraverseExpression(alias->type);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000181 },
182 [&](const ast::Function* func) {
Ben Claytonce31d182023-02-09 10:34:14 +0000183 Declare(func->name->symbol, func);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000184 TraverseFunction(func);
185 },
Ben Clayton79781f22023-02-18 17:13:18 +0000186 [&](const ast::Variable* v) {
187 Declare(v->name->symbol, v);
188 TraverseVariable(v);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000189 },
James Price98dc5a82023-02-04 12:20:55 +0000190 [&](const ast::DiagnosticDirective*) {
191 // Diagnostic directives do not affect the dependency graph.
James Price098e3d82023-01-24 21:01:36 +0000192 },
dan sinclair41e4d9a2022-05-01 14:40:55 +0000193 [&](const ast::Enable*) {
James Price098e3d82023-01-24 21:01:36 +0000194 // Enable directives do not affect the dependency graph.
dan sinclair41e4d9a2022-05-01 14:40:55 +0000195 },
Ben Claytonafc53fa2023-02-22 17:15:53 +0000196 [&](const ast::ConstAssert* assertion) { TraverseExpression(assertion->condition); },
dan sinclair41e4d9a2022-05-01 14:40:55 +0000197 [&](Default) { UnhandledNode(diagnostics_, global->node); });
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000198 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000199
dan sinclair41e4d9a2022-05-01 14:40:55 +0000200 private:
Ben Clayton79781f22023-02-18 17:13:18 +0000201 /// Traverses the variable, performing symbol resolution.
202 void TraverseVariable(const ast::Variable* v) {
203 if (auto* var = v->As<ast::Var>()) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000204 TraverseExpression(var->declared_address_space);
205 TraverseExpression(var->declared_access);
Ben Clayton79781f22023-02-18 17:13:18 +0000206 }
Ben Claytonafc53fa2023-02-22 17:15:53 +0000207 TraverseExpression(v->type);
Ben Clayton79781f22023-02-18 17:13:18 +0000208 TraverseAttributes(v->attributes);
Ben Claytonafc53fa2023-02-22 17:15:53 +0000209 TraverseExpression(v->initializer);
Ben Clayton79781f22023-02-18 17:13:18 +0000210 }
211
212 /// Traverses the function, performing symbol resolution and determining global dependencies.
dan sinclair41e4d9a2022-05-01 14:40:55 +0000213 void TraverseFunction(const ast::Function* func) {
Ben Claytonca98b1b2022-11-07 13:15:21 +0000214 TraverseAttributes(func->attributes);
215 TraverseAttributes(func->return_type_attributes);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000216 // Perform symbol resolution on all the parameter types before registering
217 // the parameters themselves. This allows the case of declaring a parameter
218 // with the same identifier as its type.
219 for (auto* param : func->params) {
Ben Claytonca98b1b2022-11-07 13:15:21 +0000220 TraverseAttributes(param->attributes);
Ben Claytonafc53fa2023-02-22 17:15:53 +0000221 TraverseExpression(param->type);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000222 }
223 // Resolve the return type
Ben Claytonafc53fa2023-02-22 17:15:53 +0000224 TraverseExpression(func->return_type);
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000225
dan sinclair41e4d9a2022-05-01 14:40:55 +0000226 // Push the scope stack for the parameters and function body.
227 scope_stack_.Push();
228 TINT_DEFER(scope_stack_.Pop());
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000229
dan sinclair41e4d9a2022-05-01 14:40:55 +0000230 for (auto* param : func->params) {
Ben Clayton651d9e22023-02-09 10:34:14 +0000231 if (auto* shadows = scope_stack_.Get(param->name->symbol)) {
Ben Clayton94181522022-11-09 20:55:33 +0000232 graph_.shadows.Add(param, shadows);
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000233 }
Ben Clayton651d9e22023-02-09 10:34:14 +0000234 Declare(param->name->symbol, param);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000235 }
236 if (func->body) {
237 TraverseStatements(func->body->statements);
238 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000239 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000240
dan sinclair41e4d9a2022-05-01 14:40:55 +0000241 /// Traverses the statements, performing symbol resolution and determining
242 /// global dependencies.
Ben Clayton783b1692022-08-02 17:03:35 +0000243 void TraverseStatements(utils::VectorRef<const ast::Statement*> stmts) {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000244 for (auto* s : stmts) {
245 TraverseStatement(s);
246 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000247 }
dan sinclair41e4d9a2022-05-01 14:40:55 +0000248
249 /// Traverses the statement, performing symbol resolution and determining
250 /// global dependencies.
251 void TraverseStatement(const ast::Statement* stmt) {
252 if (!stmt) {
253 return;
254 }
255 Switch(
256 stmt, //
257 [&](const ast::AssignmentStatement* a) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000258 TraverseExpression(a->lhs);
259 TraverseExpression(a->rhs);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000260 },
261 [&](const ast::BlockStatement* b) {
262 scope_stack_.Push();
263 TINT_DEFER(scope_stack_.Pop());
264 TraverseStatements(b->statements);
265 },
Ben Claytonafc53fa2023-02-22 17:15:53 +0000266 [&](const ast::BreakIfStatement* b) { TraverseExpression(b->condition); },
267 [&](const ast::CallStatement* r) { TraverseExpression(r->expr); },
dan sinclair41e4d9a2022-05-01 14:40:55 +0000268 [&](const ast::CompoundAssignmentStatement* a) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000269 TraverseExpression(a->lhs);
270 TraverseExpression(a->rhs);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000271 },
272 [&](const ast::ForLoopStatement* l) {
273 scope_stack_.Push();
274 TINT_DEFER(scope_stack_.Pop());
275 TraverseStatement(l->initializer);
Ben Claytonafc53fa2023-02-22 17:15:53 +0000276 TraverseExpression(l->condition);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000277 TraverseStatement(l->continuing);
278 TraverseStatement(l->body);
279 },
Ben Claytonafc53fa2023-02-22 17:15:53 +0000280 [&](const ast::IncrementDecrementStatement* i) { TraverseExpression(i->lhs); },
dan sinclair41e4d9a2022-05-01 14:40:55 +0000281 [&](const ast::LoopStatement* l) {
282 scope_stack_.Push();
283 TINT_DEFER(scope_stack_.Pop());
284 TraverseStatements(l->body->statements);
285 TraverseStatement(l->continuing);
286 },
287 [&](const ast::IfStatement* i) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000288 TraverseExpression(i->condition);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000289 TraverseStatement(i->body);
290 if (i->else_statement) {
291 TraverseStatement(i->else_statement);
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000292 }
dan sinclair41e4d9a2022-05-01 14:40:55 +0000293 },
Ben Claytonafc53fa2023-02-22 17:15:53 +0000294 [&](const ast::ReturnStatement* r) { TraverseExpression(r->value); },
dan sinclair41e4d9a2022-05-01 14:40:55 +0000295 [&](const ast::SwitchStatement* s) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000296 TraverseExpression(s->condition);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000297 for (auto* c : s->body) {
298 for (auto* sel : c->selectors) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000299 TraverseExpression(sel->expr);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000300 }
301 TraverseStatement(c->body);
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000302 }
dan sinclair41e4d9a2022-05-01 14:40:55 +0000303 },
304 [&](const ast::VariableDeclStatement* v) {
Ben Clayton651d9e22023-02-09 10:34:14 +0000305 if (auto* shadows = scope_stack_.Get(v->variable->name->symbol)) {
Ben Clayton94181522022-11-09 20:55:33 +0000306 graph_.shadows.Add(v->variable, shadows);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000307 }
Ben Clayton79781f22023-02-18 17:13:18 +0000308 TraverseVariable(v->variable);
Ben Clayton651d9e22023-02-09 10:34:14 +0000309 Declare(v->variable->name->symbol, v->variable);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000310 },
dan sinclair49d1a2d2022-06-16 12:01:27 +0000311 [&](const ast::WhileStatement* w) {
312 scope_stack_.Push();
313 TINT_DEFER(scope_stack_.Pop());
Ben Claytonafc53fa2023-02-22 17:15:53 +0000314 TraverseExpression(w->condition);
dan sinclair49d1a2d2022-06-16 12:01:27 +0000315 TraverseStatement(w->body);
316 },
Ben Claytonafc53fa2023-02-22 17:15:53 +0000317 [&](const ast::ConstAssert* assertion) { TraverseExpression(assertion->condition); },
dan sinclair41e4d9a2022-05-01 14:40:55 +0000318 [&](Default) {
Ben Clayton884f9522023-01-12 22:52:57 +0000319 if (TINT_UNLIKELY((!stmt->IsAnyOf<ast::BreakStatement, ast::ContinueStatement,
320 ast::DiscardStatement>()))) {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000321 UnhandledNode(diagnostics_, stmt);
322 }
323 });
324 }
325
326 /// Adds the symbol definition to the current scope, raising an error if two
327 /// symbols collide within the same scope.
328 void Declare(Symbol symbol, const ast::Node* node) {
329 auto* old = scope_stack_.Set(symbol, node);
330 if (old != nullptr && node != old) {
dan sinclaird026e132023-04-18 19:38:25 +0000331 auto name = symbol.Name();
dan sinclair41e4d9a2022-05-01 14:40:55 +0000332 AddError(diagnostics_, "redeclaration of '" + name + "'", node->source);
333 AddNote(diagnostics_, "'" + name + "' previously declared here", old->source);
334 }
335 }
336
Ben Clayton971318f2023-02-14 13:52:43 +0000337 /// Traverses the expression @p root_expr, performing symbol resolution and determining global
338 /// dependencies.
Ben Claytonafc53fa2023-02-22 17:15:53 +0000339 void TraverseExpression(const ast::Expression* root_expr) {
Ben Clayton971318f2023-02-14 13:52:43 +0000340 if (!root_expr) {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000341 return;
342 }
Ben Clayton971318f2023-02-14 13:52:43 +0000343
Ben Claytonafc53fa2023-02-22 17:15:53 +0000344 utils::Vector<const ast::Expression*, 8> pending{root_expr};
Ben Clayton1131d312023-02-10 19:24:24 +0000345 while (!pending.IsEmpty()) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000346 ast::TraverseExpressions(pending.Pop(), diagnostics_, [&](const ast::Expression* expr) {
Ben Clayton1131d312023-02-10 19:24:24 +0000347 Switch(
348 expr,
349 [&](const ast::IdentifierExpression* e) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000350 AddDependency(e->identifier, e->identifier->symbol);
Ben Clayton1131d312023-02-10 19:24:24 +0000351 if (auto* tmpl_ident = e->identifier->As<ast::TemplatedIdentifier>()) {
352 for (auto* arg : tmpl_ident->arguments) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000353 pending.Push(arg);
Ben Clayton1131d312023-02-10 19:24:24 +0000354 }
355 }
356 },
Ben Claytonafc53fa2023-02-22 17:15:53 +0000357 [&](const ast::CallExpression* call) { TraverseExpression(call->target); },
358 [&](const ast::BitcastExpression* cast) { TraverseExpression(cast->type); });
Ben Clayton1131d312023-02-10 19:24:24 +0000359 return ast::TraverseAction::Descend;
360 });
361 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000362 }
363
dan sinclair41e4d9a2022-05-01 14:40:55 +0000364 /// Traverses the attribute list, performing symbol resolution and
365 /// determining global dependencies.
Ben Clayton783b1692022-08-02 17:03:35 +0000366 void TraverseAttributes(utils::VectorRef<const ast::Attribute*> attrs) {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000367 for (auto* attr : attrs) {
368 TraverseAttribute(attr);
369 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000370 }
371
dan sinclair41e4d9a2022-05-01 14:40:55 +0000372 /// Traverses the attribute, performing symbol resolution and determining
373 /// global dependencies.
374 void TraverseAttribute(const ast::Attribute* attr) {
dan sinclair72ac53e2022-10-14 18:39:04 +0000375 bool handled = Switch(
376 attr,
377 [&](const ast::BindingAttribute* binding) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000378 TraverseExpression(binding->expr);
dan sinclair72ac53e2022-10-14 18:39:04 +0000379 return true;
380 },
Ben Clayton4d3ff972023-02-21 17:33:54 +0000381 [&](const ast::BuiltinAttribute* builtin) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000382 TraverseExpression(builtin->builtin);
Ben Clayton4d3ff972023-02-21 17:33:54 +0000383 return true;
384 },
dan sinclair72ac53e2022-10-14 18:39:04 +0000385 [&](const ast::GroupAttribute* group) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000386 TraverseExpression(group->expr);
dan sinclair72ac53e2022-10-14 18:39:04 +0000387 return true;
388 },
dan sinclair155165c2022-10-17 14:35:43 +0000389 [&](const ast::IdAttribute* id) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000390 TraverseExpression(id->expr);
dan sinclair155165c2022-10-17 14:35:43 +0000391 return true;
392 },
Ben Claytonf0b4dbb2023-02-21 21:05:28 +0000393 [&](const ast::InterpolateAttribute* interpolate) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000394 TraverseExpression(interpolate->type);
395 TraverseExpression(interpolate->sampling);
Ben Claytonf0b4dbb2023-02-21 21:05:28 +0000396 return true;
397 },
dan sinclair3fd42ae2022-10-17 15:21:48 +0000398 [&](const ast::LocationAttribute* loc) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000399 TraverseExpression(loc->expr);
dan sinclair3fd42ae2022-10-17 15:21:48 +0000400 return true;
401 },
dan sinclair72ac53e2022-10-14 18:39:04 +0000402 [&](const ast::StructMemberAlignAttribute* align) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000403 TraverseExpression(align->expr);
dan sinclair72ac53e2022-10-14 18:39:04 +0000404 return true;
405 },
406 [&](const ast::StructMemberSizeAttribute* size) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000407 TraverseExpression(size->expr);
dan sinclair72ac53e2022-10-14 18:39:04 +0000408 return true;
409 },
410 [&](const ast::WorkgroupAttribute* wg) {
Ben Claytonafc53fa2023-02-22 17:15:53 +0000411 TraverseExpression(wg->x);
412 TraverseExpression(wg->y);
413 TraverseExpression(wg->z);
dan sinclair72ac53e2022-10-14 18:39:04 +0000414 return true;
Ben Clayton63d0fab2023-03-06 15:43:16 +0000415 },
416 [&](const ast::InternalAttribute* i) {
417 for (auto* dep : i->dependencies) {
418 TraverseExpression(dep);
419 }
420 return true;
dan sinclair72ac53e2022-10-14 18:39:04 +0000421 });
422 if (handled) {
dan sinclair308c55d2022-10-14 18:27:35 +0000423 return;
424 }
dan sinclaircb41b8f2022-09-26 15:54:55 +0000425
Ben Clayton63d0fab2023-03-06 15:43:16 +0000426 if (attr->IsAnyOf<ast::BuiltinAttribute, ast::DiagnosticAttribute,
dan sinclaira79c6602023-02-21 18:49:40 +0000427 ast::InterpolateAttribute, ast::InvariantAttribute, ast::MustUseAttribute,
428 ast::StageAttribute, ast::StrideAttribute,
429 ast::StructMemberOffsetAttribute>()) {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000430 return;
431 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000432
dan sinclair41e4d9a2022-05-01 14:40:55 +0000433 UnhandledNode(diagnostics_, attr);
434 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000435
Ben Claytoncf0e9302023-02-08 15:18:43 +0000436 /// Adds the dependency from @p from to @p to, erroring if @p to cannot be resolved.
Ben Claytonafc53fa2023-02-22 17:15:53 +0000437 void AddDependency(const ast::Identifier* from, Symbol to) {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000438 auto* resolved = scope_stack_.Get(to);
439 if (!resolved) {
dan sinclair5a5b7df2023-04-21 11:54:23 +0000440 switch (to.Type()) {
441 case Symbol::BuiltinType::kNone:
442 graph_.resolved_identifiers.Add(from, UnresolvedIdentifier{to.Name()});
443 break;
444 case Symbol::BuiltinType::kFunction:
445 graph_.resolved_identifiers.Add(
446 from, ResolvedIdentifier(to.BuiltinValue<builtin::Function>()));
447 break;
448 case Symbol::BuiltinType::kBuiltin:
449 graph_.resolved_identifiers.Add(
450 from, ResolvedIdentifier(to.BuiltinValue<builtin::Builtin>()));
451 break;
452 case Symbol::BuiltinType::kBuiltinValue:
453 graph_.resolved_identifiers.Add(
454 from, ResolvedIdentifier(to.BuiltinValue<builtin::BuiltinValue>()));
455 break;
456 case Symbol::BuiltinType::kAddressSpace:
457 graph_.resolved_identifiers.Add(
458 from, ResolvedIdentifier(to.BuiltinValue<builtin::AddressSpace>()));
459 break;
460 case Symbol::BuiltinType::kTexelFormat:
461 graph_.resolved_identifiers.Add(
462 from, ResolvedIdentifier(to.BuiltinValue<builtin::TexelFormat>()));
463 break;
464 case Symbol::BuiltinType::kAccess:
465 graph_.resolved_identifiers.Add(
466 from, ResolvedIdentifier(to.BuiltinValue<builtin::Access>()));
467 break;
468 case Symbol::BuiltinType::kInterpolationType:
469 graph_.resolved_identifiers.Add(
470 from, ResolvedIdentifier(to.BuiltinValue<builtin::InterpolationType>()));
471 break;
472 case Symbol::BuiltinType::kInterpolationSampling:
473 graph_.resolved_identifiers.Add(
474 from,
475 ResolvedIdentifier(to.BuiltinValue<builtin::InterpolationSampling>()));
476 break;
dan sinclair41e4d9a2022-05-01 14:40:55 +0000477 }
Ben Claytoncf0e9302023-02-08 15:18:43 +0000478 return;
dan sinclair41e4d9a2022-05-01 14:40:55 +0000479 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000480
Ben Clayton7c6e2292022-11-23 21:04:25 +0000481 if (auto global = globals_.Find(to); global && (*global)->node == resolved) {
Ben Clayton94181522022-11-09 20:55:33 +0000482 if (dependency_edges_.Add(DependencyEdge{current_global_, *global},
Ben Claytonafc53fa2023-02-22 17:15:53 +0000483 DependencyInfo{from->source})) {
Ben Clayton94181522022-11-09 20:55:33 +0000484 current_global_->deps.Push(*global);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000485 }
486 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000487
Ben Claytoncf0e9302023-02-08 15:18:43 +0000488 graph_.resolved_identifiers.Add(from, ResolvedIdentifier(resolved));
dan sinclair41e4d9a2022-05-01 14:40:55 +0000489 }
490
Ben Clayton94181522022-11-09 20:55:33 +0000491 using VariableMap = utils::Hashmap<Symbol, const ast::Variable*, 32>;
dan sinclair41e4d9a2022-05-01 14:40:55 +0000492 const GlobalMap& globals_;
493 diag::List& diagnostics_;
494 DependencyGraph& graph_;
495 DependencyEdges& dependency_edges_;
496
James Price2cf32b12022-05-11 13:50:33 +0000497 ScopeStack<Symbol, const ast::Node*> scope_stack_;
dan sinclair41e4d9a2022-05-01 14:40:55 +0000498 Global* current_global_ = nullptr;
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000499};
500
501/// The global dependency analysis system
502struct DependencyAnalysis {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000503 public:
504 /// Constructor
dan sinclaird026e132023-04-18 19:38:25 +0000505 DependencyAnalysis(diag::List& diagnostics, DependencyGraph& graph)
506 : diagnostics_(diagnostics), graph_(graph) {}
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000507
dan sinclair41e4d9a2022-05-01 14:40:55 +0000508 /// Performs global dependency analysis on the module, emitting any errors to
509 /// #diagnostics.
510 /// @returns true if analysis found no errors, otherwise false.
511 bool Run(const ast::Module& module) {
Ben Clayton7d04ced2022-08-03 08:43:15 +0000512 // Reserve container memory
Ben Claytoncf0e9302023-02-08 15:18:43 +0000513 graph_.resolved_identifiers.Reserve(module.GlobalDeclarations().Length());
Ben Claytondce63f52022-08-17 18:07:20 +0000514 sorted_.Reserve(module.GlobalDeclarations().Length());
Ben Clayton7d04ced2022-08-03 08:43:15 +0000515
dan sinclair41e4d9a2022-05-01 14:40:55 +0000516 // Collect all the named globals from the AST module
517 GatherGlobals(module);
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000518
dan sinclair41e4d9a2022-05-01 14:40:55 +0000519 // Traverse the named globals to build the dependency graph
520 DetermineDependencies();
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000521
dan sinclair41e4d9a2022-05-01 14:40:55 +0000522 // Sort the globals into dependency order
523 SortGlobals();
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000524
dan sinclair41e4d9a2022-05-01 14:40:55 +0000525 // Dump the dependency graph if TINT_DUMP_DEPENDENCY_GRAPH is non-zero
526 DumpDependencyGraph();
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000527
Ben Claytondce63f52022-08-17 18:07:20 +0000528 graph_.ordered_globals = sorted_.Release();
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000529
dan sinclair41e4d9a2022-05-01 14:40:55 +0000530 return !diagnostics_.contains_errors();
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000531 }
532
dan sinclair41e4d9a2022-05-01 14:40:55 +0000533 private:
534 /// @param node the ast::Node of the global declaration
535 /// @returns the symbol of the global declaration node
536 /// @note will raise an ICE if the node is not a type, function or variable
537 /// declaration
538 Symbol SymbolOf(const ast::Node* node) const {
539 return Switch(
540 node, //
Ben Claytonb75252b2023-02-09 10:34:14 +0000541 [&](const ast::TypeDecl* td) { return td->name->symbol; },
Ben Claytonce31d182023-02-09 10:34:14 +0000542 [&](const ast::Function* func) { return func->name->symbol; },
Ben Clayton651d9e22023-02-09 10:34:14 +0000543 [&](const ast::Variable* var) { return var->name->symbol; },
James Price98dc5a82023-02-04 12:20:55 +0000544 [&](const ast::DiagnosticDirective*) { return Symbol(); },
Ben Clayton02791e92022-08-02 23:28:28 +0000545 [&](const ast::Enable*) { return Symbol(); },
Ben Claytonc98d57d2023-01-24 14:59:43 +0000546 [&](const ast::ConstAssert*) { return Symbol(); },
dan sinclair41e4d9a2022-05-01 14:40:55 +0000547 [&](Default) {
548 UnhandledNode(diagnostics_, node);
549 return Symbol{};
550 });
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000551 }
552
dan sinclair41e4d9a2022-05-01 14:40:55 +0000553 /// @param node the ast::Node of the global declaration
554 /// @returns the name of the global declaration node
555 /// @note will raise an ICE if the node is not a type, function or variable
556 /// declaration
dan sinclaird026e132023-04-18 19:38:25 +0000557 std::string NameOf(const ast::Node* node) const { return SymbolOf(node).Name(); }
dan sinclair41e4d9a2022-05-01 14:40:55 +0000558
559 /// @param node the ast::Node of the global declaration
560 /// @returns a string representation of the global declaration kind
561 /// @note will raise an ICE if the node is not a type, function or variable
562 /// declaration
563 std::string KindOf(const ast::Node* node) {
564 return Switch(
Ben Claytonc98d57d2023-01-24 14:59:43 +0000565 node, //
566 [&](const ast::Struct*) { return "struct"; }, //
567 [&](const ast::Alias*) { return "alias"; }, //
568 [&](const ast::Function*) { return "function"; }, //
569 [&](const ast::Variable* v) { return v->Kind(); }, //
570 [&](const ast::ConstAssert*) { return "const_assert"; }, //
dan sinclair41e4d9a2022-05-01 14:40:55 +0000571 [&](Default) {
572 UnhandledNode(diagnostics_, node);
573 return "<error>";
574 });
575 }
576
577 /// Traverses `module`, collecting all the global declarations and populating
578 /// the #globals and #declaration_order fields.
579 void GatherGlobals(const ast::Module& module) {
580 for (auto* node : module.GlobalDeclarations()) {
581 auto* global = allocator_.Create(node);
Ben Clayton02791e92022-08-02 23:28:28 +0000582 if (auto symbol = SymbolOf(node); symbol.IsValid()) {
Ben Clayton94181522022-11-09 20:55:33 +0000583 globals_.Add(symbol, global);
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000584 }
Ben Clayton94181522022-11-09 20:55:33 +0000585 declaration_order_.Push(global);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000586 }
587 }
588
589 /// Walks the global declarations, determining the dependencies of each global
590 /// and adding these to each global's Global::deps field.
591 void DetermineDependencies() {
dan sinclaird026e132023-04-18 19:38:25 +0000592 DependencyScanner scanner(globals_, diagnostics_, graph_, dependency_edges_);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000593 for (auto* global : declaration_order_) {
594 scanner.Scan(global);
595 }
596 }
597
598 /// Performs a depth-first traversal of `root`'s dependencies, calling `enter`
599 /// as the function decends into each dependency and `exit` when bubbling back
600 /// up towards the root.
601 /// @param enter is a function with the signature: `bool(Global*)`. The
602 /// `enter` function returns true if TraverseDependencies() should traverse
603 /// the dependency, otherwise it will be skipped.
604 /// @param exit is a function with the signature: `void(Global*)`. The `exit`
605 /// function is only called if the corresponding `enter` call returned true.
606 template <typename ENTER, typename EXIT>
607 void TraverseDependencies(const Global* root, ENTER&& enter, EXIT&& exit) {
608 // Entry is a single entry in the traversal stack. Entry points to a
609 // dep_idx'th dependency of Entry::global.
610 struct Entry {
611 const Global* global; // The parent global
612 size_t dep_idx; // The dependency index in `global->deps`
613 };
614
615 if (!enter(root)) {
616 return;
617 }
618
Ben Clayton94181522022-11-09 20:55:33 +0000619 utils::Vector<Entry, 16> stack{Entry{root, 0}};
dan sinclair41e4d9a2022-05-01 14:40:55 +0000620 while (true) {
Ben Clayton94181522022-11-09 20:55:33 +0000621 auto& entry = stack.Back();
dan sinclair41e4d9a2022-05-01 14:40:55 +0000622 // Have we exhausted the dependencies of entry.global?
Ben Clayton94181522022-11-09 20:55:33 +0000623 if (entry.dep_idx < entry.global->deps.Length()) {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000624 // No, there's more dependencies to traverse.
625 auto& dep = entry.global->deps[entry.dep_idx];
626 // Does the caller want to enter this dependency?
Ben Clayton94181522022-11-09 20:55:33 +0000627 if (enter(dep)) { // Yes.
628 stack.Push(Entry{dep, 0}); // Enter the dependency.
dan sinclair41e4d9a2022-05-01 14:40:55 +0000629 } else {
630 entry.dep_idx++; // No. Skip this node.
631 }
632 } else {
633 // Yes. Time to back up.
634 // Exit this global, pop the stack, and if there's another parent node,
635 // increment its dependency index, and loop again.
636 exit(entry.global);
Ben Clayton94181522022-11-09 20:55:33 +0000637 stack.Pop();
638 if (stack.IsEmpty()) {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000639 return; // All done.
640 }
Ben Clayton94181522022-11-09 20:55:33 +0000641 stack.Back().dep_idx++;
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000642 }
dan sinclair41e4d9a2022-05-01 14:40:55 +0000643 }
644 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000645
dan sinclair41e4d9a2022-05-01 14:40:55 +0000646 /// SortGlobals sorts the globals into dependency order, erroring if cyclic
647 /// dependencies are found. The sorted dependencies are assigned to #sorted.
648 void SortGlobals() {
649 if (diagnostics_.contains_errors()) {
650 return; // This code assumes there are no undeclared identifiers.
651 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000652
James Price098e3d82023-01-24 21:01:36 +0000653 // Make sure all directives go before any other global declarations.
dan sinclair41e4d9a2022-05-01 14:40:55 +0000654 for (auto* global : declaration_order_) {
James Price98dc5a82023-02-04 12:20:55 +0000655 if (global->node->IsAnyOf<ast::DiagnosticDirective, ast::Enable>()) {
James Price098e3d82023-01-24 21:01:36 +0000656 sorted_.Add(global->node);
Zhaoming Jiang418e8732022-06-16 08:30:17 +0000657 }
658 }
659
660 for (auto* global : declaration_order_) {
James Price98dc5a82023-02-04 12:20:55 +0000661 if (global->node->IsAnyOf<ast::DiagnosticDirective, ast::Enable>()) {
James Price098e3d82023-01-24 21:01:36 +0000662 // Skip directives here, as they are already added.
Zhaoming Jiang418e8732022-06-16 08:30:17 +0000663 continue;
664 }
Ben Claytondce63f52022-08-17 18:07:20 +0000665 utils::UniqueVector<const Global*, 8> stack;
dan sinclair41e4d9a2022-05-01 14:40:55 +0000666 TraverseDependencies(
667 global,
668 [&](const Global* g) { // Enter
Ben Claytondce63f52022-08-17 18:07:20 +0000669 if (!stack.Add(g)) {
670 CyclicDependencyFound(g, stack.Release());
dan sinclair41e4d9a2022-05-01 14:40:55 +0000671 return false;
672 }
Ben Claytondce63f52022-08-17 18:07:20 +0000673 if (sorted_.Contains(g->node)) {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000674 // Visited this global already.
675 // stack was pushed, but exit() will not be called when we return
676 // false, so pop here.
Ben Claytondce63f52022-08-17 18:07:20 +0000677 stack.Pop();
dan sinclair41e4d9a2022-05-01 14:40:55 +0000678 return false;
679 }
680 return true;
681 },
682 [&](const Global* g) { // Exit. Only called if Enter returned true.
Ben Claytondce63f52022-08-17 18:07:20 +0000683 sorted_.Add(g->node);
684 stack.Pop();
dan sinclair41e4d9a2022-05-01 14:40:55 +0000685 });
686
Ben Claytondce63f52022-08-17 18:07:20 +0000687 sorted_.Add(global->node);
dan sinclair41e4d9a2022-05-01 14:40:55 +0000688
Ben Clayton884f9522023-01-12 22:52:57 +0000689 if (TINT_UNLIKELY(!stack.IsEmpty())) {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000690 // Each stack.push() must have a corresponding stack.pop_back().
691 TINT_ICE(Resolver, diagnostics_)
692 << "stack not empty after returning from TraverseDependencies()";
693 }
694 }
695 }
696
697 /// DepInfoFor() looks up the global dependency information for the dependency
698 /// of global `from` depending on `to`.
699 /// @note will raise an ICE if the edge is not found.
700 DependencyInfo DepInfoFor(const Global* from, const Global* to) const {
Ben Clayton884f9522023-01-12 22:52:57 +0000701 auto info = dependency_edges_.Find(DependencyEdge{from, to});
702 if (TINT_LIKELY(info)) {
Ben Clayton94181522022-11-09 20:55:33 +0000703 return *info;
dan sinclair41e4d9a2022-05-01 14:40:55 +0000704 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000705 TINT_ICE(Resolver, diagnostics_)
dan sinclair41e4d9a2022-05-01 14:40:55 +0000706 << "failed to find dependency info for edge: '" << NameOf(from->node) << "' -> '"
707 << NameOf(to->node) << "'";
708 return {};
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000709 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000710
dan sinclair41e4d9a2022-05-01 14:40:55 +0000711 /// CyclicDependencyFound() emits an error diagnostic for a cyclic dependency.
712 /// @param root is the global that starts the cyclic dependency, which must be
713 /// found in `stack`.
714 /// @param stack is the global dependency stack that contains a loop.
Ben Claytondce63f52022-08-17 18:07:20 +0000715 void CyclicDependencyFound(const Global* root, utils::VectorRef<const Global*> stack) {
dan sinclairb23cda42023-02-28 17:31:54 +0000716 utils::StringStream msg;
dan sinclair41e4d9a2022-05-01 14:40:55 +0000717 msg << "cyclic dependency found: ";
718 constexpr size_t kLoopNotStarted = ~0u;
719 size_t loop_start = kLoopNotStarted;
Ben Claytondce63f52022-08-17 18:07:20 +0000720 for (size_t i = 0; i < stack.Length(); i++) {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000721 auto* e = stack[i];
722 if (loop_start == kLoopNotStarted && e == root) {
723 loop_start = i;
724 }
725 if (loop_start != kLoopNotStarted) {
726 msg << "'" << NameOf(e->node) << "' -> ";
727 }
728 }
729 msg << "'" << NameOf(root->node) << "'";
730 AddError(diagnostics_, msg.str(), root->node->source);
Ben Claytondce63f52022-08-17 18:07:20 +0000731 for (size_t i = loop_start; i < stack.Length(); i++) {
dan sinclair41e4d9a2022-05-01 14:40:55 +0000732 auto* from = stack[i];
Ben Claytondce63f52022-08-17 18:07:20 +0000733 auto* to = (i + 1 < stack.Length()) ? stack[i + 1] : stack[loop_start];
dan sinclair41e4d9a2022-05-01 14:40:55 +0000734 auto info = DepInfoFor(from, to);
735 AddNote(diagnostics_,
Ben Claytonafc53fa2023-02-22 17:15:53 +0000736 KindOf(from->node) + " '" + NameOf(from->node) + "' references " +
dan sinclair41e4d9a2022-05-01 14:40:55 +0000737 KindOf(to->node) + " '" + NameOf(to->node) + "' here",
738 info.source);
739 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000740 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000741
dan sinclair41e4d9a2022-05-01 14:40:55 +0000742 void DumpDependencyGraph() {
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000743#if TINT_DUMP_DEPENDENCY_GRAPH == 0
dan sinclair41e4d9a2022-05-01 14:40:55 +0000744 if ((true)) {
745 return;
746 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000747#endif // TINT_DUMP_DEPENDENCY_GRAPH
dan sinclair41e4d9a2022-05-01 14:40:55 +0000748 printf("=========================\n");
749 printf("------ declaration ------ \n");
750 for (auto* global : declaration_order_) {
751 printf("%s\n", NameOf(global->node).c_str());
752 }
753 printf("------ dependencies ------ \n");
754 for (auto* node : sorted_) {
755 auto symbol = SymbolOf(node);
Ben Clayton94181522022-11-09 20:55:33 +0000756 auto* global = *globals_.Find(symbol);
dan sinclaird026e132023-04-18 19:38:25 +0000757 printf("%s depends on:\n", symbol.Name().c_str());
dan sinclair41e4d9a2022-05-01 14:40:55 +0000758 for (auto* dep : global->deps) {
759 printf(" %s\n", NameOf(dep->node).c_str());
760 }
761 }
762 printf("=========================\n");
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000763 }
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000764
dan sinclair41e4d9a2022-05-01 14:40:55 +0000765 /// Program diagnostics
766 diag::List& diagnostics_;
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000767
dan sinclair41e4d9a2022-05-01 14:40:55 +0000768 /// The resulting dependency graph
769 DependencyGraph& graph_;
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000770
dan sinclair41e4d9a2022-05-01 14:40:55 +0000771 /// Allocator of Globals
772 utils::BlockAllocator<Global> allocator_;
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000773
dan sinclair41e4d9a2022-05-01 14:40:55 +0000774 /// Global map, keyed by name. Populated by GatherGlobals().
775 GlobalMap globals_;
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000776
Ben Claytonafc53fa2023-02-22 17:15:53 +0000777 /// Map of DependencyEdge to DependencyInfo. Populated by DetermineDependencies().
dan sinclair41e4d9a2022-05-01 14:40:55 +0000778 DependencyEdges dependency_edges_;
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000779
dan sinclair41e4d9a2022-05-01 14:40:55 +0000780 /// Globals in declaration order. Populated by GatherGlobals().
Ben Clayton94181522022-11-09 20:55:33 +0000781 utils::Vector<Global*, 64> declaration_order_;
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000782
dan sinclair41e4d9a2022-05-01 14:40:55 +0000783 /// Globals in sorted dependency order. Populated by SortGlobals().
Ben Claytondce63f52022-08-17 18:07:20 +0000784 utils::UniqueVector<const ast::Node*, 64> sorted_;
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000785};
786
787} // namespace
788
789DependencyGraph::DependencyGraph() = default;
790DependencyGraph::DependencyGraph(DependencyGraph&&) = default;
791DependencyGraph::~DependencyGraph() = default;
792
793bool DependencyGraph::Build(const ast::Module& module,
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000794 diag::List& diagnostics,
795 DependencyGraph& output) {
dan sinclaird026e132023-04-18 19:38:25 +0000796 DependencyAnalysis da{diagnostics, output};
dan sinclair41e4d9a2022-05-01 14:40:55 +0000797 return da.Run(module);
Ryan Harrisondbc13af2022-02-21 15:19:07 +0000798}
799
dan sinclaird026e132023-04-18 19:38:25 +0000800std::string ResolvedIdentifier::String(diag::List& diagnostics) const {
Ben Clayton0ddddb02023-02-09 15:35:27 +0000801 if (auto* node = Node()) {
802 return Switch(
803 node,
804 [&](const ast::TypeDecl* n) { //
dan sinclaird026e132023-04-18 19:38:25 +0000805 return "type '" + n->name->symbol.Name() + "'";
Ben Clayton0ddddb02023-02-09 15:35:27 +0000806 },
807 [&](const ast::Var* n) { //
dan sinclaird026e132023-04-18 19:38:25 +0000808 return "var '" + n->name->symbol.Name() + "'";
Ben Clayton0ddddb02023-02-09 15:35:27 +0000809 },
Ben Claytonc0c8abc2023-03-02 17:36:37 +0000810 [&](const ast::Let* n) { //
dan sinclaird026e132023-04-18 19:38:25 +0000811 return "let '" + n->name->symbol.Name() + "'";
Ben Claytonc0c8abc2023-03-02 17:36:37 +0000812 },
Ben Clayton0ddddb02023-02-09 15:35:27 +0000813 [&](const ast::Const* n) { //
dan sinclaird026e132023-04-18 19:38:25 +0000814 return "const '" + n->name->symbol.Name() + "'";
Ben Clayton0ddddb02023-02-09 15:35:27 +0000815 },
816 [&](const ast::Override* n) { //
dan sinclaird026e132023-04-18 19:38:25 +0000817 return "override '" + n->name->symbol.Name() + "'";
Ben Clayton0ddddb02023-02-09 15:35:27 +0000818 },
819 [&](const ast::Function* n) { //
dan sinclaird026e132023-04-18 19:38:25 +0000820 return "function '" + n->name->symbol.Name() + "'";
Ben Clayton0ddddb02023-02-09 15:35:27 +0000821 },
Ben Claytonfdef0332023-02-21 21:07:35 +0000822 [&](const ast::Parameter* n) { //
dan sinclaird026e132023-04-18 19:38:25 +0000823 return "parameter '" + n->name->symbol.Name() + "'";
Ben Claytonfdef0332023-02-21 21:07:35 +0000824 },
Ben Clayton0ddddb02023-02-09 15:35:27 +0000825 [&](Default) {
826 TINT_UNREACHABLE(Resolver, diagnostics)
827 << "unhandled ast::Node: " << node->TypeInfo().name;
828 return "<unknown>";
829 });
Ben Claytoncf0e9302023-02-08 15:18:43 +0000830 }
dan sinclair9543f742023-03-09 01:20:16 +0000831 if (auto builtin_fn = BuiltinFunction(); builtin_fn != builtin::Function::kNone) {
Ben Clayton0ddddb02023-02-09 15:35:27 +0000832 return "builtin function '" + utils::ToString(builtin_fn) + "'";
Ben Claytoncf0e9302023-02-08 15:18:43 +0000833 }
dan sinclairef30aa42023-02-19 04:28:04 +0000834 if (auto builtin_ty = BuiltinType(); builtin_ty != builtin::Builtin::kUndefined) {
Ben Clayton0ddddb02023-02-09 15:35:27 +0000835 return "builtin type '" + utils::ToString(builtin_ty) + "'";
Ben Claytoncf0e9302023-02-08 15:18:43 +0000836 }
Ben Clayton4d3ff972023-02-21 17:33:54 +0000837 if (auto builtin_val = BuiltinValue(); builtin_val != builtin::BuiltinValue::kUndefined) {
838 return "builtin value '" + utils::ToString(builtin_val) + "'";
839 }
dan sinclairb6cc4cb2023-02-19 04:01:29 +0000840 if (auto access = Access(); access != builtin::Access::kUndefined) {
Ben Clayton031e2f52023-02-09 15:35:27 +0000841 return "access '" + utils::ToString(access) + "'";
842 }
dan sinclair2a651632023-02-19 04:03:55 +0000843 if (auto addr = AddressSpace(); addr != builtin::AddressSpace::kUndefined) {
Ben Clayton031e2f52023-02-09 15:35:27 +0000844 return "address space '" + utils::ToString(addr) + "'";
845 }
Ben Claytonf0b4dbb2023-02-21 21:05:28 +0000846 if (auto type = InterpolationType(); type != builtin::InterpolationType::kUndefined) {
847 return "interpolation type '" + utils::ToString(type) + "'";
848 }
849 if (auto smpl = InterpolationSampling(); smpl != builtin::InterpolationSampling::kUndefined) {
850 return "interpolation sampling '" + utils::ToString(smpl) + "'";
851 }
dan sinclairba082fd2023-02-19 04:14:19 +0000852 if (auto fmt = TexelFormat(); fmt != builtin::TexelFormat::kUndefined) {
Ben Clayton031e2f52023-02-09 15:35:27 +0000853 return "texel format '" + utils::ToString(fmt) + "'";
854 }
Ben Claytonafc53fa2023-02-22 17:15:53 +0000855 if (auto* unresolved = Unresolved()) {
856 return "unresolved identifier '" + unresolved->name + "'";
857 }
858
Ben Clayton0ddddb02023-02-09 15:35:27 +0000859 TINT_UNREACHABLE(Resolver, diagnostics) << "unhandled ResolvedIdentifier";
860 return "<unknown>";
Ben Claytoncf0e9302023-02-08 15:18:43 +0000861}
862
dan sinclaird2093792022-04-07 17:45:45 +0000863} // namespace tint::resolver