ArkScript
A small, fast, functional and scripting language for video games
NameResolutionPass.cpp
Go to the documentation of this file.
2
3#include <Ark/Exceptions.hpp>
4#include <Ark/Utils.hpp>
6
7namespace Ark::internal
8{
10 Pass("NameResolution", debug),
11 m_ast()
12 {
13 for (const auto& builtin : Builtins::builtins)
14 m_language_symbols.emplace(builtin.first);
15 for (auto ope : Language::operators)
16 m_language_symbols.emplace(ope);
17 for (auto inst : Language::listInstructions)
18 m_language_symbols.emplace(inst);
19
23 }
24
26 {
27 m_logger.traceStart("process");
28
29 m_ast = ast;
30 visit(m_ast, /* register_declarations= */ true);
31
33
34 m_logger.trace("AST after name resolution");
36 m_ast.debugPrint(std::cout) << '\n';
37
38 m_logger.traceStart("checkForUndefinedSymbol");
41 }
42
43 const Node& NameResolutionPass::ast() const noexcept
44 {
45 return m_ast;
46 }
47
48 std::string NameResolutionPass::addDefinedSymbol(const std::string& sym, const bool is_mutable)
49 {
50 const std::string fully_qualified_name = m_scope_resolver.registerInCurrent(sym, is_mutable);
51 m_defined_symbols.emplace(fully_qualified_name);
52 return fully_qualified_name;
53 }
54
55 void NameResolutionPass::visit(Node& node, const bool register_declarations)
56 {
57 switch (node.nodeType())
58 {
60 {
61 const std::string old_name = node.string();
63 addSymbolNode(node, old_name);
64 break;
65 }
66
67 case NodeType::Field:
68 for (auto& child : node.list())
69 {
70 const std::string old_name = child.string();
71 // in case of field, no need to check if we can fully qualify names
73 addSymbolNode(child, old_name);
74 }
75 break;
76
77 case NodeType::List:
78 if (!node.constList().empty())
79 {
80 if (node.constList()[0].nodeType() == NodeType::Keyword)
81 visitKeyword(node, node.constList()[0].keyword(), register_declarations);
82 else
83 {
84 // function calls
85 // the UpdateRef function calls kind get a special treatment, like let/mut/set,
86 // because we need to check for mutability errors
87 if (node.constList().size() > 1 && node.constList()[0].nodeType() == NodeType::Symbol &&
88 node.constList()[1].nodeType() == NodeType::Symbol && register_declarations)
89 {
90 const auto funcname = node.constList()[0].string();
91 const auto arg = node.constList()[1].string();
92
93 if (std::ranges::find(Language::UpdateRef, funcname) != Language::UpdateRef.end() && m_scope_resolver.isImmutable(arg).value_or(false))
94 throw CodeError(
95 fmt::format("MutabilityError: Can not modify the constant list `{}' using `{}'", arg, funcname),
97 node.filename(),
98 node.constList()[1].line(),
99 node.constList()[1].col(),
100 arg));
101
102 // check that we aren't doing a (append! a a) nor a (concat! a a)
103 if (funcname == Language::AppendInPlace || funcname == Language::ConcatInPlace)
104 {
105 for (std::size_t i = 2, end = node.constList().size(); i < end; ++i)
106 {
107 if (node.constList()[i].nodeType() == NodeType::Symbol && node.constList()[i].string() == arg)
108 throw CodeError(
109 fmt::format("MutabilityError: Can not {} the list `{}' to itself", funcname, arg),
111 node.filename(),
112 node.constList()[1].line(),
113 node.constList()[1].col(),
114 arg));
115 }
116 }
117 }
118
119 for (auto& child : node.list())
120 visit(child, register_declarations);
121 }
122 }
123 break;
124
126 {
127 auto& namespace_ = node.arkNamespace();
128 // no need to guard createNewNamespace with an if (register_declarations), we want to keep the namespace node
129 // (which will get ignored by the compiler, that only uses its AST), so that we can (re)construct the
130 // scopes correctly
131 m_scope_resolver.createNewNamespace(namespace_.name, namespace_.with_prefix, namespace_.is_glob, namespace_.symbols);
133
134 visit(*namespace_.ast, /* register_declarations= */ true);
135 // dual visit so that we can handle forward references
136 visit(*namespace_.ast, /* register_declarations= */ false);
137
138 // if we had specific symbols to import, check that those exist
139 if (!namespace_.symbols.empty())
140 {
141 for (const auto& sym : namespace_.symbols)
142 {
143 if (!scope->get(sym, true).has_value())
144 throw CodeError(
145 fmt::format("ImportError: Can not import symbol {} from {}, as it isn't in the package", sym, namespace_.name),
147 namespace_.ast->filename(),
148 namespace_.ast->line(),
149 namespace_.ast->col(),
150 "import"));
151 }
152 }
153
155 break;
156 }
157
158 default:
159 break;
160 }
161 }
162
163 void NameResolutionPass::visitKeyword(Node& node, const Keyword keyword, const bool register_declarations)
164 {
165 switch (keyword)
166 {
167 case Keyword::Set:
168 [[fallthrough]];
169 case Keyword::Let:
170 [[fallthrough]];
171 case Keyword::Mut:
172 // first, visit the value, then register the symbol
173 // this allows us to detect things like (let foo (fun (&foo) ()))
174 if (node.constList().size() > 2)
175 visit(node.list()[2], register_declarations);
176 if (node.constList().size() > 1 && node.constList()[1].nodeType() == NodeType::Symbol)
177 {
178 const std::string& name = node.constList()[1].string();
179 if (m_language_symbols.contains(name) && register_declarations)
180 throw CodeError(
181 fmt::format("Can not use a reserved identifier ('{}') as a {} name.", name, keyword == Keyword::Let ? "constant" : "variable"),
183 node.filename(),
184 node.constList()[1].line(),
185 node.constList()[1].col(),
186 name));
187
188 if (m_scope_resolver.isInScope(name) && keyword == Keyword::Let && register_declarations)
189 throw CodeError(
190 fmt::format("MutabilityError: Can not use 'let' to redefine variable `{}'", name),
192 node.filename(),
193 node.constList()[1].line(),
194 node.constList()[1].col(),
195 name));
196 if (keyword == Keyword::Set && m_scope_resolver.isRegistered(name))
197 {
198 if (m_scope_resolver.isImmutable(name).value_or(false) && register_declarations)
199 throw CodeError(
200 fmt::format("MutabilityError: Can not set the constant `{}' to {}", name, node.constList()[2].repr()),
202 node.filename(),
203 node.constList()[1].line(),
204 node.constList()[1].col(),
205 name));
206
208 }
209 else if (keyword != Keyword::Set)
210 {
211 // update the declared variable name to use the fully qualified name
212 // this will prevent name conflicts, and handle scope resolution
213 const std::string fully_qualified_name = addDefinedSymbol(name, keyword != Keyword::Let);
214 if (register_declarations)
215 node.list()[1].setString(fully_qualified_name);
216 }
217 }
218 break;
219
220 case Keyword::Import:
221 if (!node.constList().empty())
222 m_plugin_names.push_back(node.constList()[1].constList().back().string());
223 break;
224
225 case Keyword::While:
226 // create a new scope to track variables
228 for (auto& child : node.list())
229 visit(child, register_declarations);
230 // remove the scope once the loop has been compiled, only we were registering declarations
232 break;
233
234 case Keyword::Fun:
235 // create a new scope to track variables
237
238 if (node.constList()[1].nodeType() == NodeType::List)
239 {
240 for (auto& child : node.list()[1].list())
241 {
242 if (child.nodeType() == NodeType::Capture)
243 {
244 if (!m_scope_resolver.isRegistered(child.string()) && register_declarations)
245 throw CodeError(
246 fmt::format("Can not capture `{}' because it is referencing a variable defined in an unreachable scope.", child.string()),
248 child.filename(),
249 child.line(),
250 child.col(),
251 child.repr()));
252
253 // update the declared variable name to use the fully qualified name
254 // this will prevent name conflicts, and handle scope resolution
255 std::string fqn = updateSymbolWithFullyQualifiedName(child);
256 addDefinedSymbol(fqn, true);
257 }
258 else if (child.nodeType() == NodeType::Symbol)
259 addDefinedSymbol(child.string(), /* is_mutable= */ true);
260 }
261 }
262 if (node.constList().size() > 2)
263 visit(node.list()[2], register_declarations);
264
265 // remove the scope once the function has been compiled, only we were registering declarations
267 break;
268
269 default:
270 for (auto& child : node.list())
271 visit(child, register_declarations);
272 break;
273 }
274 }
275
276 void NameResolutionPass::addSymbolNode(const Node& symbol, const std::string& old_name)
277 {
278 const std::string& name = symbol.string();
279
280 // we don't accept builtins/operators as a user symbol
281 if (m_language_symbols.contains(name))
282 return;
283
284 // remove the old name node, to avoid false positive when looking for unbound symbols
285 if (!old_name.empty())
286 {
287 auto it = std::ranges::find_if(m_symbol_nodes, [&old_name, &symbol](const Node& sym_node) -> bool {
288 return sym_node.string() == old_name &&
289 sym_node.col() == symbol.col() &&
290 sym_node.line() == symbol.line() &&
291 sym_node.filename() == symbol.filename();
292 });
293 if (it != m_symbol_nodes.end())
294 {
295 it->setString(name);
296 return;
297 }
298 }
299
300 const auto it = std::ranges::find_if(m_symbol_nodes, [&name](const Node& sym_node) -> bool {
301 return sym_node.string() == name;
302 });
303 if (it == m_symbol_nodes.end())
304 m_symbol_nodes.push_back(symbol);
305 }
306
307 bool NameResolutionPass::mayBeFromPlugin(const std::string& name) const noexcept
308 {
309 std::string splitted = Utils::splitString(name, ':')[0];
310 const auto it = std::ranges::find_if(
311 m_plugin_names,
312 [&splitted](const std::string& plugin) -> bool {
313 return plugin == splitted;
314 });
315 return it != m_plugin_names.end();
316 }
317
319 {
320 auto [allowed, fqn] = m_scope_resolver.canFullyQualifyName(symbol.string());
321
322 if (m_language_symbols.contains(fqn) && symbol.string() != fqn)
323 {
324 throw CodeError(
325 fmt::format(
326 "Symbol `{}' was resolved to `{}', which is also a builtin name. Either the symbol or the package it's in needs to be renamed to avoid conflicting with the builtin.",
327 symbol.string(), fqn),
329 symbol.filename(),
330 symbol.line(),
331 symbol.col(),
332 symbol.repr()));
333 }
334 if (!allowed)
335 {
336 std::string message;
337 if (fqn.ends_with("#hidden"))
338 message = fmt::format(
339 R"(Unbound variable "{}". However, it exists in a namespace as "{}", did you forget to add it to the symbol list while importing?)",
340 symbol.string(),
341 fqn.substr(0, fqn.find_first_of('#')));
342 else
343 message = fmt::format(R"(Unbound variable "{}". However, it exists in a namespace as "{}", did you forget to prefix it with its namespace?)", symbol.string(), fqn);
344
345 if (m_logger.shouldTrace())
346 m_ast.debugPrint(std::cout) << '\n';
347
348 throw CodeError(
349 message,
351 symbol.filename(),
352 symbol.line(),
353 symbol.col(),
354 symbol.repr()));
355 }
356
357 symbol.setString(fqn);
358 return fqn;
359 }
360
362 {
363 for (const auto& sym : m_symbol_nodes)
364 {
365 const auto& str = sym.string();
366 const bool is_plugin = mayBeFromPlugin(str);
367
368 if (!m_defined_symbols.contains(str) && !is_plugin)
369 {
370 std::string message;
371
372 const std::string suggestion = offerSuggestion(str);
373 if (suggestion.empty())
374 message = fmt::format(R"(Unbound variable error "{}" (variable is used but not defined))", str);
375 else
376 {
377 const std::string prefix = suggestion.substr(0, suggestion.find_first_of(':'));
378 const std::string note_about_prefix = fmt::format(
379 " You either forgot to import it in the symbol list (eg `(import {} :{})') or need to fully qualify it by adding the namespace",
380 prefix,
381 str);
382 const bool add_note = suggestion.ends_with(":" + str);
383 message = fmt::format(R"(Unbound variable error "{}" (did you mean "{}"?{}))", str, suggestion, add_note ? note_about_prefix : "");
384 }
385
386 throw CodeError(message, CodeErrorContext(sym.filename(), sym.line(), sym.col(), sym.repr()));
387 }
388 }
389 }
390
391 std::string NameResolutionPass::offerSuggestion(const std::string& str) const
392 {
393 auto iterate = [](const std::string& word, const std::unordered_set<std::string>& dict) -> std::string {
394 std::string suggestion;
395 // our suggestion shouldn't require more than half the string to change
396 std::size_t suggestion_distance = word.size() / 2;
397 for (const std::string& symbol : dict)
398 {
399 const std::size_t current_distance = Utils::levenshteinDistance(word, symbol);
400 if (current_distance <= suggestion_distance)
401 {
402 suggestion_distance = current_distance;
403 suggestion = symbol;
404 }
405 }
406 return suggestion;
407 };
408
409 std::string suggestion = iterate(str, m_defined_symbols);
410 // look for a suggestion related to language builtins
411 if (suggestion.empty())
412 suggestion = iterate(str, m_language_symbols);
413 // look for a suggestion related to a namespace change
414 if (suggestion.empty())
415 {
416 if (const auto it = std::ranges::find_if(m_defined_symbols, [&str](const std::string& symbol) {
417 return symbol.ends_with(":" + str);
418 });
419 it != m_defined_symbols.end())
420 suggestion = *it;
421 }
422
423 return suggestion;
424 }
425}
Lots of utilities about string, filesystem and more.
Host the declaration of all the ArkScript builtins.
ArkScript homemade exceptions.
Resolves names and fully qualify them in the AST (prefixing them with the package they are from)
bool shouldTrace() const
Definition Logger.hpp:38
void trace(const char *fmt, Args &&... args)
Write a trace level log using fmtlib.
Definition Logger.hpp:97
void traceStart(std::string &&trace_name)
Definition Logger.hpp:74
std::vector< std::string > m_plugin_names
void visit(Node &node, bool register_declarations)
Recursively visit nodes.
void visitKeyword(Node &node, Keyword keyword, bool register_declarations)
const Node & ast() const noexcept override
Unused overload that return the input AST (untouched as this pass only generates errors)
void checkForUndefinedSymbol() const
Checks for undefined symbols, not present in the defined symbols table.
std::string offerSuggestion(const std::string &str) const
Suggest a symbol of what the user may have meant to input.
std::unordered_set< std::string > m_language_symbols
Precomputed set of language symbols that can't be used to define variables.
std::unordered_set< std::string > m_defined_symbols
bool mayBeFromPlugin(const std::string &name) const noexcept
Checking if a symbol may be coming from a plugin.
void process(const Node &ast) override
Start visiting the given AST, checking for mutability violation and unbound variables.
std::string addDefinedSymbol(const std::string &sym, bool is_mutable)
Register a symbol as defined, so that later we can throw errors on undefined symbols.
std::string updateSymbolWithFullyQualifiedName(Node &symbol)
void addSymbolNode(const Node &symbol, const std::string &old_name="")
Register a given node in the symbol table.
NameResolutionPass(unsigned debug)
Create a NameResolutionPass.
A node of an Abstract Syntax Tree for ArkScript.
Definition Node.hpp:30
NodeType nodeType() const noexcept
Return the node type.
Definition Node.cpp:77
const std::string & filename() const noexcept
Return the filename in which this node was created.
Definition Node.cpp:145
const std::string & string() const noexcept
Return the string held by the value (if the node type allows it)
Definition Node.cpp:37
const std::vector< Node > & constList() const noexcept
Return the list of sub-nodes held by the node.
Definition Node.cpp:72
Namespace & arkNamespace() noexcept
Return the namespace held by the value (if the node type allows it)
Definition Node.cpp:52
std::string repr() const noexcept
Compute a representation of the node without any comments or additional sugar, colors,...
Definition Node.cpp:160
std::ostream & debugPrint(std::ostream &os) const noexcept
Print a node to an output stream with added type annotations.
Definition Node.cpp:233
std::size_t col() const noexcept
Get the column at which this node was created.
Definition Node.cpp:140
void setString(const std::string &value) noexcept
Set the String object.
Definition Node.cpp:103
std::size_t line() const noexcept
Get the line at which this node was created.
Definition Node.cpp:135
std::vector< Node > & list() noexcept
Return the list of sub-nodes held by the node.
Definition Node.cpp:67
An interface to describe compiler passes.
Definition Pass.hpp:23
std::string registerInCurrent(const std::string &name, bool is_mutable)
Register a Declaration in the current (last) scope.
void createNewNamespace(const std::string &name, bool with_prefix, bool is_glob, const std::vector< std::string > &symbols)
Create a new namespace scope.
void saveNamespaceAndRemove()
Save the last scope as a namespace, by attaching it to the nearest namespace scope.
std::string getFullyQualifiedNameInNearestScope(const std::string &name) const
Get a FQN from a variable name in the nearest scope it is declared in.
bool isRegistered(const std::string &name) const
Checks if any scope has 'name', in reverse order.
void createNew()
Create a new scope.
StaticScope * currentScope() const
Return a non-owning raw pointer to the current scope.
bool isInScope(const std::string &name) const
Checks if 'name' is in the current scope.
void removeLastScope()
Remove the last scope.
std::optional< bool > isImmutable(const std::string &name) const
Checks the scopes in reverse order for 'name' and returns its mutability status.
std::pair< bool, std::string > canFullyQualifyName(const std::string &name)
Checks if a name can be fully qualified (allows only unprefixed names to be resolved by glob namespac...
virtual std::optional< Declaration > get(const std::string &name, bool extensive_lookup)
Try to return a Declaration from this scope with a given name.
std::vector< std::string > splitString(const std::string &source, const char sep)
Cut a string into pieces, given a character separator.
Definition Utils.hpp:31
ARK_API std::size_t levenshteinDistance(const std::string &str1, const std::string &str2)
Calculate the Levenshtein distance between two strings.
Definition Utils.cpp:5
ARK_API const std::vector< std::pair< std::string, Value > > builtins
constexpr std::array< std::string_view, 9 > listInstructions
Definition Common.hpp:115
constexpr std::string_view AppendInPlace
Definition Common.hpp:102
constexpr std::array< std::string_view, 24 > operators
Definition Common.hpp:150
constexpr std::string_view ConcatInPlace
Definition Common.hpp:103
constexpr std::string_view SysArgs
Definition Common.hpp:127
constexpr std::string_view And
Definition Common.hpp:130
constexpr std::array UpdateRef
All the builtins that modify in place a variable.
Definition Common.hpp:108
constexpr std::string_view Or
Definition Common.hpp:131
Keyword
The different keywords available.
Definition Common.hpp:75
CodeError thrown by the compiler (parser, macro processor, optimizer, and compiler itself)