ChaiScript / ChaiScript
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-2018, 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;
20
      explicit Optimizer(T ... t)
21
        : T(std::move(t))...
22
      {
23
      }
24

25
      template<typename Tracer>
26 1
      auto optimize(eval::AST_Node_Impl_Ptr<Tracer> p) {
27 1
        ( (p = static_cast<T&>(*this).optimize(std::move(p))), ... );
28 1
        return p;
29
      }
30
    };
31

32
    template<typename T>
33 1
      eval::AST_Node_Impl<T> &child_at(eval::AST_Node_Impl<T> &node, const size_t offset) noexcept {
34 1
        if (node.children[offset]->identifier == AST_Node_Type::Compiled) {
35 0
          return *(dynamic_cast<eval::Compiled_AST_Node<T> &>(*node.children[offset]).m_original_node);
36
        } else {
37 1
          return *node.children[offset];
38
        }
39
      }
40

41
    template<typename T>
42 1
      const eval::AST_Node_Impl<T> &child_at(const eval::AST_Node_Impl<T> &node, const size_t offset) noexcept {
43 1
        if (node.children[offset]->identifier == AST_Node_Type::Compiled) {
44 0
          return *(dynamic_cast<const eval::Compiled_AST_Node<T> &>(*node.children[offset]).m_original_node);
45
        } else {
46 1
          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>
60 1
      auto child_count(const eval::AST_Node_Impl<T> &node) noexcept {
61 1
        if (node.identifier == AST_Node_Type::Compiled) {
62 0
          return dynamic_cast<const eval::Compiled_AST_Node<T>&>(node).m_original_node->children.size();
63
        } else {
64 1
          return node.children.size();
65
        }
66
      }
67

68
    template<typename T, typename Callable>
69 1
      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 1
        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>
77 1
      auto optimize(eval::AST_Node_Impl_Ptr<T> p)
78
      {
79 1
        if ( (p->identifier == AST_Node_Type::Def || p->identifier == AST_Node_Type::Lambda)
80 1
            && !p->children.empty())
81
        {
82 1
          auto &last_child = p->children.back();
83 1
          if (last_child->identifier == AST_Node_Type::Block) {
84 0
            auto &block_last_child = last_child->children.back();
85 0
            if (block_last_child->identifier == AST_Node_Type::Return) {
86 0
              if (block_last_child->children.size() == 1) {
87 0
                last_child->children.back() = std::move(block_last_child->children[0]);
88
              }
89
            }
90
          }
91
        }
92

93 1
        return p;
94
      }
95
    };
96

97
    template<typename T>
98 1
    bool contains_var_decl_in_scope(const eval::AST_Node_Impl<T> &node) noexcept
99
    {
100 1
      if (node.identifier == AST_Node_Type::Var_Decl || node.identifier == AST_Node_Type::Assign_Decl || node.identifier == AST_Node_Type::Reference) {
101 1
        return true;
102
      }
103

104 1
      const auto num = child_count(node);
105

106 1
      for (size_t i = 0; i < num; ++i) {
107 1
        const auto &child = child_at(node, i);
108 1
        if (child.identifier != AST_Node_Type::Block
109 1
            && child.identifier != AST_Node_Type::For
110 1
            && child.identifier != AST_Node_Type::Ranged_For
111 1
            && contains_var_decl_in_scope(child)) {
112 1
          return true;
113
        }
114
      }
115

116 1
      return false;
117
    }
118

119
    struct Block {
120
      template<typename T>
121 1
      auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
122 1
        if (node->identifier == AST_Node_Type::Block)
123
        {
124 1
          if (!contains_var_decl_in_scope(*node))
125
          {
126 1
            if (node->children.size() == 1) {
127 1
              return std::move(node->children[0]);
128
            } else {
129 1
              return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Scopeless_Block_AST_Node<T>>(node->text, node->location, 
130 1
                  std::move(node->children));
131
            }
132
          }
133
        }
134

135 1
        return node;
136
      }
137
    };
138

139
    struct Dead_Code {
140
      template<typename T>
141 1
        auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
142 1
          if (node->identifier == AST_Node_Type::Block)
143
          {
144 1
            std::vector<size_t> keepers;
145 1
            const auto num_children = node->children.size();
146 1
            keepers.reserve(num_children);
147

148 1
            for (size_t i = 0; i < num_children; ++i) {
149 1
              const auto &child = *node->children[i];
150 1
              if ( (child.identifier != AST_Node_Type::Id
151 1
                    && child.identifier != AST_Node_Type::Constant
152 1
                    && child.identifier != AST_Node_Type::Noop)
153 1
                  || i == num_children - 1) {
154 1
                keepers.push_back(i);
155
              }
156
            }
157

158 1
            if (keepers.size() == num_children) {
159 1
              return node;
160
            } else {
161 1
              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 1
              return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Block_AST_Node<T>>(node->text, node->location, new_children());
171
            }
172
          } else {
173 1
            return node;
174
          }
175
        }
176
    };
177

178
    struct Unused_Return {
179
      template<typename T>
180 1
        auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
181 1
          if ((node->identifier == AST_Node_Type::Block
182 1
              || node->identifier == AST_Node_Type::Scopeless_Block)
183 1
              && !node->children.empty())
184
          {
185 1
            for (size_t i = 0; i < node->children.size()-1; ++i) {
186 1
              auto child = node->children[i].get();
187 1
              if (child->identifier == AST_Node_Type::Fun_Call) {
188 1
                node->children[i] = chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Unused_Return_Fun_Call_AST_Node<T>>(child->text, child->location, 
189 1
                    std::move(child->children));
190
              }
191
            }
192 1
          } else if ((node->identifier == AST_Node_Type::For
193 1
                      || node->identifier == AST_Node_Type::While)
194 1
                     && child_count(*node) > 0) {
195 1
            auto &child = child_at(*node, child_count(*node) - 1);
196 1
            if (child.identifier == AST_Node_Type::Block
197 1
                || child.identifier == AST_Node_Type::Scopeless_Block)
198
            {
199 1
              auto num_sub_children = child_count(child);
200 1
              for (size_t i = 0; i < num_sub_children; ++i) {
201 1
                auto &sub_child = child_at(child, i);
202 1
                if (sub_child.identifier == AST_Node_Type::Fun_Call) {
203 1
                  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 1
          return node;
209
        }
210
    };
211

212
    struct Assign_Decl {
213
      template<typename T>
214 1
      auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
215 1
        if ((node->identifier == AST_Node_Type::Equation)
216 1
             && node->text == "="
217 1
             && node->children.size() == 2
218 1
             && node->children[0]->identifier == AST_Node_Type::Var_Decl
219
           )
220
        {
221 1
          std::vector<eval::AST_Node_Impl_Ptr<T>> new_children;
222 1
          new_children.push_back(std::move(node->children[0]->children[0]));
223 1
          new_children.push_back(std::move(node->children[1]));
224 1
          return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Assign_Decl_AST_Node<T>>(node->text, 
225 1
              node->location, std::move(new_children) );
226
        }
227

228 1
        return node;
229
      }
230
    };
231

232

233
    struct If {
234
      template<typename T>
235 1
      auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
236 1
        if ((node->identifier == AST_Node_Type::If)
237 1
             && node->children.size() >= 2
238 1
             && node->children[0]->identifier == AST_Node_Type::Constant)
239
        {
240 0
          const auto condition = dynamic_cast<eval::Constant_AST_Node<T> *>(node->children[0].get())->m_value;
241 1
          if (condition.get_type_info().bare_equal_type_info(typeid(bool))) {
242 1
            if (boxed_cast<bool>(condition)) {
243 1
              return std::move(node->children[1]);
244 1
            } else if (node->children.size() == 3) {
245 1
              return std::move(node->children[2]);
246
            }
247
          }
248
        }
249

250 1
        return node;
251
      }
252
    };
253

254
    struct Partial_Fold {
255
      template<typename T>
256 1
      auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
257

258
        // Fold right side
259 1
        if (node->identifier == AST_Node_Type::Binary
260 1
            && node->children.size() == 2
261 1
            && node->children[0]->identifier != AST_Node_Type::Constant
262 1
            && node->children[1]->identifier == AST_Node_Type::Constant)
263
        {
264
          try {
265 1
            const auto &oper = node->text;
266 1
            const auto parsed = Operators::to_operator(oper);
267 1
            if (parsed != Operators::Opers::invalid) {
268
              const auto rhs = dynamic_cast<eval::Constant_AST_Node<T> *>(node->children[1].get())->m_value;
269 1
              if (rhs.get_type_info().is_arithmetic()) {
270 1
                return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Fold_Right_Binary_Operator_AST_Node<T>>(node->text, node->location, 
271 1
                    std::move(node->children), rhs);
272
              }
273
            }
274 0
          } catch (const std::exception &) {
275
            //failure to fold, that's OK
276
          }
277
        }
278

279 1
        return node;
280
      }
281
    };
282

283
    struct Constant_Fold {
284
      template<typename T>
285 1
      auto optimize(eval::AST_Node_Impl_Ptr<T> node) {
286

287 1
        if (node->identifier == AST_Node_Type::Prefix
288 1
            && node->children.size() == 1
289 1
            && node->children[0]->identifier == AST_Node_Type::Constant)
290
        {
291
          try {
292 1
            const auto &oper = node->text;
293 1
            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 1
            const auto match = oper + node->children[0]->text;
296

297 1
            if (parsed != Operators::Opers::invalid && parsed != Operators::Opers::bitwise_and && lhs.get_type_info().is_arithmetic()) {
298 1
              const auto val  = Boxed_Number::do_oper(parsed, lhs);
299 1
              return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Constant_AST_Node<T>>(std::move(match), node->location, std::move(val));
300 1
            } else if (lhs.get_type_info().bare_equal_type_info(typeid(bool)) && oper == "!") {
301 1
              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 1
          } catch (const std::exception &) {
304
            //failure to fold, that's OK
305
          }
306 1
        } else if ((node->identifier == AST_Node_Type::Logical_And || node->identifier == AST_Node_Type::Logical_Or)
307 1
            && node->children.size() == 2
308 1
            && node->children[0]->identifier == AST_Node_Type::Constant
309 1
            && node->children[1]->identifier == AST_Node_Type::Constant)
310
        {
311
          try {
312 0
            const auto lhs = dynamic_cast<const eval::Constant_AST_Node<T> &>(*node->children[0]).m_value;
313 0
            const auto rhs = dynamic_cast<const eval::Constant_AST_Node<T> &>(*node->children[1]).m_value;
314 1
            if (lhs.get_type_info().bare_equal_type_info(typeid(bool)) && rhs.get_type_info().bare_equal_type_info(typeid(bool))) {
315 1
              const auto match = node->children[0]->text + " " + node->text + " " + node->children[1]->text;
316 1
              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 1
              return chaiscript::make_unique<eval::AST_Node_Impl<T>, eval::Constant_AST_Node<T>>(std::move(match), node->location, std::move(val));
322
            }
323 0
          } catch (const std::exception &) {
324
            //failure to fold, that's OK
325
          }
326 1
        } else if (node->identifier == AST_Node_Type::Binary
327 1
            && node->children.size() == 2
328 1
            && node->children[0]->identifier == AST_Node_Type::Constant
329 1
            && node->children[1]->identifier == AST_Node_Type::Constant)
330
        {
331
          try {
332 1
            const auto &oper = node->text;
333 1
            const auto parsed = Operators::to_operator(oper);
334 1
            if (parsed != Operators::Opers::invalid) {
335 0
              const auto lhs = dynamic_cast<const eval::Constant_AST_Node<T> &>(*node->children[0]).m_value;
336 0
              const auto rhs = dynamic_cast<const eval::Constant_AST_Node<T> &>(*node->children[1]).m_value;
337 1
              if (lhs.get_type_info().is_arithmetic() && rhs.get_type_info().is_arithmetic()) {
338 1
                const auto val  = Boxed_Number::do_oper(parsed, lhs, rhs);
339 1
                const auto match = node->children[0]->text + " " + oper + " " + node->children[1]->text;
340 1
                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 1
          } catch (const std::exception &) {
344
            //failure to fold, that's OK
345
          }
346 1
        } else if (node->identifier == AST_Node_Type::Fun_Call
347 1
                   && node->children.size() == 2
348 1
                   && node->children[0]->identifier == AST_Node_Type::Id
349 1
                   && node->children[1]->identifier == AST_Node_Type::Arg_List
350 1
                   && node->children[1]->children.size() == 1
351 1
                   && 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 1
          if (arg.get_type_info().is_arithmetic()) {
355 1
            const auto &fun_name = node->children[0]->text;
356

357 1
            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 1
            if (fun_name == "double") {
363 0
              return make_constant(Boxed_Number(arg).get_as<double>());
364 1
            } else if (fun_name == "int") {
365 1
              return make_constant(Boxed_Number(arg).get_as<int>());
366 1
            } else if (fun_name == "float") {
367 1
              return make_constant(Boxed_Number(arg).get_as<float>());
368 1
            } else if (fun_name == "long") {
369 0
              return make_constant(Boxed_Number(arg).get_as<long>());
370 1
            } else if (fun_name == "size_t") {
371 1
              return make_constant(Boxed_Number(arg).get_as<size_t>());
372
            }
373

374

375
          }
376

377
        }
378

379 1
        return node;
380
      }
381
    };
382

383
    struct For_Loop {
384
      template<typename T>
385 1
      auto optimize(eval::AST_Node_Impl_Ptr<T> for_node) {
386

387 1
        if (for_node->identifier != AST_Node_Type::For) {
388 1
          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 1
                      } 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 1
                  } 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

Read our documentation on viewing source code .

Loading