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