Blender V5.3
symbol_scope.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include "symbol_scope.hh"
10#include "symbol_class.hh"
11#include "symbol_function.hh"
12#include "symbol_table.hh"
13
14namespace bsl {
15
16using namespace blender::gpu::shader::parser::ast;
17
18template<typename T, typename AstNodeT>
20 T *sym,
21 AstNodeT id,
22 const SymbolScope &scope)
23{
24 if (TemplateParamList param = id.template_params();
25 param.is_valid() && sym && sym->template_data)
26 {
27 auto [inst, _, err] = sym->template_data->lookup_inst(param, scope, table);
28 return {inst, err};
29 }
30 return {sym, std::nullopt};
31}
32
33#if 0 /* For debugging. */
34# define LOOKUP_LOG(a) cerr << a;
35#else
36# define LOOKUP_LOG(a)
37#endif
38
40 IdQualified id,
41 optional<SourceLocation> loc) const
42{
43 LOOKUP_LOG("\n")
44 SymbolFunction *func = lookup_generic<SymbolFunction>(table, id, loc.value_or(id.front()));
45 return resolve_template_instantiation(table, func, id, *this);
46}
47
48template<typename ArgOrParamList>
50 IdQualified id,
51 ArgOrParamList params,
52 const SymbolScope &arguments_scope,
53 optional<SourceLocation> loc) const
54{
55 auto [func, err] = lookup_function(table, id, loc);
56 if (func->is_error) {
57 /* Try to resolve type constructors (only for builtins for now). */
58 if (auto [cls, err_cls] = lookup_class(table, id); !cls->is_error && cls && cls->is_builtin())
59 {
60 /* Some builtin types have no constructor (e.g. `bool32_t`). */
61 if (SymbolFunction *ctor = table.root->lookup_function(cls->identifier)) {
62 return {ctor, {}};
63 }
64 }
65 return {func, err ? err : AstNodeException{id, Diag::UnknownFunction, string(id.str())}};
66 }
67
68 if (func->template_data) {
69 /* TODO(fclem): This doesn't resolve overloads of templated function. */
70 TemplateParamList template_params = id.template_params();
71 if (template_params.is_valid()) {
72 func = func->template_data->lookup_inst(template_params, arguments_scope, table)
73 .unwrap(err)
74 .first;
75 return {func, err};
76 }
77 // if (!func->template_data->is_adl_possible()) {
78 // return {table.err_func, AstNodeException{id, Diag::MissingExplicitTemplateArguments}};
79 // }
80 }
81
82 auto arg_types = SymbolFunction::to_arg_types(table, arguments_scope, params).unwrap(err);
83 /* Get exact match when querying for the declaration. */
84 func = func->lookup_overload(id, table, arg_types).unwrap(err);
85 return {func, err};
86}
87
89 IdQualified id,
90 FuncParamList params,
91 const SymbolScope &arguments_scope,
92 optional<SourceLocation> loc) const;
94 IdQualified id,
95 FuncArgList params,
96 const SymbolScope &arguments_scope,
97 optional<SourceLocation> loc) const;
98
100 IdQualified id,
101 optional<SourceLocation> loc) const
102{
103 LOOKUP_LOG("\n")
104 SymbolClass *cls = lookup_generic<SymbolClass>(table, id, loc.value_or(id.front()));
105 return resolve_template_instantiation(table, cls, id, *this);
106}
107
109 Id id,
110 Id last,
111 optional<SourceLocation> loc) const
112{
113 LOOKUP_LOG("\n")
114 SymbolClass *cls = lookup_generic_nested<SymbolClass>(table, id, last, loc.value_or(id.front()));
115 return resolve_template_instantiation(table, cls, last, *this);
116}
117
119{
120 LOOKUP_LOG("\n")
121 return lookup_generic<SymbolFunction>(table, id, id.front());
122}
123
125{
126 LOOKUP_LOG("\n")
127 return lookup_generic<SymbolClass>(table, id, id.front());
128}
129
131{
132 LOOKUP_LOG("\n")
133 return lookup_generic<SymbolVariable>(table, id, id.front());
134}
135
136std::pair<ast::FuncForwardDecl, SymbolFunction *> SymbolScope::lookup_function_forward_decl(
137 ast::FuncDecl decl) const
138{
139 /* Note: while this linear search might seem very slow, it is only concerning a handful of
140 * functions. */
141 for (const auto &fwd : function_prototypes) {
142 /* Check identifier. */
143 if (fwd.first.identifier().str() != decl.identifier().str()) {
144 continue;
145 }
146 /* Check return type. */
147 if (fwd.first.return_type().str() != decl.return_type().str()) {
148 continue;
149 }
150 /* Check arg type. */
151 FuncArg fwd_arg = fwd.first.arguments().child_first();
152 FuncArg decl_par = decl.arguments().child_first();
153 while (fwd_arg.is_valid() &&
154 /* Check type. */
155 fwd_arg.type().str() == decl_par.type().str() &&
156 /* Check reference. */
157 fwd_arg.declarator().is_reference() == decl_par.declarator().is_reference() &&
158 /* Check array. */
159 fwd_arg.declarator().is_array() == decl_par.declarator().is_array())
160 {
161 fwd_arg = fwd_arg.next();
162 decl_par = decl_par.next();
163 }
164 /* Arg count or value doesn't match. */
165 if (decl_par.is_valid() != fwd_arg.is_valid()) {
166 continue;
167 }
168 /* Match! */
169 return fwd;
170 }
171 return {};
172}
173
175{
176 const SymbolScope *scope = this;
177 while (scope->parent) {
178 scope = scope->parent;
179 }
180 return scope;
181}
182
184{
185 SymbolScope *scope = this;
186 while (scope->parent) {
187 scope = scope->parent;
188 }
189 return scope;
190}
191
192/* Helper for debug print. */
193template<typename T> const char *get_symbol_type_name()
194{
195 if constexpr (std::is_same_v<T, SymbolFunction>) {
196 return "Function";
197 }
198 else if constexpr (std::is_same_v<T, SymbolClass>) {
199 return "Class";
200 }
201 else if constexpr (std::is_same_v<T, SymbolVariable>) {
202 return "Variable";
203 }
204 else {
205 return "Unknown";
206 }
207}
208
209template<typename T>
210T *SymbolScope::lookup_generic(const SymbolTable &table,
211 IdQualified id,
212 const SourceLocation &loc) const
213{
214 assert(id.is_valid());
215
216 LOOKUP_LOG("[Lookup] Looking up " << get_symbol_type_name<T>() << " '" << id.str()
217 << "' in scope '" << identifier << "'\n")
218
219 /* Bubble up immediately if it's a global lookup. */
220 if (id.is_global() && parent) {
221 LOOKUP_LOG("[Lookup] Global lookup: Bubbling up to parent scope " << parent->identifier
222 << "\n")
223 return parent->lookup_generic<T>(table, id, poi.value_or(loc));
224 }
225
226 /* Try to match within this scope. */
227 if (auto v = lookup_generic_nested<T>(
228 table, id.namespace_start(), id.child_last(NodeType::Id), loc))
229 {
230 LOOKUP_LOG("[Lookup] Symbol found locally '" << identifier << "'.\n")
231 return v;
232 }
233
234 /* Try to resolve in class scope if this is a member function scope (contains 'this_'). */
235 if (auto it = variables.find("this_"); it != variables.end()) {
236 LOOKUP_LOG("[Lookup] Member function scope ('this_' found). Checking class scope...\n")
237 const SymbolVariable *this_var = it->second.second;
238 /* Resolve class pointer/type from `this_` symbol */
239 const SymbolClass *cls = this_var->type;
240 const SymbolScope *this_scope = static_cast<const SymbolScope *>(cls);
241 if (auto v = this_scope->lookup_generic<T>(table, id, loc); v && !v->is_error) {
242 LOOKUP_LOG("[Lookup] Symbol found in class scope '" << cls->identifier << "'.\n")
243 return v;
244 }
245 }
246
247 /* Delegate to parent scope if not found locally. */
248 if (parent) {
249 LOOKUP_LOG("[Lookup] Not found locally. Delegating to parent scope\n")
250 return parent->lookup_generic<T>(table, id, poi.value_or(loc));
251 }
252
253 /* Lookup failure at root level, try to return error symbol. */
254 LOOKUP_LOG("[Lookup] FAILED at root scope.\n")
255
256 if constexpr (is_same_v<T, SymbolFunction>) {
257 if (auto it = functions.find(SymbolTable::err_symbol); it != functions.end()) {
258 return it->second.second;
259 }
260 }
261 else if constexpr (is_same_v<T, SymbolClass>) {
262 if (auto it = classes.find(SymbolTable::err_symbol); it != classes.end()) {
263 return it->second.second;
264 }
265 }
266 else if constexpr (is_same_v<T, SymbolVariable>) {
267 if (auto it = variables.find(SymbolTable::err_symbol); it != variables.end()) {
268 return it->second.second;
269 }
270 }
271 else {
272 static_assert(false);
273 }
274 /* Couldn't find the error symbol. Catastrophic failure. */
275 assert(0);
276 return nullptr;
277}
278
279template<typename T>
280T *SymbolScope::lookup_generic_nested(const SymbolTable &table,
281 Id id,
282 Id last,
283 const SourceLocation &loc) const
284{
285 LOOKUP_LOG("[Nested] Looking up " << get_symbol_type_name<T>() << " '"
286 << id.front().buf_->substr(id.front(), last.front())
287 << "' in scope '" << identifier << "'\n")
288
289 /* Look up anonymous namespace first. */
290 if (auto it = scopes.find(""); it != scopes.end()) {
291 LOOKUP_LOG("[Nested] Looking up anonymous namespace scope\n")
292 Id next_search_id = id.id != last.id ? id.next_id() : id;
293 if (auto ret = it->second->lookup_generic_nested<T>(table, next_search_id, last, loc)) {
294 return ret;
295 }
296 }
297
298 /* Resolve target based on whether it's a namespace or the final symbol. */
299 if (id.id != last.id) {
300 /* Only classes can have template specifiers. */
301 if (TemplateParamList list = id.template_params(); list.is_valid()) {
302 LOOKUP_LOG("[Nested] Segment '" << id.str() << "' has template params. Checking classes.\n")
303 if (auto it = classes.find(string(id.str())); it != classes.end()) {
304 if (SymbolClass *cls = it->second.second->as_class(); cls && cls->template_data) {
305 if (auto [tmp, _, err] = cls->template_data->lookup_inst(list, *this, table);
306 !tmp->is_error)
307 {
308 LOOKUP_LOG("[Nested] Found template instance scope '" << tmp->identifier << "'.\n")
309 return tmp->lookup_generic_nested<T>(table, id.next_id(), last, loc);
310 }
311 }
312 }
313 LOOKUP_LOG("[Nested] Template instance lookup failed for '" << id.str() << "'.\n")
314 return nullptr;
315 }
316
317 if (auto it = scopes.find(string(id.str())); it != scopes.end()) {
318 LOOKUP_LOG("[Nested] Match sub-scope/namespace '"
319 << id.str() << "' at " << it->second->identifier << ". Descending...\n")
320 return it->second->lookup_generic_nested<T>(table, id.next_id(), last, loc);
321 }
322 LOOKUP_LOG("[Nested] Mid-segment '" << id.str() << "' could not be resolved as a scope.\n")
323 return nullptr;
324 }
325
326 if constexpr (is_same_v<T, SymbolFunction>) {
327 if (auto it = functions.find(string(id.str())); it != functions.end()) {
328 if (it->second.first <= loc) {
329 LOOKUP_LOG("[Nested] Found function match: " << it->second.second->identifier << "\n")
330 return it->second.second;
331 }
333 "[Nested] Found function, but declared AFTER current source location "
334 "(shadowed/invisible).\n")
335 }
336 }
337 else if constexpr (is_same_v<T, SymbolClass>) {
338 if (auto it = classes.find(string(id.str())); it != classes.end()) {
339 if (it->second.first <= loc) {
340 LOOKUP_LOG("[Nested] Found class match: " << it->second.second->identifier << "\n")
341 return it->second.second;
342 }
344 "[Nested] Found class, but declared AFTER current source location "
345 "(shadowed/invisible).\n")
346 }
347 }
348 else if constexpr (is_same_v<T, SymbolVariable>) {
349 if (auto it = variables.find(string(id.str())); it != variables.end()) {
350 if (it->second.first <= loc) {
351 if (TemplateParamList list = id.template_params(); list.is_valid()) {
353 "[Nested] Found variable match, but rejected: Variables cannot be templated.\n")
354 return nullptr;
355 }
356 LOOKUP_LOG("[Nested] Found variable match: " << it->second.second->identifier << "\n")
357 return it->second.second;
358 }
360 "[Nested] Found variable, but declared AFTER current source location "
361 "(shadowed/invisible).\n")
362 }
363 }
364 else {
365 static_assert(false);
366 }
367 return nullptr;
368}
369
371{
372 auto it = classes.find(id);
373 return it != classes.end() ? it->second.second : nullptr;
374}
375
377{
378 auto it = functions.find(id);
379 return it != functions.end() ? it->second.second : nullptr;
380}
381
383{
384 auto it = variables.find(id);
385 return it != variables.end() ? it->second.second : nullptr;
386}
387
389{
390 return type == CLASS ? static_cast<SymbolClass *>(this) : nullptr;
391}
392
394{
395 return type == FUNCTION ? static_cast<SymbolFunction *>(this) : nullptr;
396}
398{
399 return type == FUNCTION ? static_cast<const SymbolFunction *>(this) : nullptr;
400}
401
403{
404 SymbolScope *fn = this;
405 while (fn && fn->type != FUNCTION) {
406 fn = fn->parent;
407 }
408 return fn ? fn->as_function() : nullptr;
409}
411{
412 const SymbolScope *fn = this;
413 while (fn && fn->type != FUNCTION) {
414 fn = fn->parent;
415 }
416 return fn ? fn->as_function() : nullptr;
417}
418
420{
421 bool result = false;
422 if (auto it = functions.emplace(fn); !it.second) {
423 /* If the function is a builtin and the new overload by not a builtin, we have to discard
424 * all builtin overloads of this function. This is to emulate the GLSL and MSL overload
425 * behavior. */
426 if (it.first->is_builtin && !builtin) {
427 functions.erase(functions.find(fn->identifier));
428 functions.emplace(fn);
429 }
430 else {
431 it.first->add_overload(fn);
432 if (!builtin) {
433 /* Add suffix to the function identifier to reduce chance of hitting an overload at
434 * runtime. This way, the dead code eliminator can discard more functions. This suffix
435 * needs to be the same whatever the file include order is, as it can differ from shader to
436 * shader. We use the line index for that. It is short enough to not clutter the resulting
437 * source file. */
438 /* TODO(fclem): This is left out for compatibility with previous BSL versions. */
439 // fn->identifier += to_string(fn->loc.tok.line_number());
440 }
441 result = true;
442 }
443 }
444 /* Builtins functions aren't parsed and don't need access to the scope.
445 * Avoid bloating global namespace. */
446 if (!builtin) {
447 scopes.emplace(unique_id(), fn);
448 }
449 return result;
450}
451
453{
454 return !variables.emplace(id, var).second;
455}
456
458{
459 return !variables.emplace(var->identifier, var).second;
460}
461
463{
464 assert(this->type == CLASS);
465 vector<SymbolVariable *> members;
466 for (const auto &[k, v] : variables) {
467 members.emplace_back(v.second);
468 }
469
470 /* Sort elements to guarantee deterministic order. */
471 sort(members.begin(), members.end(), [](const SymbolVariable *a, const SymbolVariable *b) {
472 return a->loc < b->loc;
473 });
474
475 return members;
476}
477
479{
480 if (auto it = scopes.find(to_string(n)); it != scopes.end()) {
481 return it->second;
482 }
483 return nullptr;
484}
485
487{
488 enum class SymbolType { Variable, FunctionTemplate, ClassTemplate, Function, Class, Scope };
489 /* Helper lambda to handle formatting and tree indentation. */
490 auto print_line = [](const SourceLocation src_loc,
491 SymbolType type,
492 const string &identifier,
493 const SymbolClass *decl_type,
494 const string &identifier_mangled,
495 int depth,
496 const vector<bool> &is_last) {
497 string loc = src_loc;
498 if (loc.starts_with("builtin:") && identifier != "<root>") {
499 return;
500 }
501
502 /* Create indentation based on tree depth. */
503 int padding_size = max(0, 55 - int(loc.size()));
504 string padding(padding_size, ' ');
505
506 cout << loc << padding;
507
508 /* Print the tree branch lines based on depth and ancestor sibling status. */
509 for (int i = 0; i < depth - 1; ++i) {
510 if (is_last[i]) {
511 cout << " "; /* Ancestor was the last sibling, leave space. */
512 }
513 else {
514 cout << "│ "; /* Ancestor has more siblings, draw vertical line. */
515 }
516 }
517
518 /* Print the branch for the current node. */
519 if (depth > 0) {
520 if (is_last.back()) {
521 cout << "└─"; /* Last sibling. */
522 }
523 else {
524 cout << "├─"; /* Not the last sibling. */
525 }
526 }
527
528 /* Print the current node type and identifier. */
529 cout << "o ";
530 switch (type) {
531 case SymbolType::Variable:
532 cout << "Decl";
533 break;
534 case SymbolType::FunctionTemplate:
535 cout << "TmpF";
536 break;
537 case SymbolType::ClassTemplate:
538 cout << "TmpC";
539 break;
540 case SymbolType::Function:
541 cout << "Func";
542 break;
543 case SymbolType::Class:
544 cout << "Type";
545 break;
546 case SymbolType::Scope:
547 cout << "Scop";
548 break;
549 }
550 if (!identifier.empty()) {
551 cout << " " << identifier;
552 }
553 if (decl_type) {
554 cout << " : " << decl_type->identifier;
555 }
556 if (!identifier_mangled.empty()) {
557 cout << " -> " << identifier_mangled;
558 }
559 cout << "\n";
560 };
561
562 /* Print the root node. */
563 print_line(loc,
564 SymbolType::Scope,
565 this->identifier.empty() ? "<root>" : this->identifier,
566 nullptr,
567 "",
568 0,
569 {});
570
571 /* Recursive lambda to traverse all symbol branches. */
572 auto print_node = [&](auto &self, auto *node, int depth, const vector<bool> &is_last) -> void {
573 struct Child {
574 SymbolType type;
575 string sym;
576 const Symbol *resolved;
577 const SymbolClass *cls;
578 };
579
580 vector<Child> children;
581 /* Gather children based on the current node type. */
582 for (const auto &[name, var] : node->variables) {
583 children.emplace_back(
584 SymbolType::Variable, var.second->identifier, var.second, var.second->type);
585 }
586 for (const auto &[name, func] : node->functions) {
587 children.emplace_back(SymbolType::Function, func.second->identifier, func.second, nullptr);
588 }
589 for (const auto &[name, cls] : node->classes) {
590 children.emplace_back(SymbolType::Class, name, cls.second, nullptr);
591 }
592 for (const auto &[name, scope_ptr] : node->scopes) {
593 children.emplace_back(SymbolType::Scope, scope_ptr->identifier, nullptr, nullptr);
594 }
595 /* Sort elements to guarantee deterministic output (Row -> Col -> Alphabetical). */
596 sort(children.begin(), children.end(), [](const Child &a, const Child &b) {
597 return a.resolved->loc < b.resolved->loc;
598 });
599
600 /* Iterate and print the sorted children. */
601 for (size_t i = 0; i < children.size(); ++i) {
602 bool child_is_last = (i == children.size() - 1);
603
604 vector<bool> next_is_last = is_last;
605 next_is_last.push_back(child_is_last);
606
607 print_line(children[i].resolved->loc,
608 children[i].type,
609 children[i].sym,
610 children[i].cls,
611 children[i].resolved ? children[i].resolved->identifier : "",
612 depth + 1,
613 next_is_last);
614
615 if (children[i].type == SymbolType::Scope) {
616 const auto *next_node = static_cast<const SymbolScope *>(children[i].resolved);
617 /* Recurse deeper if the child acts as a container for other symbols. */
618 self(self, next_node, depth + 1, next_is_last);
619 }
620 }
621 };
622
623 print_node(print_node, this, 0, {});
624}
625
626} // namespace bsl
btScalar max
void sort(btMatrix3x3 &U, btVector3 &sigma, btMatrix3x3 &V, int t)
Helper function of 3X3 SVD for sorting singular values.
#define str(s)
#define assert(assertion)
if(state< num_states)
#define T
uint padding(uint offset, uint alignment)
ATTR_WARN_UNUSED_RESULT const BMVert * v
Definition codegen.cc:18
static Result< T * > resolve_template_instantiation(const SymbolTable &table, T *sym, AstNodeT id, const SymbolScope &scope)
const char * get_symbol_type_name()
@ Class
Definition types.hh:118
string to_string(const char *str)
Definition string.cpp:202
std::string_view str() const
Definition ast.cc:113
Represents a specific position within a source file or included sub-file.
static Result< vector< SymbolClass * > > to_arg_types(const SymbolTable &table, const SymbolScope &scope, ast::FuncParamList list)
SymbolScope * child_scope(int n)
unordered_map< string, SymbolScope * > scopes
vector< SymbolVariable * > non_static_variables_in_declaration_order() const
SymbolVariable * lookup_variable(const SymbolTable &table, ast::IdQualified id) const
enum bsl::SymbolScope::Type type
SymbolScope(ast::LocalScope decl)
vector< std::pair< ast::FuncForwardDecl, SymbolFunction * > > function_prototypes
bool function_emplace(SymbolFunction *fn, bool builtin=false)
SymbolMap< SymbolFunction > functions
optional< SourceLocation > poi
SymbolFunction * as_function()
bool variable_emplace(string id, SymbolVariable *var)
SymbolFunction * parent_function()
SymbolMap< SymbolVariable > variables
SymbolFunction * lookup_function_base(const SymbolTable &table, ast::IdQualified id) const
void print() const
SymbolMap< SymbolClass > classes
const SymbolScope * root_scope() const
Result< SymbolFunction * > lookup_function(const SymbolTable &table, ast::IdQualified id, optional< SourceLocation > loc=nullopt) const
SymbolClass * lookup_class_base(const SymbolTable &table, ast::IdQualified id) const
SymbolClass * as_class()
Result< SymbolClass * > lookup_class(const SymbolTable &table, ast::IdQualified id, optional< SourceLocation > loc=nullopt) const
std::pair< ast::FuncForwardDecl, SymbolFunction * > lookup_function_forward_decl(ast::FuncDecl decl) const
static constexpr const char * err_symbol
SymbolScope * root
SymbolScope * parent
SourceLocation loc
#define LOOKUP_LOG(a)