GCC Code Coverage Report

Line	Branch	Exec	Source
1
2			#ifndef LYTHON_TREE_EVAL_HEADER
3			#define LYTHON_TREE_EVAL_HEADER
4
5			#include "ast/magic.h"
6			#include "ast/ops.h"
7			#include "ast/visitor.h"
8			#include "sema/bindings.h"
9			#include "sema/builtin.h"
10			#include "sema/errors.h"
11			#include "utilities/strings.h"
12
13			namespace lython {
14
15			using PartialResult = Node;
16
17			struct TreeEvaluatorTrait {
18			using StmtRet = PartialResult*;
19			using ExprRet = PartialResult*;
20			using ModRet = PartialResult*;
21			using PatRet = PartialResult*;
22			using Trace = std::true_type;
23
24			enum
25			{ MaxRecursionDepth = LY_MAX_VISITOR_RECURSION_DEPTH };
26			};
27
28			struct StackTrace {
29			// The statement point to the line
30			// while the expression points to a specific location in the line
31			StmtNode const* stmt;
32			ExprNode const* expr;
33			};
34
35			/* Tree evaluator is a very simple interpreter that is also very slow.
36			* It takes as input the binding array generated by the semantic analysis
37			* i.e the evaluation context and the expression to evaluate given the context
38			*
39			* The expression to evaluate is often a call to a function, for a standard
40			* program that function will be main.
41			*
42			* While being slow this evaluator has the advantage or returning an AST
43			* as result which makes it perfect for compile-time usage.
44			*
45			* We can call the evaluator on standard declaration which will result in
46			* constant folding everything it can. Note that because we are able to represent
47			* complex types at compile time, string/list/dict even object operations can be folded.
48			*
49			* .. code-block:: python
50			*
51			* value = '.'.join(['a', 'b', 'c']) # <= Everything is known at compile time
52			* # It can be folded
53			*
54			* Additionally, this can be used to generate code at compile time by
55			* creating function with types as arguments.
56			*
57			* .. code-block::
58			*
59			* def Point(type: Type):
60			* class point:
61			* x: type
62			* y: type
63			*
64			* return point
65			*
66			* Pointi = Point(int)
67			* Pointf = Point(float) # <= Generate new types at compile time
68			*
69			*
70			* Evaluation Implementation
71			* -------------------------
72			*
73			* 1. Reuse as much as possible from the sema context
74			* Save the context inside each statement so we can use it
75			* during evaluation.
76			* Because the context is copied, it is easy to do parallel executions
77			*
78			* 2. Create a different context for evaluation only
79			*/
80			struct TreeEvaluator: BaseVisitor<TreeEvaluator, false, TreeEvaluatorTrait> {
81
82			public:
83			using Super = BaseVisitor<TreeEvaluator, false, TreeEvaluatorTrait>;
84
85			TreeEvaluator(Bindings& bindings): bindings(bindings) { traces.push_back(StackTrace()); }
86
87			virtual ~TreeEvaluator() {}
88
89			template <typename Exception, typename... Args>
90			ConstantValue raise(Args... args) {
91			return ConstantValue::none();
92			}
93
94			#define FUNCTION_GEN(name, fun) virtual PartialResult* fun(name##_t* n, int depth);
95
96			#define X(name, _)
97			#define SSECTION(name)
98			#define MOD(name, fun)
99			#define EXPR(name, fun) FUNCTION_GEN(name, fun)
100			#define STMT(name, fun) FUNCTION_GEN(name, fun)
101			#define MATCH(name, fun) FUNCTION_GEN(name, fun)
102
103			NODEKIND_ENUM(X, SSECTION, EXPR, STMT, MOD, MATCH)
104
105			#undef X
106			#undef SSECTION
107			#undef EXPR
108			#undef STMT
109			#undef MOD
110			#undef MATCH
111
112			#undef FUNCTION_GEN
113
114			// this some clean up code, acknowledge we have exceptions
115			// but this code needs to run regardless, it will stop if new exceptions are raised
116			struct HandleException {
117			HandleException(TreeEvaluator* self): self(self) {
118		✗	self->handling_exceptions = int(self->exceptions.size());
119		✗	}
120
121			~HandleException() { self->handling_exceptions = 0; }
122
123			TreeEvaluator* self;
124			};
125
126			// Helpers
127			PartialResult* get_next(Node* iterator, int depth);
128			PartialResult* call_enter(Node* ctx, int depth);
129			PartialResult* call_exit(Node* ctx, int depth);
130			PartialResult* call_native(Call_t* call, BuiltinType_t* n, int depth);
131			PartialResult* call_script(Call_t* call, FunctionDef_t* n, int depth);
132			PartialResult* call_constructor(Call_t* call, ClassDef_t* cls, int depth);
133			PartialResult* make_generator(Call_t* call, FunctionDef_t* n, int depth);
134
135			void raise_exception(PartialResult* exception, PartialResult* cause);
136
137			// Only returns true when new exceptions pop up
138			// we usually expect 0 exceptions,
139			// during exceptions handling we will execpt n and this will only be true
140			// if new exceptions are raised during the previous exceptions handling
141			bool has_exceptions() const { return int(exceptions.size()) > handling_exceptions; }
142
143			PartialResult* eval(StmtNode_t* stmt);
144
145			Constant* make(ClassDef* class_t, Array<Constant*> args, int depth);
146
147			private:
148			PartialResult* exec(StmtNode_t* stmt, int depth) {
149		176	StackTrace& trace = get_kwtrace();
150		176	trace.stmt = stmt;
151		176	return Super::exec(stmt, depth);
152			}
153
154			PartialResult* exec(ExprNode_t* expr, int depth) {
155		570	StackTrace& trace = get_kwtrace();
156		570	trace.expr = expr;
157		570	return Super::exec(expr, depth);
158			}
159
160			StackTrace& get_kwtrace() { return traces[traces.size() - 1]; }
161
162			// private:
163			// --------
164			public:
165			void set_return_value(PartialResult* ret) {
166			// I cant delete the return value here, it might be re-used in the context
167			// It is hard to decide when to delete the return value
168			// the problem lie when a value is returned, its scope ends
169			// but the value belongs to the upper scope
170			//
171			// Maybe just make a stack of scopes and return makes the value belong to the upper scope
172			// or promote it to the upper scope so it does not get deleted
173			//
174			// I thought about allocating the return value before the call is made
175			// so I do not have to promote the return value (it would already be on the right scope)
176			// but it might get tricky with values referenced twice
177			// when the variable is promoted the references are removed but not freed because it is
178			// still used as a return value
179
180			// if (return_value != nullptr) {
181			// root.remove_child_if_parent(return_value, true);
182			// }
183		47	return_value = ret;
184		47	}
185
186			// This can be used as a root for garbage collection
187			// root is never deleted but its children gets checked as reachable or not
188			// we can traverse the bindings struct to check if all values are reachable or not
189			// every time we leave a scope we could do a quick small GC step on that scope
190			// to remove free temporary variables and only keep the return value
191			Expression root;
192
193			Bindings& bindings;
194			PartialResult* return_value = nullptr;
195
196			private:
197			// `Registers`
198
199			bool loop_break = false;
200			bool loop_continue = false;
201			bool yielding = false;
202
203			PartialResult* cause = nullptr;
204			int handling_exceptions = 0;
205
206			Array<struct lyException*> exceptions;
207			Array<StackTrace> traces;
208			};
209
210			} // namespace lython
211
212			#endif
213