11629611787

Committed 01 Nov 2024 12:48PM UTC coverage: 77.319% (+0.3%) from 77.042%

Build # 11629611787

Build Type

push

github

Committed by

SuperFola

Commit Message

feat(tests): adding first test for IR generation and optimization

Run Details

5209 of 6737 relevant lines covered (77.32%)

9473.78 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

88.8

/src/arkreactor/Compiler/NameResolutionPass.cpp

#include <Ark/Compiler/NameResolutionPass.hpp>

#include <Ark/Exceptions.hpp>
#include <Ark/Utils.hpp>
#include <Ark/Builtins/Builtins.hpp>

#include <fmt/format.h>
#include <ranges>

namespace Ark::internal
{
    void ScopeResolver::Scope::add(const std::string& name, bool is_mutable)
    {
        m_vars.emplace(name, is_mutable);
    }

    std::optional<Variable> ScopeResolver::Scope::get(const std::string& name) const
    {
        if (const auto it = std::ranges::find(m_vars, name, &Variable::name); it != m_vars.end())
            return *it;
        return std::nullopt;
    }

    bool ScopeResolver::Scope::has(const std::string& name) const
    {
        return std::ranges::find(m_vars, name, &Variable::name) != m_vars.end();
    }

    ScopeResolver::ScopeResolver()
    {
        createNew();
    }

    void ScopeResolver::createNew()
    {
        m_scopes.emplace_back();
    }

    void ScopeResolver::removeLocalScope()
    {
        m_scopes.pop_back();
    }

    void ScopeResolver::registerInCurrent(const std::string& name, const bool is_mutable)
    {
        m_scopes.back().add(name, is_mutable);
    }

    std::optional<bool> ScopeResolver::isImmutable(const std::string& name) const
    {
        for (const auto& m_scope : std::ranges::reverse_view(m_scopes))
        {
            if (auto maybe = m_scope.get(name); maybe.has_value())
                return !maybe.value().is_mutable;
        }
        return std::nullopt;
    }

    bool ScopeResolver::isRegistered(const std::string& name) const
    {
        return std::ranges::any_of(
            m_scopes.rbegin(),
            m_scopes.rend(),
            [name](const Scope& scope) {
                return scope.has(name);
            });
    }

    bool ScopeResolver::isInScope(const std::string& name) const
    {
        return m_scopes.back().has(name);
    }

    NameResolutionPass::NameResolutionPass(const unsigned debug) :
        Pass("NameResolution", debug),
        m_ast()
    {
        for (const auto& builtin : Builtins::builtins)
            m_language_symbols.emplace(builtin.first);
        for (auto ope : Language::operators)
            m_language_symbols.emplace(ope);
        for (auto inst : Language::listInstructions)
            m_language_symbols.emplace(inst);

        m_language_symbols.emplace(Language::And);
        m_language_symbols.emplace(Language::Or);
        m_language_symbols.emplace(Language::SysArgs);
    }

    void NameResolutionPass::process(const Node& ast)
    {
        m_logger.traceStart("process");

        m_ast = ast;
        visit(ast);
        m_logger.traceStart("checkForUndefinedSymbol");
        checkForUndefinedSymbol();
        m_logger.traceEnd();

        m_logger.traceEnd();
    }

    const Node& NameResolutionPass::ast() const noexcept
    {
        return m_ast;
    }

    void NameResolutionPass::addDefinedSymbol(const std::string& sym, const bool is_mutable)
    {
        m_defined_symbols.emplace(sym);
        m_scope_resolver.registerInCurrent(sym, is_mutable);
    }

    void NameResolutionPass::visit(const Node& node)
    {
        switch (node.nodeType())
        {
            case NodeType::Symbol:
                addSymbolNode(node);
                break;

            case NodeType::Field:
                for (const auto& child : node.constList())
                    addSymbolNode(child);
                break;

            case NodeType::List:
                if (!node.constList().empty())
                {
                    if (node.constList()[0].nodeType() == NodeType::Keyword)
                        visitKeyword(node, node.constList()[0].keyword());
                    else
                    {
                        // function calls
                        // the UpdateRef function calls kind get a special treatment, like let/mut/set,
                        // because we need to check for mutability errors
                        if (node.constList().size() > 1 && node.constList()[0].nodeType() == NodeType::Symbol &&
                            node.constList()[1].nodeType() == NodeType::Symbol)
                        {
                            const auto funcname = node.constList()[0].string();
                            const auto arg = node.constList()[1].string();

                            if (std::ranges::find(Language::UpdateRef, funcname) != Language::UpdateRef.end() && m_scope_resolver.isImmutable(arg).value_or(false))
                                throw CodeError(
                                    fmt::format("MutabilityError: Can not modify the constant list `{}' using `{}'", arg, funcname),
                                    node.filename(),
                                    node.constList()[1].line(),
                                    node.constList()[1].col(),
                                    arg);

                            // check that we aren't doing a (append! a a) nor a (concat! a a)
                            if (funcname == Language::AppendInPlace || funcname == Language::ConcatInPlace)
                            {
                                for (std::size_t i = 2, end = node.constList().size(); i < end; ++i)
                                {
                                    if (node.constList()[i].nodeType() == NodeType::Symbol && node.constList()[i].string() == arg)
                                        throw CodeError(
                                            fmt::format("MutabilityError: Can not {} the list `{}' to itself", funcname, arg),
                                            node.filename(),
                                            node.constList()[1].line(),
                                            node.constList()[1].col(),
                                            arg);
                                }
                            }
                        }

                        for (const auto& child : node.constList())
                            visit(child);
                    }
                }
                break;

            default:
                break;
        }
    }

    void NameResolutionPass::visitKeyword(const Node& node, const Keyword keyword)
    {
        switch (keyword)
        {
            case Keyword::Set:
                [[fallthrough]];
            case Keyword::Let:
                [[fallthrough]];
            case Keyword::Mut:
                // first, visit the value, then register the symbol
                // this allows us to detect things like (let foo (fun (&foo) ()))
                if (node.constList().size() > 2)
                    visit(node.constList()[2]);
                if (node.constList().size() > 1 && node.constList()[1].nodeType() == NodeType::Symbol)
                {
                    const std::string& name = node.constList()[1].string();
                    if (m_language_symbols.contains(name))
                        throw CodeError(
                            fmt::format("Can not use a reserved identifier ('{}') as a {} name.", name, keyword == Keyword::Let ? "constant" : "variable"),
                            node.filename(),
                            node.constList()[1].line(),
                            node.constList()[1].col(),
                            name);

                    if (m_scope_resolver.isInScope(name) && keyword == Keyword::Let)
                        throw CodeError(
                            fmt::format("MutabilityError: Can not use 'let' to redefine variable `{}'", name),
                            node.filename(),
                            node.constList()[1].line(),
                            node.constList()[1].col(),
                            name);
                    else if (keyword == Keyword::Set)
                    {
                        const auto val = node.constList()[2].repr();

                        if (const auto mutability = m_scope_resolver.isImmutable(name); m_scope_resolver.isRegistered(name) &&
                            mutability.value_or(false))
                            throw CodeError(
                                fmt::format("MutabilityError: Can not set the constant `{}' to {}", name, val),
                                node.filename(),
                                node.constList()[1].line(),
                                node.constList()[1].col(),
                                name);
                    }
                    else
                        addDefinedSymbol(name, keyword != Keyword::Let);
                }
                break;

            case Keyword::Import:
                if (!node.constList().empty())
                    m_plugin_names.push_back(node.constList()[1].constList().back().string());
                break;

            case Keyword::Fun:
                // create a new scope to track variables
                m_scope_resolver.createNew();
                if (node.constList()[1].nodeType() == NodeType::List)
                {
                    for (const auto& child : node.constList()[1].constList())
                    {
                        if (child.nodeType() == NodeType::Capture)
                        {
                            // First, check that the capture is a defined symbol
                            if (!m_defined_symbols.contains(child.string()))
                            {
                                // we didn't find node in the defined symbol list, thus we can't capture node
                                throw CodeError(
                                    fmt::format("Can not capture {} because it is referencing an unbound variable.", child.string()),
                                    child.filename(),
                                    child.line(),
                                    child.col(),
                                    child.repr());
                            }
                            else if (!m_scope_resolver.isRegistered(child.string()))
                            {
                                throw CodeError(
                                    fmt::format("Can not capture {} because it is referencing a variable defined in an unreachable scope.", child.string()),
                                    child.filename(),
                                    child.line(),
                                    child.col(),
                                    child.repr());
                            }
                            addDefinedSymbol(child.string(), /* is_mutable= */ true);
                        }
                        else if (child.nodeType() == NodeType::Symbol)
                            addDefinedSymbol(child.string(), /* is_mutable= */ true);
                    }
                }
                if (node.constList().size() > 2)
                    visit(node.constList()[2]);
                m_scope_resolver.removeLocalScope();  // and remove it once the function has been compiled
                break;

            default:
                for (const auto& child : node.constList())
                    visit(child);
                break;
        }
    }

    void NameResolutionPass::addSymbolNode(const Node& symbol)
    {
        const std::string& name = symbol.string();

        // we don't accept builtins/operators as a user symbol
        if (m_language_symbols.contains(name))
            return;

        const auto it = std::ranges::find_if(m_symbol_nodes, [&name](const Node& sym_node) -> bool {
            return sym_node.string() == name;
        });
        if (it == m_symbol_nodes.end())
            m_symbol_nodes.push_back(symbol);
    }

    bool NameResolutionPass::mayBeFromPlugin(const std::string& name) const noexcept
    {
        std::string splitted = Utils::splitString(name, ':')[0];
        const auto it = std::ranges::find_if(
            m_plugin_names,
            [&splitted](const std::string& plugin) -> bool {
                return plugin == splitted;
            });
        return it != m_plugin_names.end();
    }

    void NameResolutionPass::checkForUndefinedSymbol() const
    {
        for (const auto& sym : m_symbol_nodes)
        {
            const auto& str = sym.string();
            const bool is_plugin = mayBeFromPlugin(str);

            if (!m_defined_symbols.contains(str) && !is_plugin)
            {
                std::string message;

                const std::string suggestion = offerSuggestion(str);
                if (suggestion.empty())
                    message = fmt::format(R"(Unbound variable error "{}" (variable is used but not defined))", str);
                else
                    message = fmt::format(R"(Unbound variable error "{}" (did you mean "{}"?))", str, suggestion);

                throw CodeError(message, sym.filename(), sym.line(), sym.col(), sym.repr());
            }
        }
    }

    std::string NameResolutionPass::offerSuggestion(const std::string& str) const
    {
        std::string suggestion;
        // our suggestion shouldn't require more than half the string to change
        std::size_t suggestion_distance = str.size() / 2;

        for (const std::string& symbol : m_defined_symbols)
        {
            const std::size_t current_distance = Utils::levenshteinDistance(str, symbol);
            if (current_distance <= suggestion_distance)
            {
                suggestion_distance = current_distance;
                suggestion = symbol;
            }
        }

        return suggestion;
    }
}

1	#include <Ark/Compiler/NameResolutionPass.hpp>
2
3	#include <Ark/Exceptions.hpp>
4	#include <Ark/Utils.hpp>
5	#include <Ark/Builtins/Builtins.hpp>
6
7	#include <fmt/format.h>
8	#include <ranges>
9
10	namespace Ark::internal
11	{
12	void ScopeResolver::Scope::add(const std::string& name, bool is_mutable)	505✔
13	{	505✔
14	m_vars.emplace(name, is_mutable);	505✔
15	}	505✔
16
17	std::optional<Variable> ScopeResolver::Scope::get(const std::string& name) const	106✔
18	{	106✔
19	if (const auto it = std::ranges::find(m_vars, name, &Variable::name); it != m_vars.end())	198✔
20	return *it;	92✔
21	return std::nullopt;	14✔
22	}	106✔
23
24	bool ScopeResolver::Scope::has(const std::string& name) const	557✔
25	{	557✔
26	return std::ranges::find(m_vars, name, &Variable::name) != m_vars.end();	557✔
27	}
28
29	ScopeResolver::ScopeResolver()	100✔
30	{	100✔
31	createNew();	100✔
32	}	100✔
33
34	void ScopeResolver::createNew()	215✔
35	{	215✔
36	m_scopes.emplace_back();	215✔
37	}	215✔
38
39	void ScopeResolver::removeLocalScope()	113✔
40	{	113✔
41	m_scopes.pop_back();	113✔
42	}	113✔
43
44	void ScopeResolver::registerInCurrent(const std::string& name, const bool is_mutable)	505✔
45	{	505✔
46	m_scopes.back().add(name, is_mutable);	505✔
47	}	505✔
48
49	std::optional<bool> ScopeResolver::isImmutable(const std::string& name) const	94✔
50	{	94✔
51	for (const auto& m_scope : std::ranges::reverse_view(m_scopes))	200✔
52	{
53	if (auto maybe = m_scope.get(name); maybe.has_value())	198✔
54	return !maybe.value().is_mutable;	92✔
55	}	106✔
56	return std::nullopt;	2✔
57	}	94✔
58
59	bool ScopeResolver::isRegistered(const std::string& name) const	119✔
60	{	119✔
61	return std::ranges::any_of(	119✔
62	m_scopes.rbegin(),	119✔
63	m_scopes.rend(),	119✔
64	[name](const Scope& scope) {	403✔
65	return scope.has(name);	165✔
66	});
67	}	×
68
69	bool ScopeResolver::isInScope(const std::string& name) const	392✔
70	{	392✔
71	return m_scopes.back().has(name);	392✔
72	}
73
74	NameResolutionPass::NameResolutionPass(const unsigned debug) :	200✔
75	Pass("NameResolution", debug),	100✔
76	m_ast()	100✔
77	{	200✔
78	for (const auto& builtin : Builtins::builtins)	5,600✔
79	m_language_symbols.emplace(builtin.first);	5,500✔
80	for (auto ope : Language::operators)	2,400✔
81	m_language_symbols.emplace(ope);	2,300✔
82	for (auto inst : Language::listInstructions)	800✔
83	m_language_symbols.emplace(inst);	700✔
84
85	m_language_symbols.emplace(Language::And);	100✔
86	m_language_symbols.emplace(Language::Or);	100✔
87	m_language_symbols.emplace(Language::SysArgs);	100✔
88	}	100✔
89
90	void NameResolutionPass::process(const Node& ast)	40✔
91	{	40✔
92	m_logger.traceStart("process");	40✔
93
94	m_ast = ast;	40✔
95	visit(ast);	40✔
96	m_logger.traceStart("checkForUndefinedSymbol");	40✔
97	checkForUndefinedSymbol();	40✔
98	m_logger.traceEnd();	40✔
99
100	m_logger.traceEnd();	40✔
101	}	40✔
102
103	const Node& NameResolutionPass::ast() const noexcept	×
104	{	×
105	return m_ast;	×
106	}
107
108	void NameResolutionPass::addDefinedSymbol(const std::string& sym, const bool is_mutable)	505✔
109	{	505✔
110	m_defined_symbols.emplace(sym);	505✔
111	m_scope_resolver.registerInCurrent(sym, is_mutable);	505✔
112	}	505✔
113
114	void NameResolutionPass::visit(const Node& node)	9,066✔
115	{	9,066✔
116	switch (node.nodeType())	9,066✔
117	{	3,032✔
118	case NodeType::Symbol:
119	addSymbolNode(node);	3,032✔
120	break;	3,246✔
121
122	case NodeType::Field:
123	for (const auto& child : node.constList())	647✔
124	addSymbolNode(child);	433✔
125	break;	3,509✔
126
127	case NodeType::List:
128	if (!node.constList().empty())	3,295✔
129	{
130	if (node.constList()[0].nodeType() == NodeType::Keyword)	3,276✔
131	visitKeyword(node, node.constList()[0].keyword());	1,064✔
132	else
133	{
134	// function calls
135	// the UpdateRef function calls kind get a special treatment, like let/mut/set,
136	// because we need to check for mutability errors
137	if (node.constList().size() > 1 && node.constList()[0].nodeType() == NodeType::Symbol &&	3,704✔
138	node.constList()[1].nodeType() == NodeType::Symbol)	1,492✔
139	{
140	const auto funcname = node.constList()[0].string();	558✔
141	const auto arg = node.constList()[1].string();	558✔
142
143	if (std::ranges::find(Language::UpdateRef, funcname) != Language::UpdateRef.end() && m_scope_resolver.isImmutable(arg).value_or(false))	558✔
144	throw CodeError(	6✔
145	fmt::format("MutabilityError: Can not modify the constant list `{}' using `{}'", arg, funcname),	3✔
146	node.filename(),	3✔
147	node.constList()[1].line(),	3✔
148	node.constList()[1].col(),	3✔
149	arg);	3✔
150
151	// check that we aren't doing a (append! a a) nor a (concat! a a)
152	if (funcname == Language::AppendInPlace \|\| funcname == Language::ConcatInPlace)	555✔
153	{
154	for (std::size_t i = 2, end = node.constList().size(); i < end; ++i)	12✔
155	{
156	if (node.constList()[i].nodeType() == NodeType::Symbol && node.constList()[i].string() == arg)	6✔
157	throw CodeError(	4✔
158	fmt::format("MutabilityError: Can not {} the list `{}' to itself", funcname, arg),	2✔
159	node.filename(),	2✔
160	node.constList()[1].line(),	2✔
161	node.constList()[1].col(),	2✔
162	arg);	2✔
163	}	4✔
164	}	4✔
165	}	558✔
166
167	for (const auto& child : node.constList())	8,222✔
168	visit(child);	6,015✔
169	}
170	}	3,271✔
171	break;	5,815✔
172
173	default:
174	break;	2,525✔
175	}	9,023✔
176	}	9,028✔
177
178	void NameResolutionPass::visitKeyword(const Node& node, const Keyword keyword)	1,064✔
179	{	1,064✔
180	switch (keyword)	1,064✔
181	{	396✔
182	case Keyword::Set:
183	[[fallthrough]];
184	case Keyword::Let:
185	[[fallthrough]];
186	case Keyword::Mut:
187	// first, visit the value, then register the symbol
188	// this allows us to detect things like (let foo (fun (&foo) ()))
189	if (node.constList().size() > 2)	396✔
190	visit(node.constList()[2]);	395✔
191	if (node.constList().size() > 1 && node.constList()[1].nodeType() == NodeType::Symbol)	396✔
192	{
193	const std::string& name = node.constList()[1].string();	394✔
194	if (m_language_symbols.contains(name))	394✔
195	throw CodeError(	4✔
196	fmt::format("Can not use a reserved identifier ('{}') as a {} name.", name, keyword == Keyword::Let ? "constant" : "variable"),	2✔
197	node.filename(),	2✔
198	node.constList()[1].line(),	2✔
199	node.constList()[1].col(),	2✔
200	name);	2✔
201
202	if (m_scope_resolver.isInScope(name) && keyword == Keyword::Let)	392✔
203	throw CodeError(	2✔
204	fmt::format("MutabilityError: Can not use 'let' to redefine variable `{}'", name),	1✔
205	node.filename(),	1✔
206	node.constList()[1].line(),	1✔
207	node.constList()[1].col(),	1✔
208	name);	1✔
209	else if (keyword == Keyword::Set)	391✔
210	{
211	const auto val = node.constList()[2].repr();	82✔
212
213	if (const auto mutability = m_scope_resolver.isImmutable(name); m_scope_resolver.isRegistered(name) &&	82✔
214	mutability.value_or(false))	162✔
215	throw CodeError(	2✔
216	fmt::format("MutabilityError: Can not set the constant `{}' to {}", name, val),	1✔
217	node.filename(),	1✔
218	node.constList()[1].line(),	1✔
219	node.constList()[1].col(),	1✔
220	name);	1✔
221	}	82✔
222	else
223	addDefinedSymbol(name, keyword != Keyword::Let);	309✔
224	}	396✔
225	break;	392✔
226
227	case Keyword::Import:
228	if (!node.constList().empty())	×
229	m_plugin_names.push_back(node.constList()[1].constList().back().string());	×
230	break;	115✔
231
232	case Keyword::Fun:
233	// create a new scope to track variables
234	m_scope_resolver.createNew();	115✔
235	if (node.constList()[1].nodeType() == NodeType::List)	115✔
236	{
237	for (const auto& child : node.constList()[1].constList())	308✔
238	{
239	if (child.nodeType() == NodeType::Capture)	194✔
240	{
241	// First, check that the capture is a defined symbol
242	if (!m_defined_symbols.contains(child.string()))	38✔
243	{
244	// we didn't find node in the defined symbol list, thus we can't capture node
245	throw CodeError(	2✔
246	fmt::format("Can not capture {} because it is referencing an unbound variable.", child.string()),	1✔
247	child.filename(),	1✔
248	child.line(),	1✔
249	child.col(),	1✔
250	child.repr());	1✔
251	}
252	else if (!m_scope_resolver.isRegistered(child.string()))	37✔
253	{
254	throw CodeError(	2✔
255	fmt::format("Can not capture {} because it is referencing a variable defined in an unreachable scope.", child.string()),	1✔
256	child.filename(),	1✔
257	child.line(),	1✔
258	child.col(),	1✔
259	child.repr());	1✔
260	}
261	addDefinedSymbol(child.string(), /* is_mutable= */ true);	36✔
262	}	36✔
263	else if (child.nodeType() == NodeType::Symbol)	156✔
264	addDefinedSymbol(child.string(), /* is_mutable= */ true);	156✔
265	}	194✔
266	}	112✔
267	if (node.constList().size() > 2)	113✔
268	visit(node.constList()[2]);	112✔
269	m_scope_resolver.removeLocalScope(); // and remove it once the function has been compiled	113✔
270	break;	666✔
271
272	default:
273	for (const auto& child : node.constList())	3,027✔
274	visit(child);	2,474✔
275	break;	553✔
276	}	1,058✔
277	}	1,064✔
278
279	void NameResolutionPass::addSymbolNode(const Node& symbol)	3,465✔
280	{	3,465✔
281	const std::string& name = symbol.string();	3,465✔
282
283	// we don't accept builtins/operators as a user symbol
284	if (m_language_symbols.contains(name))	3,465✔
285	return;	1,735✔
286
287	const auto it = std::ranges::find_if(m_symbol_nodes, [&name](const Node& sym_node) -> bool {	110,274✔
288	return sym_node.string() == name;	108,544✔
289	});
290	if (it == m_symbol_nodes.end())	1,730✔
291	m_symbol_nodes.push_back(symbol);	220✔
292	}	3,465✔
293
294	bool NameResolutionPass::mayBeFromPlugin(const std::string& name) const noexcept	220✔
295	{	220✔
296	std::string splitted = Utils::splitString(name, ':')[0];	220✔
297	const auto it = std::ranges::find_if(	220✔
298	m_plugin_names,	220✔
299	[&splitted](const std::string& plugin) -> bool {	220✔
300	return plugin == splitted;	×
301	});
302	return it != m_plugin_names.end();	220✔
303	}	220✔
304
305	void NameResolutionPass::checkForUndefinedSymbol() const	40✔
306	{	40✔
307	for (const auto& sym : m_symbol_nodes)	260✔
308	{
309	const auto& str = sym.string();	220✔
310	const bool is_plugin = mayBeFromPlugin(str);	220✔
311
312	if (!m_defined_symbols.contains(str) && !is_plugin)	220✔
313	{
314	std::string message;	×
315
316	const std::string suggestion = offerSuggestion(str);	×
317	if (suggestion.empty())	×
318	message = fmt::format(R"(Unbound variable error "{}" (variable is used but not defined))", str);	×
319	else
320	message = fmt::format(R"(Unbound variable error "{}" (did you mean "{}"?))", str, suggestion);	×
321
322	throw CodeError(message, sym.filename(), sym.line(), sym.col(), sym.repr());	×
323	}	×
324	}	220✔
325	}	40✔
326
327	std::string NameResolutionPass::offerSuggestion(const std::string& str) const	×
328	{	×
329	std::string suggestion;	×
330	// our suggestion shouldn't require more than half the string to change
331	std::size_t suggestion_distance = str.size() / 2;	×
332
333	for (const std::string& symbol : m_defined_symbols)	×
334	{
335	const std::size_t current_distance = Utils::levenshteinDistance(str, symbol);	×
336	if (current_distance <= suggestion_distance)	×
337	{
338	suggestion_distance = current_distance;	×
339	suggestion = symbol;	×
340	}	×
341	}	×
342
343	return suggestion;	×
344	}	×
345	}

ArkScript-lang / Ark / 11629611787

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous