1/* Copyright (c) 1997-2021 2 Ewgenij Gawrilow, Michael Joswig, and the polymake team 3 Technische Universität Berlin, Germany 4 https://polymake.org 5 6 This program is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by the 8 Free Software Foundation; either version 2, or (at your option) any 9 later version: http://www.gnu.org/licenses/gpl.txt. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15-------------------------------------------------------------------------------- 16*/ 17 18#include "polymake/perl/glue.h" 19#include "polymake/perl/macros.h" 20#include "polymake/perl/wrappers.h" 21 22#include "polymake/Graph.h" 23#include "polymake/Bitset.h" 24#include <deque> 25 26namespace pm { namespace perl { 27 28class RuleGraph { 29public: 30 // must be kept in sync with Scheduler.pm 31 enum arc_state_t { inactive_arc, weak_arc, initial_arc, optional_arc=initial_arc, exclusive_arc, unique_arc, resolved_arc, source_arc }; 32 33 // lower bits in node_in_state 34 enum { alive_node=1, ready_node=2, scheduled_node=4, pending_supplier=8 }; 35 36 typedef graph::Graph<graph::Directed> graph_t; 37 typedef graph::EdgeMap<graph::Directed, arc_state_t> arc_map_t; 38 39 RuleGraph() 40 : graph() 41 , arc_states(graph) {} 42 43 Int add_node(pTHX_ AV* rule); 44 45 void add_arc(Int from, Int to, arc_state_t arc_state) 46 { 47 const Int e = graph.add_edge(from, to); 48 arc_states[e] = arc_state; 49 } 50 51 // first elimination round after gather_rules 52 bool eliminate_after_gather(pTHX_ SV* tell_sv, SV** rules_to_elim, Int n_elim); 53 54 // elimination in a variant 55 bool eliminate_in_variant(pTHX_ char* state_vec, arc_state_t max_optional_state, AV* ready_rules, SV** rules_to_elim, Int n_elim) const; 56 57 bool add_scheduled_rule(pTHX_ char* state_vec, AV* ready_rules, SV* rule_to_add, Int enforced, SV* rule_without_perm) const; 58 59 /// @param state_vec state to modify, that is, to remove all rules not listed among the arguments 60 /// @param init_state_vec state of the initial rule chain, to check the alive status of all rules 61 /// @param final_state_vec state of the resolved chain, to check the status of PermActions 62 void constrain_to_rules(pTHX_ char* state_vec, AV* ready_rules, char* init_state_vec, char* final_state_vec, SV** rules_to_keep, Int n_keep) const; 63 64 size_t state_vector_size() const 65 { 66 return (2 * graph.nodes() + graph.edges()) * sizeof(Int); 67 } 68 69 bool rule_is_ready_to_use(pTHX_ SV* rule); 70 71 void init_state(pTHX_ char* state_vec, AV* ready_rules); 72 73 bool is_complete(char* state_vec) const; 74 bool rule_is_alive(char* state_vec, SV* rule_ref) const; 75 76 SV** select_ready_rule(pTHX_ char* state_vec, AV* ready_rules) const; 77 78 SV** push_resolved_suppliers(pTHX_ char* state_vec, SV* rule_ref) const; 79 SV** push_resolved_consumers(pTHX_ char* state_vec, SV* rule_ref) const; 80 81 SV** push_active_rules(pTHX_ char* state_vec) const; 82 SV** push_active_suppliers(pTHX_ char* state_vec, SV* rule_ref) const; 83 SV** push_active_consumers(pTHX_ char* state_vec, SV* rule_ref) const; 84 85 static SV* class_descr; 86 static int RuleChain_rgr_index, RuleChain_rgr_state_index, RuleChain_ready_rules_index, 87 RuleDeputy_rgr_node_index, RuleDeputy_flags_index, RuleDeputy_weight_index, 88 Rule_is_precondition, Rule_is_perm_action; 89 90private: 91 class bare_graph_adapter; 92 class overlaid_state_adapter; 93 94 // index into node_state 95 static constexpr int in_state = 0, ///< nr. of unresolved suppliers (inputs)+1; 0 = eliminated 96 out_state = 1; ///< 2 * nr. of alive unique and source arcs+1 when scheduled 97 98 static Int rule_ref2node(SV* rule_ref); 99 100 void fill_elim_queue(SV** rules_to_elim, Int n_elim) const; 101 void remove_ready_rule(pTHX_ AV* ready_rules, Int node) const; 102 static SV** extract_ready_rule(pTHX_ SV** SP, AV* ready_rules, SV** ready, SV** ready_last); 103 104 template <typename GraphAdapter> 105 bool eliminate(pTHX_ const GraphAdapter& adapter, arc_state_t max_optional_state, AV* ready_rules) const; 106 107 void add_rule(pTHX_ const overlaid_state_adapter& adapter, AV* ready_rules, Int node, Int enforced = 0, bool with_permutation = false) const; 108 109 // must be kept in sync with Scheduler.pm 110 enum announce_t { announce_no_supplier, announce_no_consumer, announce_no_path }; 111 112 class renumber_nodes; 113 114 class renumber_edges { 115 public: 116 renumber_edges(const arc_map_t& old_arg, arc_state_t* new_arg) 117 : old_arc_states(old_arg) 118 , new_arc_states(new_arg) {} 119 120 void operator() (Int old_id, Int new_id) const 121 { 122 new_arc_states[new_id] = old_arc_states[old_id]; 123 } 124 125 private: 126 const arc_map_t& old_arc_states; 127 arc_state_t* const new_arc_states; 128 }; 129 130 graph_t graph; 131 arc_map_t arc_states; 132 std::vector<AV*> rule_deputies; 133 134 /// scratch variables for repeated use 135 mutable Bitset marked_elim_nodes; 136 mutable std::deque<Int> elim_queue; 137}; 138 139Int RuleGraph::add_node(pTHX_ AV* rule) 140{ 141 const Int node = graph.add_node(); 142 if (size_t(node) >= rule_deputies.size()) { 143 assert(size_t(node) == rule_deputies.size()); 144 rule_deputies.push_back(rule); 145 } else { 146 rule_deputies[node] = rule; 147 } 148 if (rule) { 149 SV* node_sv = AvARRAY(rule)[RuleDeputy_rgr_node_index]; 150 assert(!SvOK(node_sv)); 151 sv_setiv(node_sv, node); 152 } 153 return node; 154} 155 156class RuleGraph::renumber_nodes { 157public: 158 renumber_nodes(pTHX_ std::vector<AV*>& rule_deputies_arg) 159 : rule_deputies(rule_deputies_arg) {} 160 161 void operator() (Int old_n, Int new_n) const 162 { 163 if (old_n != new_n) { 164 assert(!rule_deputies[new_n]); 165 AV* rule = rule_deputies[old_n]; 166 if (rule) { 167 dTHX; 168 SV* node_sv = AvARRAY(rule)[RuleDeputy_rgr_node_index]; 169 assert(SvIOKp(node_sv) && SvIVX(node_sv) == old_n); 170 sv_setiv(node_sv, new_n); 171 } 172 rule_deputies[new_n] = rule; 173#ifndef NDEBUG 174 rule_deputies[old_n] = nullptr; 175#endif 176 } 177 } 178 179private: 180 std::vector<AV*>& rule_deputies; 181}; 182 183inline 184Int RuleGraph::rule_ref2node(SV* rule_ref) 185{ 186 assert(SvROK(rule_ref)); 187 SV* const node_sv = PmArray(rule_ref)[RuleDeputy_rgr_node_index]; 188 return node_sv && SvIOKp(node_sv) ? SvIVX(node_sv) : -1; 189} 190 191void RuleGraph::init_state(pTHX_ char* state_vec, AV* ready_rules) 192{ 193 Int* node_state_vec = reinterpret_cast<Int*>(state_vec); 194 arc_state_t* arc_state_vec = reinterpret_cast<arc_state_t*>(node_state_vec+2*graph.nodes()); 195 graph.squeeze(renumber_nodes(aTHX_ rule_deputies)); 196 graph.squeeze_edges(renumber_edges(arc_states, arc_state_vec)); 197 rule_deputies.resize(graph.nodes()); 198 199 Int* node_state=node_state_vec; 200 for (auto node_it = entire(nodes(graph)); !node_it.at_end(); ++node_it, node_state += 2) { 201 Int cnt = alive_node; 202 for (auto supplier = node_it.in_edges().begin(); !supplier.at_end(); ++supplier) { 203 const arc_state_t arc_state = arc_state_vec[*supplier]; 204 if (arc_state != inactive_arc && arc_state != exclusive_arc) 205 cnt += pending_supplier; 206 } 207 if (cnt == alive_node) { 208 AV* rule = rule_deputies[node_it.index()]; 209 if (rule) { 210 av_push(ready_rules, newRV((SV*)rule)); 211 cnt += ready_node; 212 } 213 } 214 node_state[in_state] = cnt; 215 216 cnt = 0; 217 for (auto consumer = node_it.out_edges().begin(); !consumer.at_end(); ++consumer) { 218 const arc_state_t arc_state = arc_state_vec[*consumer]; 219 if (arc_state > optional_arc) 220 ++cnt; 221 } 222 node_state[out_state] = cnt; 223 } 224} 225 226void RuleGraph::fill_elim_queue(SV** rules_to_elim, Int n_elim) const 227{ 228 marked_elim_nodes.clear(); 229 elim_queue.clear(); 230 231 for (; n_elim > 0; --n_elim, ++rules_to_elim) { 232 const Int node = rule_ref2node(*rules_to_elim); 233 assert(node > 0); 234 marked_elim_nodes += node; 235 elim_queue.push_back(node); 236 } 237} 238 239void RuleGraph::remove_ready_rule(pTHX_ AV* ready_rules, Int node) const 240{ 241 if (AvFILLp(ready_rules) >= 0) { 242 SV* rule = (SV*)rule_deputies[node]; 243 assert(rule); 244 for (SV **ready = AvARRAY(ready_rules), **ready_last = ready+AvFILLp(ready_rules); 245 ready <= ready_last; ++ready) { 246 if (rule == SvRV(*ready)) { 247 SvREFCNT_dec(*ready); 248 if (ready != ready_last) *ready = *ready_last; 249 *ready_last = PmEmptyArraySlot; 250 --AvFILLp(ready_rules); 251 break; 252 } 253 } 254 } 255} 256 257template <typename GraphAdapter> 258bool RuleGraph::eliminate(pTHX_ const GraphAdapter& adapter, arc_state_t max_optional_state, AV* ready_rules) const 259{ 260 for (bool second_round = false; ; second_round = true) { 261 262 while (!elim_queue.empty()) { 263 const Int node = elim_queue.front(); elim_queue.pop_front(); 264 265 assert(adapter.is_alive(node)); 266 if (adapter.is_ready(node)) 267 remove_ready_rule(aTHX_ ready_rules, node); 268 269 // check the consumer rules: some of them may become infeasible 270 271 for (auto consumer=graph.out_edges(node).begin(); !consumer.at_end(); ++consumer) { 272 arc_state_t& arc_state=adapter.arc_state(*consumer); 273 if (arc_state == inactive_arc) continue; 274 275 const Int cons_node = consumer.to_node(); 276 if (arc_state > max_optional_state && !marked_elim_nodes.contains(cons_node)) { 277 bool alt_exists = false; 278 if (arc_state >= source_arc) { 279 for (auto other_supplier = graph.in_edges(cons_node).begin(); !other_supplier.at_end(); ++other_supplier) { 280 const arc_state_t alt_state = adapter.arc_state(*other_supplier); 281 if (alt_state == arc_state && other_supplier.from_node() != node) { 282 alt_exists = true; 283 break; 284 } 285 } 286 } 287 if (!alt_exists) { 288 adapter.announce_elim(cons_node, announce_no_supplier); 289 if (cons_node == 0) return false; // final rule lost a mandatory supplier 290 marked_elim_nodes += cons_node; 291 elim_queue.push_back(cons_node); 292 } 293 } 294 adapter.remove_in_arc(cons_node, arc_state); 295 } 296 297 // check the supplier rules: some of them may become useless 298 299 for (auto supplier=graph.in_edges(node).begin(); !supplier.at_end(); ++supplier) { 300 arc_state_t& arc_state = adapter.arc_state(*supplier); 301 if (arc_state == inactive_arc) continue; 302 303 const Int supp_node = supplier.from_node(); 304 // optional arcs only occur between initial rules and the final rule (which can never be eliminated) 305 // or between PermAction and CreatingPermutation before scheduling the latter (can be ignored because of an opposite unique_arc) 306 if (arc_state > optional_arc && !marked_elim_nodes.contains(supp_node)) { 307 if (adapter.remove_out_arc(supp_node, *supplier) == 0) { 308 AV* const supp_rule = rule_deputies[supp_node]; 309 if (!supp_rule || !adapter.is_scheduled(supp_node)) { 310 // An unscheduled rule or a property node without consumers 311 adapter.announce_elim(supp_node, announce_no_consumer); 312 marked_elim_nodes += supp_node; 313 elim_queue.push_back(supp_node); 314 } else { 315 // When a scheduled rule looses all consumers, the variant does not make any sense more. 316 // Unused preconditions are tolerated, however, because they are evaluated ASAP and out of order. 317 SV* const supp_flags = AvARRAY(supp_rule)[RuleDeputy_flags_index]; 318 assert(SvIOKp(supp_flags)); 319 if (!(SvIVX(supp_flags) & Rule_is_precondition)) 320 return false; 321 } 322 } 323 } else { 324 arc_state=inactive_arc; 325 } 326 } 327 328 adapter.delete_node(node); 329 } 330 331 if (second_round || adapter.is_ready(0)) break; 332 333 // perform a reverse BFS starting at the final rule, mark all reachable rules; 334 // the rest can be eliminated 335 336 marked_elim_nodes = range(1, graph.dim()-1); 337 elim_queue.push_back(0); 338 while (!elim_queue.empty()) { 339 const Int node=elim_queue.front(); elim_queue.pop_front(); 340 for (auto supplier=graph.in_edges(node).begin(); !supplier.at_end(); ++supplier) { 341 switch (adapter.arc_state(*supplier)) { 342 case inactive_arc: 343 break; 344 case resolved_arc: 345 // watch out for scheduled ruled becoming useless in the second round 346 assert(adapter.is_scheduled(supplier.from_node())); 347 marked_elim_nodes -= supplier.from_node(); 348 break; 349 default: 350 // recurse down on rules which are neither scheduled nor eliminated 351 { 352 const Int supp_node = supplier.from_node(); 353 assert(adapter.is_alive(supp_node) && !adapter.is_scheduled(supp_node)); 354 if (marked_elim_nodes.contains(supp_node)) { 355 marked_elim_nodes -= supp_node; 356 elim_queue.push_back(supp_node); 357 } 358 } 359 break; 360 } 361 } 362 } 363 364 for (auto unreached=marked_elim_nodes.begin(); !unreached.at_end(); ++unreached) { 365 const Int node = *unreached; 366 if (adapter.is_alive(node)) { 367 if (adapter.is_scheduled(node)) { 368 marked_elim_nodes -= node; 369 } else { 370 adapter.announce_elim(node, announce_no_path); 371 elim_queue.push_back(node); 372 } 373 } 374 } 375 } 376 377 return true; 378} 379 380class RuleGraph::bare_graph_adapter { 381public: 382 bare_graph_adapter(pTHX_ RuleGraph& me_arg, SV* tell_arg) 383 : me(me_arg) 384 , tell_sv(tell_arg) {} 385 386 arc_state_t& arc_state(Int edge_id) const 387 { 388 return me.arc_states[edge_id]; 389 } 390 391 void announce_elim(Int node, announce_t reason) const 392 { 393 if (tell_sv) { 394 if (AV* rule = me.rule_deputies[node]) { 395 dTHX; 396 PmStartFuncall(2); 397 mPUSHs(newRV((SV*)rule)); 398 mPUSHi(reason); 399 PUTBACK; 400 glue::call_func_void(aTHX_ tell_sv); 401 } 402 } 403 } 404 405 // do nothing now; all edges will be removed with the node 406 void remove_in_arc(Int, arc_state_t&) const {} 407 408 Int remove_out_arc(Int node, Int) const 409 { 410 // do nothing now; all edges will be removed with the node; 411 // report the out-degree as it will become after the deletion 412 return me.graph.out_degree(node)-1; 413 } 414 415 void delete_node(Int node) const 416 { 417 me.graph.delete_node(node); 418 if (AV* rule = me.rule_deputies[node]) { 419#if PerlVersion < 5220 420 dTHX; 421#endif 422 SvOK_off(AvARRAY(rule)[RuleDeputy_rgr_node_index]); 423 me.rule_deputies[node] = nullptr; 424 } 425 } 426 427 bool is_alive(Int node) const 428 { 429 return me.graph.node_exists(node); 430 } 431 432 bool is_ready(Int node) const 433 { 434 return false; 435 } 436 437 bool is_scheduled(Int node) const 438 { 439 return false; 440 } 441 442private: 443 RuleGraph& me; 444 SV* const tell_sv; 445}; 446 447class RuleGraph::overlaid_state_adapter { 448public: 449 overlaid_state_adapter(const RuleGraph& me, char* state_arg) 450 : node_states(reinterpret_cast<Int*>(state_arg)) 451 , arc_states(reinterpret_cast<arc_state_t*>(node_states+2*me.graph.nodes())) {} 452 453 arc_state_t& arc_state(Int edge_id) const 454 { 455 return arc_states[edge_id]; 456 } 457 458 void announce_elim(Int, announce_t) const {} 459 460 void remove_in_arc(Int node, arc_state_t& arc_state) const 461 { 462 if (arc_state != exclusive_arc) { 463 Int& node_state = node_in_state(node); 464 assert(node_state >= alive_node+pending_supplier); 465 node_state -= pending_supplier; 466 } 467 arc_state=inactive_arc; 468 } 469 470 Int remove_out_arc(Int node, Int edge_id) const 471 { 472 Int& node_state = node_out_state(node); 473 assert(node_state > 0); 474 --node_state; 475 assert(arc_states[edge_id] > optional_arc); 476 arc_states[edge_id] = inactive_arc; 477 return node_state; 478 } 479 480 void delete_node(Int node) const 481 { 482 node_in_state(node) = 0; 483 node_out_state(node) = 0; 484 } 485 486 /// @return true if the consumer must be removed from the ready list 487 bool activate_arc(Int node_from, Int node_to, Int edge_id, arc_state_t new_state) const 488 { 489 arc_state_t& arc_state = arc_states[edge_id]; 490 assert(arc_state == inactive_arc); 491 arc_state = new_state; 492 ++node_out_state(node_from); 493 Int& in_st = node_in_state(node_to); 494 in_st += pending_supplier; 495 if (in_st & ready_node) { 496 in_st -= ready_node; 497 return true; 498 } 499 return false; 500 } 501 502 Int& node_in_state(Int node) const 503 { 504 return node_states[node*2+in_state]; 505 } 506 507 Int& node_out_state(Int node) const 508 { 509 return node_states[node*2+out_state]; 510 } 511 512 bool is_alive(Int node) const 513 { 514 return node_in_state(node) != 0; 515 } 516 517 bool is_ready(Int node) const 518 { 519 return (node_in_state(node) & ready_node) != 0; 520 } 521 522 bool is_scheduled(Int node) const 523 { 524 return (node_in_state(node) & scheduled_node) != 0; 525 } 526 527 /// @param enforced when =1, a rule has been added unconditionally and out of order, 528 /// e.g. a precondition or a production rule in replay mode. 529 /// Such a rule should not make the chain infeasible even when all its consumers are gone. 530 void mark_as_scheduled(Int node, Int enforced) const 531 { 532 Int& state = node_in_state(node); 533 state &= ~ready_node; 534 state |= scheduled_node; 535 node_out_state(node) += enforced; 536 } 537 538private: 539 Int* const node_states; 540 arc_state_t* const arc_states; 541}; 542 543bool RuleGraph::rule_is_ready_to_use(pTHX_ SV* rule_ref) 544{ 545 const Int node = rule_ref2node(rule_ref); 546 assert(node >= 0); 547 if (graph.in_degree(node) == 0) { 548 bare_graph_adapter(aTHX_ *this, nullptr).delete_node(node); 549 return true; 550 } 551 return false; 552} 553 554bool RuleGraph::eliminate_after_gather(pTHX_ SV* tell_sv, SV** rules_to_elim, Int n_elim) 555{ 556 marked_elim_nodes.reserve(graph.dim()); 557 fill_elim_queue(rules_to_elim, n_elim); 558 return eliminate(aTHX_ bare_graph_adapter(aTHX_ *this, tell_sv), optional_arc, nullptr); 559} 560 561bool RuleGraph::eliminate_in_variant(pTHX_ char* state_vec, arc_state_t max_optional_state, AV* ready_rules, SV** rules_to_elim, Int n_elim) const 562{ 563 fill_elim_queue(rules_to_elim, n_elim); 564 return eliminate(aTHX_ overlaid_state_adapter(*this, state_vec), max_optional_state, ready_rules); 565} 566 567void RuleGraph::add_rule(pTHX_ const overlaid_state_adapter& adapter, AV* ready_rules, Int node, Int enforced, bool with_permutation) const 568{ 569 adapter.mark_as_scheduled(node, enforced); 570 571 for (auto consumer = graph.out_edges(node).begin(); !consumer.at_end(); ++consumer) { 572 arc_state_t& arc_state = adapter.arc_state(*consumer); 573 const arc_state_t old_arc_state = arc_state; 574 if (arc_state == inactive_arc) continue; 575 assert(arc_state != resolved_arc); 576 const Int cons_node = consumer.to_node(); 577 if (marked_elim_nodes.contains(cons_node)) continue; // consumer marked for elimination, don't waste time on analysing it 578 579 Int n_resolved_inputs; 580 if (arc_state >= source_arc) { 581 n_resolved_inputs = 0; 582 for (auto supplier = graph.in_edges(cons_node).begin(); !supplier.at_end(); ++supplier) { 583 arc_state_t& source_arc_state = adapter.arc_state(*supplier); 584 if (source_arc_state == old_arc_state) { 585 ++n_resolved_inputs; 586 const Int supp_node = supplier.from_node(); 587 if (supp_node == node) { 588 source_arc_state = resolved_arc; 589 } else { 590 assert(!adapter.is_scheduled(supp_node)); 591 source_arc_state = inactive_arc; 592 if (!marked_elim_nodes.contains(supp_node)) { 593 // this supplier might become superfluous 594 Int& supp_state = adapter.node_out_state(supp_node); 595 assert(supp_state > 0); 596 if (--supp_state == 0) { 597 marked_elim_nodes += supp_node; 598 elim_queue.push_back(supp_node); 599 } 600 } 601 } 602 } else if (source_arc_state == exclusive_arc) { 603 source_arc_state = inactive_arc; 604 const Int excl_node = supplier.from_node(); 605 assert(!adapter.is_scheduled(excl_node)); 606 Int& excl_state = adapter.node_out_state(excl_node); 607 assert(excl_state > 0 && !marked_elim_nodes.contains(excl_node)); 608 --excl_state; 609 marked_elim_nodes += excl_node; 610 elim_queue.push_back(excl_node); 611 } 612 } 613 } else { 614 arc_state = resolved_arc; 615 n_resolved_inputs = 1; 616 } 617 Int& cons_state = adapter.node_in_state(cons_node); 618 cons_state -= n_resolved_inputs * pending_supplier; 619 assert(cons_state > 0); 620 if (cons_state == alive_node) { 621 if (AV* const cons_rule=rule_deputies[cons_node]) { 622 cons_state |= ready_node; 623 SV* const cons_flags=AvARRAY(cons_rule)[RuleDeputy_flags_index]; 624 assert(SvIOKp(cons_flags)); 625 if (SvIVX(cons_flags) & Rule_is_perm_action) { 626 // permuted property has been successfully restored; unblock the consumers 627 add_rule(aTHX_ adapter, ready_rules, cons_node); 628 } else { 629 // the consumer is a production rule or a precondition 630 av_push(ready_rules, newRV((SV*)cons_rule)); 631 } 632 } else { 633 // this is a property node; propagate the resolved status to its consumers 634 add_rule(aTHX_ adapter, ready_rules, cons_node); 635 } 636 } else if (with_permutation && old_arc_state==unique_arc) { 637 const Int action_node = cons_node; 638#ifndef NDEBUG 639 AV* const action = rule_deputies[action_node]; 640 assert(action); 641 SV* const action_flags = AvARRAY(action)[RuleDeputy_flags_index]; 642 assert(SvIOKp(action_flags) && (SvIVX(action_flags) & Rule_is_perm_action)); 643#endif 644 for (auto action_consumer = graph.out_edges(action_node).begin(); !action_consumer.at_end(); ++action_consumer) { 645 const Int edge_id = *action_consumer; 646 switch (adapter.arc_state(*action_consumer)) { 647 case inactive_arc: 648 // block the final rule and other production rules triggering the same permutation until the permuted property is restored 649 { 650 const Int rule_node = action_consumer.to_node(); 651 assert(rule_deputies[rule_node]); 652 if (rule_node == 0 || 653 adapter.is_alive(rule_node) && !adapter.is_scheduled(rule_node) && !marked_elim_nodes.contains(rule_node)) { 654 if (adapter.activate_arc(action_node, rule_node, edge_id, unique_arc)) 655 remove_ready_rule(aTHX_ ready_rules, rule_node); 656 } 657 } 658 break; 659 case weak_arc: 660 // hide the weak reverse arc between the action and the rule creating a permutation; 661 // the in_state of the latter has already been updated in the caller 662 assert(action_consumer.to_node() == node); 663 adapter.arc_state(edge_id)=inactive_arc; 664 break; 665 case source_arc: 666 // remove all other suppliers of the property 667 { 668 const Int prop_node = action_consumer.to_node(); 669 assert(!rule_deputies[prop_node]); 670 for (auto prop_supplier = graph.in_edges(prop_node).begin(); !prop_supplier.at_end(); ++prop_supplier) { 671 arc_state_t& supp_arc_state = adapter.arc_state(*prop_supplier); 672 if (supp_arc_state == source_arc && *prop_supplier != edge_id) { 673 supp_arc_state = inactive_arc; 674 const Int supp_node = prop_supplier.from_node(); 675 if (!marked_elim_nodes.contains(supp_node)) { 676 // this supplier might become superfluous 677 assert(!adapter.is_scheduled(supp_node)); 678 Int& supp_state = adapter.node_out_state(supp_node); 679 assert(supp_state > 0); 680 if (--supp_state == 0) { 681 marked_elim_nodes += supp_node; 682 elim_queue.push_back(supp_node); 683 } 684 } 685 } 686 } 687 adapter.node_in_state(prop_node) = alive_node + pending_supplier; 688 } 689 break; 690 default: 691 break; 692 } 693 } 694 } 695 } 696} 697 698 699bool RuleGraph::add_scheduled_rule(pTHX_ char* state_vec, AV* ready_rules, SV* rule_to_add, Int enforced, SV* rule_without_perm) const 700{ 701 marked_elim_nodes.clear(); 702 elim_queue.clear(); 703 overlaid_state_adapter adapter(*this, state_vec); 704 705 const Int node = rule_ref2node(rule_to_add); 706 assert(node>0 && !adapter.is_scheduled(node)); 707 708 if (SvRV(rule_to_add) != SvRV(rule_without_perm)) { 709 // break the dependency between the rule w/o permutation and the rule to be scheduled 710 const Int node_without_perm = rule_ref2node(rule_without_perm); 711 assert(node_without_perm > 0 && adapter.node_in_state(node_without_perm) == alive_node + ready_node); 712 adapter.remove_out_arc(node_without_perm, graph.edge(node_without_perm, node)); 713 adapter.node_in_state(node) = alive_node; 714 marked_elim_nodes += node_without_perm; 715 elim_queue.push_back(node_without_perm); 716 add_rule(aTHX_ adapter, ready_rules, node, enforced, true); 717 } else { 718 assert(adapter.node_in_state(node) == alive_node + ready_node); 719 add_rule(aTHX_ adapter, ready_rules, node, enforced, false); 720 } 721 return eliminate(aTHX_ adapter, optional_arc, ready_rules); 722} 723 724inline 725SV** RuleGraph::extract_ready_rule(pTHX_ SV** SP, AV* ready_rules, SV** ready, SV** ready_last) 726{ 727 PUSHs(sv_2mortal(*ready)); 728 if (ready < ready_last) *ready=*ready_last; 729 *ready_last=PmEmptyArraySlot; 730 --AvFILLp(ready_rules); 731 return SP; 732} 733 734SV** RuleGraph::select_ready_rule(pTHX_ char* state_vec, AV* ready_rules) const 735{ 736 dSP; 737 overlaid_state_adapter adapter(*this, state_vec); 738 elim_queue.clear(); 739 740 // Collect all such properties produced by ready rules that they don't have any other (non-ready) producers. 741 // Among them, choose the properties having minimal number of producers. 742 // If all properties do have non-ready producers, choose those with minimal number of consumers (out-degree). 743 Int min_num_ready_prod = std::numeric_limits<Int>::max(); 744 Int min_out_degree = std::numeric_limits<Int>::max(); 745 bool all_ready_prod = false; 746 747 for (SV **ready = AvARRAY(ready_rules), ** const ready_last = ready + AvFILLp(ready_rules); ready <= ready_last; ++ready) { 748 const Int rule_node = rule_ref2node(*ready); 749 assert(rule_node > 0); 750 751 for (auto consumer = graph.out_edges(rule_node).begin(); !consumer.at_end(); ++consumer) { 752 if (adapter.arc_state(*consumer) != source_arc) continue; 753 const Int cons_node = consumer.to_node(); 754 if (cons_node == 0) { 755 // direct supplier of the final rule 756 return extract_ready_rule(aTHX_ SP, ready_rules, ready, ready_last); 757 } 758 // rules restoring permuted properties are filtered away in Scheduler.pm prior to calling this 759 assert(!rule_deputies[cons_node]); 760 761 Int num_prod = 0, num_ready_prod = 0; 762 763 for (auto supplier = graph.in_edges(cons_node).begin(); !supplier.at_end(); ++supplier) { 764 if (adapter.arc_state(*supplier) != source_arc) continue; 765 ++num_prod; 766 const Int supp_node = supplier.from_node(); 767 if (adapter.is_ready(supp_node)) ++num_ready_prod; 768 } 769 770 Int diff_to_best = 1; 771 if (all_ready_prod) { 772 if (num_prod == num_ready_prod) { 773 diff_to_best = num_ready_prod - min_num_ready_prod; 774 } 775 } else { 776 if (num_prod == num_ready_prod) { 777 all_ready_prod = true; 778 diff_to_best = -1; 779 } else { 780 diff_to_best = adapter.node_out_state(cons_node) - min_out_degree; 781 if (diff_to_best == 0) diff_to_best = num_ready_prod - min_num_ready_prod; 782 } 783 } 784 785 if (diff_to_best < 0) { 786 elim_queue.clear(); 787 elim_queue.push_back(cons_node); 788 min_num_ready_prod = num_ready_prod; 789 min_out_degree = adapter.node_out_state(cons_node); 790 } else if (diff_to_best == 0) { 791 elim_queue.push_back(cons_node); 792 } 793 } 794 } 795 796 // Choose a ready producer of the selected properties with maximal weight 797 798 SV* best_rule = nullptr; 799 int max_major_wt = -1, max_minor_wt = -1; 800 801 for (const Int prop_node : elim_queue) { 802 for (auto supplier = graph.in_edges(prop_node).begin(); !supplier.at_end(); ++supplier) { 803 if (adapter.arc_state(*supplier) != source_arc) continue; 804 const Int supp_node = supplier.from_node(); 805 if (adapter.is_ready(supp_node)) { 806 AV* rule = rule_deputies[supp_node]; 807 AV* weight = (AV*)SvRV(AvARRAY(rule)[RuleDeputy_weight_index]); 808 const int major_wt = int(SvIVX(AvARRAY(weight)[0])), 809 minor_wt = int(SvIVX(AvARRAY(weight)[1])); 810 if (major_wt > max_major_wt || (major_wt == max_major_wt && minor_wt > max_minor_wt)) { 811 best_rule = (SV*)rule; 812 max_major_wt = major_wt; 813 max_minor_wt = minor_wt; 814 } 815 } 816 } 817 } 818 819 assert(best_rule); 820 821 for (SV **ready = AvARRAY(ready_rules), **const ready_last = ready+AvFILLp(ready_rules); ready <= ready_last; ++ready) { 822 if (best_rule == SvRV(*ready)) 823 return extract_ready_rule(aTHX_ SP, ready_rules, ready, ready_last); 824 } 825 826 return SP; 827} 828 829void RuleGraph::constrain_to_rules(pTHX_ char* state_vec, AV* ready_rules, char* init_state_vec, char* final_state_vec, SV** rules_to_keep, Int n_keep) const 830{ 831 overlaid_state_adapter adapter(*this, state_vec); 832 overlaid_state_adapter init_adapter(*this, init_state_vec); 833 overlaid_state_adapter final_adapter(*this, final_state_vec); 834 835 marked_elim_nodes=range(1, graph.dim()-1); 836 for (; n_keep > 0; --n_keep, ++rules_to_keep) { 837 const Int node = rule_ref2node(*rules_to_keep); 838 if (node > 0 && init_adapter.is_alive(node)) { 839 AV* rule = rule_deputies[node]; 840 SV* rule_flags = AvARRAY(rule)[RuleDeputy_flags_index]; 841 assert(SvIOKp(rule_flags)); 842 if (!(SvIVX(rule_flags) & Rule_is_perm_action) || final_adapter.is_scheduled(node)) 843 marked_elim_nodes -= node; 844 } 845 } 846 847 for (auto unneeded = marked_elim_nodes.begin(); !unneeded.at_end(); ++unneeded) { 848 const Int node = *unneeded; 849 if (rule_deputies[node]) { 850 if (adapter.is_ready(node)) 851 remove_ready_rule(aTHX_ ready_rules, node); 852 adapter.delete_node(node); 853 for (auto consumer = graph.out_edges(node).begin(); !consumer.at_end(); ++consumer) { 854 arc_state_t& arc_state = adapter.arc_state(*consumer); 855 if (arc_state != inactive_arc) { 856 assert(arc_state != exclusive_arc); 857 const Int cons_node = consumer.to_node(); 858 if (!marked_elim_nodes.contains(cons_node) || !rule_deputies[cons_node]) { 859 assert(adapter.node_in_state(cons_node) > (rule_deputies[cons_node] ? 2*pending_supplier : 0)); 860 adapter.node_in_state(cons_node) -= pending_supplier; 861 } 862 arc_state = inactive_arc; 863 } 864 } 865 for (auto supplier = graph.in_edges(node).begin(); !supplier.at_end(); ++supplier) { 866 arc_state_t& arc_state = adapter.arc_state(*supplier); 867 if (arc_state > optional_arc) { 868 const Int supp_node = supplier.from_node(); 869 if (!marked_elim_nodes.contains(supp_node) || !rule_deputies[supp_node]) { 870 assert(adapter.node_out_state(supp_node) > 0); 871 --adapter.node_out_state(supp_node); 872 } 873 } 874 arc_state = inactive_arc; 875 } 876 } 877 } 878} 879 880bool RuleGraph::is_complete(char* state_vec) const 881{ 882 return overlaid_state_adapter(*this, state_vec).is_ready(0); 883} 884 885SV** RuleGraph::push_resolved_consumers(pTHX_ char* state_vec, SV* rule_ref) const 886{ 887 dSP; 888 overlaid_state_adapter adapter(*this, state_vec); 889 const Int source_node = rule_ref2node(rule_ref); 890 if (source_node < 0 || !adapter.is_alive(source_node)) return SP; // empty result 891 892 elim_queue.clear(); 893 elim_queue.push_back(source_node); 894 895 do { 896 const Int node = elim_queue.front(); elim_queue.pop_front(); 897 assert(adapter.is_scheduled(node)); 898 for (auto consumer = graph.out_edges(node).begin(); !consumer.at_end(); ++consumer) { 899 if (adapter.arc_state(*consumer) == resolved_arc) { 900 const Int cons_node = consumer.to_node(); 901 if (adapter.node_in_state(cons_node) & (ready_node | scheduled_node)) { 902 if (AV* cons_rule = rule_deputies[cons_node]) { 903 SV* cons_flags = AvARRAY(cons_rule)[RuleDeputy_flags_index]; 904 if (SvIVX(cons_flags) & Rule_is_perm_action) { 905 elim_queue.push_back(cons_node); 906 } else { 907 XPUSHs(sv_2mortal(newRV((SV*)cons_rule))); 908 } 909 } else { 910 elim_queue.push_back(cons_node); 911 } 912 } 913 } 914 } 915 } while (!elim_queue.empty()); 916 917 return SP; 918} 919 920SV** RuleGraph::push_resolved_suppliers(pTHX_ char* state_vec, SV* rule_ref) const 921{ 922 dSP; 923 overlaid_state_adapter adapter(*this, state_vec); 924 const Int target_node = rule_ref2node(rule_ref); 925 if (target_node < 0 || !adapter.is_alive(target_node)) return SP; // empty result 926 927 elim_queue.clear(); 928 elim_queue.push_back(target_node); 929 930 do { 931 const Int node = elim_queue.front(); elim_queue.pop_front(); 932 for (auto supplier = graph.in_edges(node).begin(); !supplier.at_end(); ++supplier) { 933 if (adapter.arc_state(*supplier) == resolved_arc) { 934 const Int supp_node = supplier.from_node(); 935 assert(adapter.is_scheduled(supp_node)); 936 if (AV* supp_rule = rule_deputies[supp_node]) { 937 SV* supp_flags = AvARRAY(supp_rule)[RuleDeputy_flags_index]; 938 if (SvIVX(supp_flags) & Rule_is_perm_action) { 939 elim_queue.push_back(supp_node); 940 } else { 941 XPUSHs(sv_2mortal(newRV((SV*)supp_rule))); 942 } 943 } else { 944 elim_queue.push_back(supp_node); 945 } 946 } 947 } 948 } while (!elim_queue.empty()); 949 950 return SP; 951} 952 953bool RuleGraph::rule_is_alive(char* state_vec, SV* rule_ref) const 954{ 955 const Int node = rule_ref2node(rule_ref); 956 return node >= 0 && overlaid_state_adapter(*this, state_vec).is_alive(node); 957} 958 959SV** RuleGraph::push_active_rules(pTHX_ char* state_vec) const 960{ 961 dSP; 962 EXTEND(SP, graph.dim()); 963 964 overlaid_state_adapter adapter(*this, state_vec); 965 for (auto node_it = entire(nodes(graph)); !node_it.at_end(); ++node_it) { 966 const Int node = node_it.index(); 967 if (adapter.is_alive(node) && !adapter.is_scheduled(node) && rule_deputies[node]) 968 PUSHs(sv_2mortal(newRV((SV*)rule_deputies[node]))); 969 } 970 971 return SP; 972} 973 974SV** RuleGraph::push_active_suppliers(pTHX_ char* state_vec, SV* rule_ref) const 975{ 976 dSP; 977 const Int node = rule_ref2node(rule_ref); 978 assert(node >= 0); 979 EXTEND(SP, graph.in_degree(node)); 980 981 overlaid_state_adapter adapter(*this, state_vec); 982 for (auto supplier = graph.in_edges(node).begin(); !supplier.at_end(); ++supplier) { 983 if (adapter.arc_state(*supplier) != inactive_arc) 984 mPUSHi(supplier.from_node()); 985 } 986 987 return SP; 988} 989 990SV** RuleGraph::push_active_consumers(pTHX_ char* state_vec, SV* rule_ref) const 991{ 992 dSP; 993 const Int node = rule_ref2node(rule_ref); 994 assert(node >= 0); 995 EXTEND(SP, graph.out_degree(node)); 996 997 overlaid_state_adapter adapter(*this, state_vec); 998 for (auto consumer = graph.out_edges(node).begin(); !consumer.at_end(); ++consumer) { 999 if (adapter.arc_state(*consumer) != inactive_arc) 1000 mPUSHi(consumer.to_node()); 1001 } 1002 1003 return SP; 1004} 1005 1006 1007SV* RuleGraph::class_descr = nullptr; 1008int RuleGraph::RuleChain_rgr_index = 0; 1009int RuleGraph::RuleChain_rgr_state_index = 0; 1010int RuleGraph::RuleChain_ready_rules_index = 0; 1011int RuleGraph::RuleDeputy_rgr_node_index = 0; 1012int RuleGraph::RuleDeputy_flags_index = 0; 1013int RuleGraph::RuleDeputy_weight_index = 0; 1014int RuleGraph::Rule_is_precondition = 0; 1015int RuleGraph::Rule_is_perm_action = 0; 1016 1017} } 1018 1019using namespace pm::perl; 1020using namespace pm::perl::glue; 1021using polymake::Int; 1022 1023#define RetrieveGraphArg(...) \ 1024 MAGIC* mg=get_cpp_magic(SvRV(self)); \ 1025 __VA_ARGS__ RuleGraph* rgr=reinterpret_cast<__VA_ARGS__ RuleGraph*>(mg->mg_ptr) 1026 1027#define RetrieveChainGraph(...) \ 1028 SV** const chain_body=PmArray(chain); \ 1029 SV* const self=chain_body[RuleGraph::RuleChain_rgr_index]; \ 1030 RetrieveGraphArg(__VA_ARGS__) 1031 1032#define RetrieveState() \ 1033 SV* const state=chain_body[RuleGraph::RuleChain_rgr_state_index] 1034 1035#define RetrieveReadyRules() \ 1036 AV* ready_rules=(AV*)SvRV(chain_body[RuleGraph::RuleChain_ready_rules_index]) 1037 1038MODULE = Polymake::Core::Scheduler::RuleGraph PACKAGE = Polymake::Core::Scheduler::RuleGraph 1039 1040PROTOTYPES: DISABLE 1041 1042void new(SV* pkg) 1043PPCODE: 1044{ 1045 using polymake::AnyString; 1046 1047 if (!RuleGraph::class_descr) { 1048 // this initialization can't be done in the BOOT block because CPlusPlus is not yet initialized that early 1049 RuleGraph::class_descr = OpaqueClassRegistrator<RuleGraph>::register_it("Polymake::Core::Scheduler::RuleGraph", nullptr, nullptr); 1050 RuleGraph::RuleChain_rgr_index = CvDEPTH(get_cv("Polymake::Core::Scheduler::TentativeRuleChain::rgr", false)); 1051 RuleGraph::RuleChain_rgr_state_index = CvDEPTH(get_cv("Polymake::Core::Scheduler::TentativeRuleChain::rgr_state", false)); 1052 RuleGraph::RuleChain_ready_rules_index = CvDEPTH(get_cv("Polymake::Core::Scheduler::TentativeRuleChain::ready", false)); 1053 RuleGraph::RuleDeputy_rgr_node_index = CvDEPTH(get_cv("Polymake::Core::Scheduler::RuleDeputy::rgr_node", false)); 1054 RuleGraph::RuleDeputy_flags_index = CvDEPTH(get_cv("Polymake::Core::Rule::Deputy::flags", false)); 1055 RuleGraph::RuleDeputy_weight_index = CvDEPTH(get_cv("Polymake::Core::Rule::Deputy::weight", false)); 1056 1057 sv_setiv(get_sv("Polymake::Core::Scheduler::rgr_inactive_arc", false), RuleGraph::inactive_arc); 1058 sv_setiv(get_sv("Polymake::Core::Scheduler::rgr_weak_arc", false), RuleGraph::weak_arc); 1059 sv_setiv(get_sv("Polymake::Core::Scheduler::rgr_initial_arc", false), RuleGraph::initial_arc); 1060 sv_setiv(get_sv("Polymake::Core::Scheduler::rgr_exclusive_arc", false), RuleGraph::exclusive_arc); 1061 sv_setiv(get_sv("Polymake::Core::Scheduler::rgr_unique_arc", false), RuleGraph::unique_arc); 1062 sv_setiv(get_sv("Polymake::Core::Scheduler::rgr_resolved_arc", false), RuleGraph::resolved_arc); 1063 sv_setiv(get_sv("Polymake::Core::Scheduler::rgr_source_arc", false), RuleGraph::source_arc); 1064 1065 HV* RuleFlags_stash = get_named_stash(aTHX_ "Polymake::Core::Rule::Flags"); 1066 RuleGraph::Rule_is_precondition = get_named_constant(aTHX_ RuleFlags_stash, "is_precondition"); 1067 RuleGraph::Rule_is_perm_action = get_named_constant(aTHX_ RuleFlags_stash, "is_perm_action"); 1068 } 1069 SV* ref = newSV_type(SVt_NULL); 1070 MAGIC* mg = glue::allocate_canned_magic(aTHX_ ref, RuleGraph::class_descr, ValueFlags::alloc_magic, 0); 1071 new(mg->mg_ptr) RuleGraph(); 1072 PUSHs(sv_2mortal(ref)); 1073 PERL_UNUSED_ARG(pkg); 1074} 1075 1076void add_node(SV* self, ...) 1077PPCODE: 1078{ 1079 dTARGET; 1080 RetrieveGraphArg(); 1081 const Int node = rgr->add_node(aTHX_ items == 2 ? (AV*)SvRV(ST(1)) : nullptr); 1082 if (items == 1) PUSHi(node); 1083} 1084 1085void add_arc(SV* self, SV* from, SV* to, SV* arc_state) 1086PPCODE: 1087{ 1088 RetrieveGraphArg(); 1089 SV* const from_node_sv=SvROK(from) ? PmArray(from)[RuleGraph::RuleDeputy_rgr_node_index] : from; 1090 SV* const to_node_sv=SvROK(to) ? PmArray(to)[RuleGraph::RuleDeputy_rgr_node_index] : to; 1091 if (!SvIOKp(from_node_sv)) Perl_croak(aTHX_ "add_arc: invalid from node"); 1092 if (!SvIOKp(to_node_sv)) Perl_croak(aTHX_ "add_arc: invalid to node"); 1093 if (!SvIOKp(arc_state)) Perl_croak(aTHX_ "add_arc: invalid arc code"); 1094 rgr->add_arc(SvIVX(from_node_sv), SvIVX(to_node_sv), RuleGraph::arc_state_t(SvIVX(arc_state))); 1095} 1096 1097MODULE = Polymake::Core::Scheduler::RuleGraph PACKAGE = Polymake::Core::Scheduler::TentativeRuleChain 1098 1099void finalize_gather(SV* chain, SV* tell_eliminated, ...) 1100PPCODE: 1101{ 1102 RetrieveChainGraph(); 1103 RetrieveState(); 1104 RetrieveReadyRules(); 1105 SV* tell_sv=SvROK(tell_eliminated) ? SvRV(tell_eliminated) : nullptr; 1106 if (items>2 && !rgr->eliminate_after_gather(aTHX_ tell_sv, &ST(2), items-2)) 1107 XSRETURN_NO; 1108 const size_t state_size=rgr->state_vector_size(); 1109 sv_grow(state, state_size); 1110 SvPOK_on(state); 1111 SvCUR_set(state, state_size); 1112 rgr->init_state(aTHX_ SvPVX(state), ready_rules); 1113 PUSHs(&PL_sv_yes); 1114} 1115 1116void eliminate(SV* chain, SV* max_optional_state, ...) 1117PPCODE: 1118{ 1119 const int first_rule_arg = 2; 1120 if (items == first_rule_arg) XSRETURN_YES; 1121 RetrieveChainGraph(const); 1122 RetrieveState(); 1123 RetrieveReadyRules(); 1124 assert(SvPOKp(state)); 1125 assert(SvIOK(max_optional_state) && SvIVX(max_optional_state) <= RuleGraph::optional_arc); 1126 if (rgr->eliminate_in_variant(aTHX_ SvPVX(state), static_cast<RuleGraph::arc_state_t>(SvIVX(max_optional_state)), 1127 ready_rules, &ST(first_rule_arg), items-first_rule_arg)) 1128 PUSHs(&PL_sv_yes); 1129 else 1130 PUSHs(&PL_sv_no); 1131} 1132 1133void add_scheduled_rule(SV* chain, SV* rule_to_add, I32 enforced, ...) 1134PPCODE: 1135{ 1136 RetrieveChainGraph(const); 1137 RetrieveState(); 1138 RetrieveReadyRules(); 1139 assert(SvPOKp(state)); 1140 if (rgr->add_scheduled_rule(aTHX_ SvPVX(state), ready_rules, rule_to_add, enforced, items == 4 ? ST(3) : rule_to_add)) 1141 PUSHs(&PL_sv_yes); 1142 else 1143 PUSHs(&PL_sv_no); 1144} 1145 1146void constrain_to_rules(SV* chain, SV* init_chain, SV* final_chain, ...) 1147PPCODE: 1148{ 1149 RetrieveChainGraph(const); 1150 RetrieveState(); 1151 RetrieveReadyRules(); 1152 assert(SvPOKp(state)); 1153 SV* const init_state=PmArray(init_chain)[RuleGraph::RuleChain_rgr_state_index]; 1154 SV* const final_state=PmArray(final_chain)[RuleGraph::RuleChain_rgr_state_index]; 1155 assert(SvPOKp(init_state)); 1156 assert(SvPOKp(final_state)); 1157 rgr->constrain_to_rules(aTHX_ SvPVX(state), ready_rules, SvPVX(init_state), SvPVX(final_state), &ST(3), items-3); 1158} 1159 1160void rule_is_alive(SV* chain, SV* rule) 1161PPCODE: 1162{ 1163 RetrieveChainGraph(); 1164 RetrieveState(); 1165 assert(SvPOKp(state)); 1166 if (rgr->rule_is_alive(SvPVX(state), rule)) 1167 PUSHs(&PL_sv_yes); 1168 else 1169 PUSHs(&PL_sv_no); 1170} 1171 1172void rule_is_ready_to_use(SV* chain, SV* rule) 1173PPCODE: 1174{ 1175 RetrieveChainGraph(); 1176#ifndef NDEBUG 1177 RetrieveState(); 1178 assert(!SvOK(state)); 1179#endif 1180 if (rgr->rule_is_ready_to_use(aTHX_ rule)) 1181 PUSHs(&PL_sv_yes); 1182 else 1183 PUSHs(&PL_sv_no); 1184} 1185 1186void is_complete(SV* chain) 1187PPCODE: 1188{ 1189 RetrieveChainGraph(const); 1190 RetrieveState(); 1191 assert(SvPOKp(state)); 1192 if (rgr->is_complete(SvPVX(state))) 1193 PUSHs(&PL_sv_yes); 1194 else 1195 PUSHs(&PL_sv_no); 1196} 1197 1198void select_ready_rule(SV* chain) 1199PPCODE: 1200{ 1201 RetrieveChainGraph(const); 1202 RetrieveState(); 1203 RetrieveReadyRules(); 1204 assert(SvPOKp(state) && AvFILLp(ready_rules)>0); 1205 PUTBACK; 1206 SP=rgr->select_ready_rule(aTHX_ SvPVX(state), ready_rules); 1207} 1208 1209void get_resolved_suppliers(SV* chain, SV* rule) 1210PPCODE: 1211{ 1212 RetrieveChainGraph(const); 1213 RetrieveState(); 1214 assert(SvPOKp(state)); 1215 PUTBACK; 1216 SP=rgr->push_resolved_suppliers(aTHX_ SvPVX(state), rule); 1217} 1218 1219void get_resolved_consumers(SV* chain, SV* rule) 1220PPCODE: 1221{ 1222 RetrieveChainGraph(const); 1223 RetrieveState(); 1224 assert(SvPOKp(state)); 1225 PUTBACK; 1226 SP=rgr->push_resolved_consumers(aTHX_ SvPVX(state), rule); 1227} 1228 1229void get_active_rules(SV* chain) 1230PPCODE: 1231{ 1232 RetrieveChainGraph(const); 1233 RetrieveState(); 1234 assert(SvPOKp(state)); 1235 PUTBACK; 1236 SP=rgr->push_active_rules(aTHX_ SvPVX(state)); 1237} 1238 1239void get_active_supplier_nodes(SV* chain, SV* rule) 1240PPCODE: 1241{ 1242 RetrieveChainGraph(const); 1243 RetrieveState(); 1244 assert(SvPOKp(state)); 1245 PUTBACK; 1246 SP=rgr->push_active_suppliers(aTHX_ SvPVX(state), rule); 1247} 1248 1249void get_active_consumer_nodes(SV* chain, SV* rule) 1250PPCODE: 1251{ 1252 RetrieveChainGraph(const); 1253 RetrieveState(); 1254 assert(SvPOKp(state)); 1255 PUTBACK; 1256 SP=rgr->push_active_consumers(aTHX_ SvPVX(state), rule); 1257} 1258 1259=pod 1260// Local Variables: 1261// mode:C++ 1262// c-basic-offset:3 1263// indent-tabs-mode:nil 1264// End: 1265=cut 1266