1 // This file is distributed under the BSD License.
2 // See "license.txt" for details.
3 // Copyright 2009-2012, Jonathan Turner (jonathan@emptycrate.com)
4 // Copyright 2009-2017, Jason Turner (jason@emptycrate.com)
5 // http://www.chaiscript.com
6 
7 #ifndef CHAISCRIPT_OPTIMIZER_HPP_
8 #define CHAISCRIPT_OPTIMIZER_HPP_
9 
10 #include "chaiscript_eval.hpp"
11 
12 
13 namespace chaiscript {
14   namespace optimizer {
15 
16     template<typename ... T>
17       struct Optimizer : T...
18     {
19       Optimizer() = default;
Optimizerchaiscript::optimizer::Optimizer20       explicit Optimizer(T ... t)
21         : T(std::move(t))...
22       {
23       }
24 
25       template<typename Tracer>
optimizechaiscript::optimizer::Optimizer26       auto optimize(eval::AST_Node_Impl_Ptr<Tracer> p) {
27         (void)std::initializer_list<int>{ (p = static_cast<T&>(*this).optimize(std::move(p)), 0)... };
28         return p;
29       }
30     };
31 
32     template<typename T>
child_at(eval::AST_Node_Impl<T> & node,const size_t offset)33       eval::AST_Node_Impl<T> &child_at(eval::AST_Node_Impl<T> &node, const size_t offset) {
34         if (node.children[offset]->identifier == AST_Node_Type::Compiled) {
35           return *(dynamic_cast<eval::Compiled_AST_Node<T> &>(*node.children[offset]).m_original_node);
36         } else {
37           return *node.children[offset];
38         }
39       }
40 
41     template<typename T>
child_at(const eval::AST_Node_Impl<T> & node,const size_t offset)42       const eval::AST_Node_Impl<T> &child_at(const eval::AST_Node_Impl<T> &node, const size_t offset) {
43         if (node.children[offset]->identifier == AST_Node_Type::Compiled) {
44           return *(dynamic_cast<const eval::Compiled_AST_Node<T> &>(*node.children[offset]).m_original_node);
45         } else {
46           return *node.children[offset];
47         }
48 
49 
50         /*
51         if (node->identifier == AST_Node_Type::Compiled) {
52           return dynamic_cast<const eval::Compiled_AST_Node<T>&>(*node).m_original_node->children[offset];
53         } else {
54           return node->children[offset];
55         }
56         */
57       }
58 
59     template<typename T>
child_count(const eval::AST_Node_Impl<T> & node)60       auto child_count(const eval::AST_Node_Impl<T> &node) {
61         if (node.identifier == AST_Node_Type::Compiled) {
62           return dynamic_cast<const eval::Compiled_AST_Node<T>&>(node).m_original_node->children.size();
63         } else {
64           return node.children.size();
65         }
66       }
67 
68     template<typename T, typename Callable>
make_compiled_node(eval::AST_Node_Impl_Ptr<T> original_node,std::vector<eval::AST_Node_Impl_Ptr<T>> children,Callable callable)69       auto make_compiled_node(eval::AST_Node_Impl_Ptr<T> original_node, std::vector<eval::AST_Node_Impl_Ptr<T>> children, Callable callable)
70       {
71         return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Compiled_AST_Node<T>>(std::move(original_node), std::move(children), std::move(callable));
72       }
73 
74 
75     struct Return {
76       template<typename T>
optimizechaiscript::optimizer::Return77       auto optimize(eval::AST_Node_Impl_Ptr<T> p)
78       {
79         if ( (p->identifier == AST_Node_Type::Def || p->identifier == AST_Node_Type::Lambda)
80             && !p->children.empty())
81         {
82           auto &last_child = p->children.back();
83           if (last_child->identifier == AST_Node_Type::Block) {
84             auto &block_last_child = last_child->children.back();
85             if (block_last_child->identifier == AST_Node_Type::Return) {
86               if (block_last_child->children.size() == 1) {
87                 last_child->children.back() = std::move(block_last_child->children[0]);
88               }
89             }
90           }
91         }
92 
93         return p;
94       }
95     };
96 
97     template<typename T>
contains_var_decl_in_scope(const eval::AST_Node_Impl<T> & node)98     bool contains_var_decl_in_scope(const eval::AST_Node_Impl<T> &node)
99     {
100       if (node.identifier == AST_Node_Type::Var_Decl || node.identifier == AST_Node_Type::Assign_Decl || node.identifier == AST_Node_Type::Reference) {
101         return true;
102       }
103 
104       const auto num = child_count(node);
105 
106       for (size_t i = 0; i < num; ++i) {
107         const auto &child = child_at(node, i);
108         if (child.identifier != AST_Node_Type::Block
109             && child.identifier != AST_Node_Type::For
110             && child.identifier != AST_Node_Type::Ranged_For
111             && contains_var_decl_in_scope(child)) {
112           return true;
113         }
114       }
115 
116       return false;
117     }
118 
119     struct Block {
120       template<typename T>
optimizechaiscript::optimizer::Block121       auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
122         if (node->identifier == AST_Node_Type::Block)
123         {
124           if (!contains_var_decl_in_scope(*node))
125           {
126             if (node->children.size() == 1) {
127               return std::move(node->children[0]);
128             } else {
129               return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Scopeless_Block_AST_Node<T>>(node->text, node->location,
130                   std::move(node->children));
131             }
132           }
133         }
134 
135         return node;
136       }
137     };
138 
139     struct Dead_Code {
140       template<typename T>
optimizechaiscript::optimizer::Dead_Code141         auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
142           if (node->identifier == AST_Node_Type::Block)
143           {
144             std::vector<size_t> keepers;
145             const auto num_children = node->children.size();
146             keepers.reserve(num_children);
147 
148             for (size_t i = 0; i < num_children; ++i) {
149               const auto &child = *node->children[i];
150               if ( (child.identifier != AST_Node_Type::Id
151                     && child.identifier != AST_Node_Type::Constant
152                     && child.identifier != AST_Node_Type::Noop)
153                   || i == num_children - 1) {
154                 keepers.push_back(i);
155               }
156             }
157 
158             if (keepers.size() == num_children) {
159               return node;
160             } else {
161               const auto new_children = [&](){
162                 std::vector<eval::AST_Node_Impl_Ptr<T>> retval;
163                 for (const auto x : keepers)
164                 {
165                   retval.push_back(std::move(node->children[x]));
166                 }
167                 return retval;
168               };
169 
170               return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Block_AST_Node<T>>(node->text, node->location, new_children());
171             }
172           } else {
173             return node;
174           }
175         }
176     };
177 
178     struct Unused_Return {
179       template<typename T>
optimizechaiscript::optimizer::Unused_Return180         auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
181           if ((node->identifier == AST_Node_Type::Block
182               || node->identifier == AST_Node_Type::Scopeless_Block)
183               && !node->children.empty())
184           {
185             for (size_t i = 0; i < node->children.size()-1; ++i) {
186               auto child = node->children[i].get();
187               if (child->identifier == AST_Node_Type::Fun_Call) {
188                 node->children[i] = chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Unused_Return_Fun_Call_AST_Node<T>>(child->text, child->location,
189                     std::move(child->children));
190               }
191             }
192           } else if ((node->identifier == AST_Node_Type::For
193                       || node->identifier == AST_Node_Type::While)
194                      && child_count(*node) > 0) {
195             auto &child = child_at(*node, child_count(*node) - 1);
196             if (child.identifier == AST_Node_Type::Block
197                 || child.identifier == AST_Node_Type::Scopeless_Block)
198             {
199               auto num_sub_children = child_count(child);
200               for (size_t i = 0; i < num_sub_children; ++i) {
201                 auto &sub_child = child_at(child, i);
202                 if (sub_child.identifier == AST_Node_Type::Fun_Call) {
203                   child.children[i] = chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Unused_Return_Fun_Call_AST_Node<T>>(sub_child.text, sub_child.location, std::move(sub_child.children));
204                 }
205               }
206             }
207           }
208           return node;
209         }
210     };
211 
212     struct Assign_Decl {
213       template<typename T>
optimizechaiscript::optimizer::Assign_Decl214       auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
215         if ((node->identifier == AST_Node_Type::Equation)
216              && node->text == "="
217              && node->children.size() == 2
218              && node->children[0]->identifier == AST_Node_Type::Var_Decl
219            )
220         {
221           std::vector<eval::AST_Node_Impl_Ptr<T>> new_children;
222           new_children.push_back(std::move(node->children[0]->children[0]));
223           new_children.push_back(std::move(node->children[1]));
224           return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Assign_Decl_AST_Node<T>>(node->text,
225               node->location, std::move(new_children) );
226         }
227 
228         return node;
229       }
230     };
231 
232 
233     struct If {
234       template<typename T>
optimizechaiscript::optimizer::If235       auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
236         if ((node->identifier == AST_Node_Type::If)
237              && node->children.size() >= 2
238              && node->children[0]->identifier == AST_Node_Type::Constant)
239         {
240           const auto condition = dynamic_cast<eval::Constant_AST_Node<T> *>(node->children[0].get())->m_value;
241           if (condition.get_type_info().bare_equal_type_info(typeid(bool))) {
242             if (boxed_cast<bool>(condition)) {
243               return std::move(node->children[1]);
244             } else if (node->children.size() == 3) {
245               return std::move(node->children[2]);
246             }
247           }
248         }
249 
250         return node;
251       }
252     };
253 
254     struct Partial_Fold {
255       template<typename T>
optimizechaiscript::optimizer::Partial_Fold256       auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
257 
258         // Fold right side
259         if (node->identifier == AST_Node_Type::Binary
260             && node->children.size() == 2
261             && node->children[0]->identifier != AST_Node_Type::Constant
262             && node->children[1]->identifier == AST_Node_Type::Constant)
263         {
264           try {
265             const auto &oper = node->text;
266             const auto parsed = Operators::to_operator(oper);
267             if (parsed != Operators::Opers::invalid) {
268               const auto rhs = dynamic_cast<eval::Constant_AST_Node<T> *>(node->children[1].get())->m_value;
269               if (rhs.get_type_info().is_arithmetic()) {
270                 return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Fold_Right_Binary_Operator_AST_Node<T>>(node->text, node->location,
271                     std::move(node->children), rhs);
272               }
273             }
274           } catch (const std::exception &) {
275             //failure to fold, that's OK
276           }
277         }
278 
279         return node;
280       }
281     };
282 
283     struct Constant_Fold {
284       template<typename T>
optimizechaiscript::optimizer::Constant_Fold285       auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
286 
287         if (node->identifier == AST_Node_Type::Prefix
288             && node->children.size() == 1
289             && node->children[0]->identifier == AST_Node_Type::Constant)
290         {
291           try {
292             const auto &oper = node->text;
293             const auto parsed = Operators::to_operator(oper, true);
294             const auto lhs = dynamic_cast<const eval::Constant_AST_Node<T> *>(node->children[0].get())->m_value;
295             const auto match = oper + node->children[0]->text;
296 
297             if (parsed != Operators::Opers::invalid && parsed != Operators::Opers::bitwise_and && lhs.get_type_info().is_arithmetic()) {
298               const auto val  = Boxed_Number::do_oper(parsed, lhs);
299               return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Constant_AST_Node<T>>(std::move(match), node->location, std::move(val));
300             } else if (lhs.get_type_info().bare_equal_type_info(typeid(bool)) && oper == "!") {
301               return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Constant_AST_Node<T>>(std::move(match), node->location, Boxed_Value(!boxed_cast<bool>(lhs)));
302             }
303           } catch (const std::exception &) {
304             //failure to fold, that's OK
305           }
306         } else if ((node->identifier == AST_Node_Type::Logical_And || node->identifier == AST_Node_Type::Logical_Or)
307             && node->children.size() == 2
308             && node->children[0]->identifier == AST_Node_Type::Constant
309             && node->children[1]->identifier == AST_Node_Type::Constant)
310         {
311           try {
312             const auto lhs = dynamic_cast<const eval::Constant_AST_Node<T> &>(*node->children[0]).m_value;
313             const auto rhs = dynamic_cast<const eval::Constant_AST_Node<T> &>(*node->children[1]).m_value;
314             if (lhs.get_type_info().bare_equal_type_info(typeid(bool)) && rhs.get_type_info().bare_equal_type_info(typeid(bool))) {
315               const auto match = node->children[0]->text + " " + node->text + " " + node->children[1]->text;
316               const auto val = [lhs_val = boxed_cast<bool>(lhs), rhs_val = boxed_cast<bool>(rhs), id = node->identifier] {
317                 if (id == AST_Node_Type::Logical_And) { return Boxed_Value(lhs_val && rhs_val); }
318                 else { return Boxed_Value(lhs_val || rhs_val); }
319               }();
320 
321               return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Constant_AST_Node<T>>(std::move(match), node->location, std::move(val));
322             }
323           } catch (const std::exception &) {
324             //failure to fold, that's OK
325           }
326         } else if (node->identifier == AST_Node_Type::Binary
327             && node->children.size() == 2
328             && node->children[0]->identifier == AST_Node_Type::Constant
329             && node->children[1]->identifier == AST_Node_Type::Constant)
330         {
331           try {
332             const auto &oper = node->text;
333             const auto parsed = Operators::to_operator(oper);
334             if (parsed != Operators::Opers::invalid) {
335               const auto lhs = dynamic_cast<const eval::Constant_AST_Node<T> &>(*node->children[0]).m_value;
336               const auto rhs = dynamic_cast<const eval::Constant_AST_Node<T> &>(*node->children[1]).m_value;
337               if (lhs.get_type_info().is_arithmetic() && rhs.get_type_info().is_arithmetic()) {
338                 const auto val  = Boxed_Number::do_oper(parsed, lhs, rhs);
339                 const auto match = node->children[0]->text + " " + oper + " " + node->children[1]->text;
340                 return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Constant_AST_Node<T>>(std::move(match), node->location, std::move(val));
341               }
342             }
343           } catch (const std::exception &) {
344             //failure to fold, that's OK
345           }
346         } else if (node->identifier == AST_Node_Type::Fun_Call
347                    && node->children.size() == 2
348                    && node->children[0]->identifier == AST_Node_Type::Id
349                    && node->children[1]->identifier == AST_Node_Type::Arg_List
350                    && node->children[1]->children.size() == 1
351                    && node->children[1]->children[0]->identifier == AST_Node_Type::Constant) {
352 
353           const auto arg = dynamic_cast<const eval::Constant_AST_Node<T> &>(*node->children[1]->children[0]).m_value;
354           if (arg.get_type_info().is_arithmetic()) {
355             const auto &fun_name = node->children[0]->text;
356 
357             const auto make_constant = [&node, &fun_name](auto val){
358               const auto match = fun_name + "(" + node->children[1]->children[0]->text + ")";
359               return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Constant_AST_Node<T>>(std::move(match), node->location, const_var(val));
360             };
361 
362             if (fun_name == "double") {
363               return make_constant(Boxed_Number(arg).get_as<double>());
364             } else if (fun_name == "int") {
365               return make_constant(Boxed_Number(arg).get_as<int>());
366             } else if (fun_name == "float") {
367               return make_constant(Boxed_Number(arg).get_as<float>());
368             } else if (fun_name == "long") {
369               return make_constant(Boxed_Number(arg).get_as<long>());
370             } else if (fun_name == "size_t") {
371               return make_constant(Boxed_Number(arg).get_as<size_t>());
372             }
373 
374 
375           }
376 
377         }
378 
379         return node;
380       }
381     };
382 
383     struct For_Loop {
384       template<typename T>
optimizechaiscript::optimizer::For_Loop385       auto optimize(eval::AST_Node_Impl_Ptr<T> for_node) {
386 
387         if (for_node->identifier != AST_Node_Type::For) {
388           return for_node;
389         }
390 
391         const auto &eq_node = child_at(*for_node, 0);
392         const auto &binary_node = child_at(*for_node, 1);
393         const auto &prefix_node = child_at(*for_node, 2);
394 
395         if (child_count(*for_node) == 4
396             && eq_node.identifier == AST_Node_Type::Assign_Decl
397             && child_count(eq_node) == 2
398             && child_at(eq_node, 0).identifier == AST_Node_Type::Id
399             && child_at(eq_node, 1).identifier == AST_Node_Type::Constant
400             && binary_node.identifier == AST_Node_Type::Binary
401             && binary_node.text == "<"
402             && child_count(binary_node) == 2
403             && child_at(binary_node, 0).identifier == AST_Node_Type::Id
404             && child_at(binary_node, 0).text == child_at(eq_node,0).text
405             && child_at(binary_node, 1).identifier == AST_Node_Type::Constant
406             && prefix_node.identifier == AST_Node_Type::Prefix
407             && prefix_node.text == "++"
408             && child_count(prefix_node) == 1
409             && child_at(prefix_node, 0).identifier == AST_Node_Type::Id
410             && child_at(prefix_node, 0).text == child_at(eq_node,0).text)
411         {
412           const Boxed_Value &begin = dynamic_cast<const eval::Constant_AST_Node<T> &>(child_at(eq_node, 1)).m_value;
413           const Boxed_Value &end = dynamic_cast<const eval::Constant_AST_Node<T> &>(child_at(binary_node, 1)).m_value;
414           const std::string &id = child_at(prefix_node, 0).text;
415 
416           if (begin.get_type_info().bare_equal(user_type<int>())
417               && end.get_type_info().bare_equal(user_type<int>())) {
418 
419             const auto start_int = boxed_cast<int>(begin);
420             const auto end_int = boxed_cast<int>(end);
421 
422             // note that we are moving the last element out, then popping the empty shared_ptr
423             // from the vector
424             std::vector<eval::AST_Node_Impl_Ptr<T>> body_vector;
425             auto body_child = std::move(for_node->children[3]);
426             for_node->children.pop_back();
427             body_vector.emplace_back(std::move(body_child));
428 
429             return make_compiled_node(std::move(for_node), std::move(body_vector),
430                 [id, start_int, end_int](const std::vector<eval::AST_Node_Impl_Ptr<T>> &children, const chaiscript::detail::Dispatch_State &t_ss) {
431                   assert(children.size() == 1);
432                   chaiscript::eval::detail::Scope_Push_Pop spp(t_ss);
433 
434                   int i = start_int;
435                   t_ss.add_object(id, var(&i));
436 
437                   try {
438                     for (; i < end_int; ++i) {
439                       try {
440                         // Body of Loop
441                         children[0]->eval(t_ss);
442                       } catch (eval::detail::Continue_Loop &) {
443                         // we got a continue exception, which means all of the remaining
444                         // loop implementation is skipped and we just need to continue to
445                         // the next iteration step
446                       }
447                     }
448                   } catch (eval::detail::Break_Loop &) {
449                     // loop broken
450                   }
451 
452                   return void_var();
453                 }
454             );
455           } else {
456             return for_node;
457           }
458         } else {
459           return for_node;
460         }
461       }
462     };
463 
464     typedef Optimizer<optimizer::Partial_Fold, optimizer::Unused_Return, optimizer::Constant_Fold,
465       optimizer::If, optimizer::Return, optimizer::Dead_Code, optimizer::Block, optimizer::For_Loop, optimizer::Assign_Decl> Optimizer_Default;
466 
467   }
468 }
469 
470 
471 #endif
472