1package Marpa::Internal::Recce_Value; 2 3use 5.010; 4use warnings; 5use strict; 6use integer; 7 8use English qw( -no_match_vars ); 9use Marpa::Internal::Carp_Not; 10 11# This perlcritic check is broken as of 9 Aug 2010 12## no critic (TestingAndDebugging::ProhibitNoWarnings) 13no warnings qw(qw); 14## use critic 15 16use Marpa::Offset qw( 17 18 :package=Marpa::Internal::Or_Node 19 20 ID 21 TAG 22 ITEMS 23 RULE_ID 24 POSITION 25 AND_NODE_IDS 26 27 SOURCE_OR_NODE { The name of the first grandparent or-node, 28 for keeping track while populating the ITEMS element } 29 30 CYCLE { Can this Or node be part of a cycle? } 31 32 INITIAL_RANK_REF 33 34 =LAST_FIELD 35); 36 37use Marpa::Offset qw( 38 39 :package=Marpa::Internal::And_Node 40 41 ID 42 TAG 43 RULE_ID 44 TOKEN_NAME 45 VALUE_REF 46 VALUE_OPS 47 48 { Fields before this (except ID) 49 are used in evaluate() } 50 51 PREDECESSOR_ID 52 CAUSE_ID 53 54 CAUSE_EARLEME 55 56 INITIAL_RANK_REF 57 CONSTANT_RANK_REF 58 TOKEN_RANK_REF 59 60 { These earleme positions will be needed for the callbacks: } 61 62 START_EARLEME 63 END_EARLEME 64 65 POSITION { This is only used for diagnostics, but 66 diagnostics are important. } 67 68 =LAST_FIELD 69 70); 71 72use Marpa::Offset qw( 73 74 :package=Marpa::Internal::Iteration_Node 75 76 OR_NODE { The or-node } 77 78 CHOICES { 79 A list of remaining choices of and-node. 80 The current choice is first in the list. 81 } 82 83 PARENT { Offset of the parent in the iterations stack } 84 85 CAUSE_IX { Offset of the cause child, if any } 86 PREDECESSOR_IX { Offset of the predecessor child, if any } 87 { IX value is -1 if IX needs to be recalculated } 88 89 CHILD_TYPE { Cause or Predecessor } 90 91 RANK { Current rank } 92 CLEAN { Boolean -- true if rank does not need to 93 be recalculated } 94 95); 96 97use Marpa::Offset qw( 98 99 :package=Marpa::Internal::Task 100 101 INITIALIZE 102 POPULATE_OR_NODE 103 POPULATE_DEPTH 104 105 RANK_ALL 106 GRAFT_SUBTREE 107 108 ITERATE 109 FIX_TREE 110 STACK_INODE 111 CHECK_FOR_CYCLE 112 113); 114 115use Marpa::Offset qw( 116 117 :package=Marpa::Internal::Op 118 119 :{ These are the valuation-time ops } 120 ARGC 121 CALL 122 CONSTANT_RESULT 123 VIRTUAL_HEAD 124 VIRTUAL_HEAD_NO_SEP 125 VIRTUAL_KERNEL 126 VIRTUAL_TAIL 127 128); 129 130use Marpa::Offset qw( 131 132 :package=Marpa::Internal::Choice 133 134 { These are the valuation-time ops } 135 136 AND_NODE 137 RANK { *NOT* a rank ref } 138 ITERATION_SUBTREE 139 140); 141 142use constant SKIP => -1; 143 144use warnings; 145 146sub Marpa::Recognizer::show_recce_and_node { 147 my ( $recce, $and_node, $verbose ) = @_; 148 $verbose //= 0; 149 150 my $text = "show_recce_and_node:\n"; 151 152 my $grammar = $recce->[Marpa::Internal::Recognizer::GRAMMAR]; 153 my $rules = $grammar->[Marpa::Internal::Grammar::RULES]; 154 155 my $name = $and_node->[Marpa::Internal::And_Node::TAG]; 156 my $id = $and_node->[Marpa::Internal::And_Node::ID]; 157 my $predecessor_id = 158 $and_node->[Marpa::Internal::And_Node::PREDECESSOR_ID]; 159 my $cause_id = $and_node->[Marpa::Internal::And_Node::CAUSE_ID]; 160 my $value_ref = $and_node->[Marpa::Internal::And_Node::VALUE_REF]; 161 my $rule_id = $and_node->[Marpa::Internal::And_Node::RULE_ID]; 162 my $position = $and_node->[Marpa::Internal::And_Node::POSITION]; 163 164 my @rhs = (); 165 166 my $rule = $rules->[$rule_id]; 167 my $original_rule = $rule->[Marpa::Internal::Rule::ORIGINAL_RULE] 168 // $rule; 169 my $is_virtual_rule = $rule != $original_rule; 170 171 my $or_nodes = $recce->[Marpa::Internal::Recognizer::OR_NODES]; 172 173 my $predecessor; 174 if ($predecessor_id) { 175 $predecessor = $or_nodes->[$predecessor_id]; 176 177 push @rhs, $predecessor->[Marpa::Internal::Or_Node::TAG] 178 . "o$predecessor_id"; 179 } # predecessor 180 181 my $cause; 182 if ($cause_id) { 183 $cause = $or_nodes->[$cause_id]; 184 push @rhs, $cause->[Marpa::Internal::Or_Node::TAG] . "o$cause_id"; 185 } # cause 186 187 if ( defined $value_ref ) { 188 my $value_as_string = 189 Data::Dumper->new( [$value_ref] )->Terse(1)->Dump; 190 chomp $value_as_string; 191 push @rhs, $value_as_string; 192 } # value 193 194 $text .= "R$rule_id:$position" . "a$id -> " . join( q{ }, @rhs ) . "\n"; 195 196 SHOW_RULE: { 197 if ( $is_virtual_rule and $verbose >= 2 ) { 198 $text 199 .= ' rule ' 200 . $rule->[Marpa::Internal::Rule::ID] . ': ' 201 . Marpa::show_dotted_rule( $rule, $position + 1 ) 202 . "\n " 203 . Marpa::brief_virtual_rule( $rule, $position + 1 ) . "\n"; 204 last SHOW_RULE; 205 } ## end if ( $is_virtual_rule and $verbose >= 2 ) 206 207 last SHOW_RULE if not $verbose; 208 $text 209 .= ' rule ' 210 . $rule->[Marpa::Internal::Rule::ID] . ': ' 211 . Marpa::brief_virtual_rule( $rule, $position + 1 ) . "\n"; 212 213 } ## end SHOW_RULE: 214 215 if ( $verbose >= 2 ) { 216 my @comment = (); 217 if ( $and_node->[Marpa::Internal::And_Node::VALUE_OPS] ) { 218 push @comment, 'value_ops'; 219 } 220 if ( scalar @comment ) { 221 $text .= q{ } . ( join q{, }, @comment ) . "\n"; 222 } 223 } ## end if ( $verbose >= 2 ) 224 225 return $text; 226 227} ## end sub Marpa::Recognizer::show_recce_and_node 228 229sub Marpa::Recognizer::show_recce_or_node { 230 my ( $recce, $or_node, $verbose, ) = @_; 231 $verbose //= 0; 232 233 my $grammar = $recce->[Marpa::Internal::Recognizer::GRAMMAR]; 234 my $rules = $grammar->[Marpa::Internal::Grammar::RULES]; 235 my $rule_id = $or_node->[Marpa::Internal::Or_Node::RULE_ID]; 236 my $position = $or_node->[Marpa::Internal::Or_Node::POSITION]; 237 my $or_node_id = $or_node->[Marpa::Internal::Or_Node::ID]; 238 my $or_node_tag = $or_node->[Marpa::Internal::Or_Node::TAG]; 239 240 my $text = "show_recce_or_node o$or_node_id:\n"; 241 242 my $rule = $rules->[$rule_id]; 243 my $original_rule = $rule->[Marpa::Internal::Rule::ORIGINAL_RULE] 244 // $rule; 245 my $is_virtual_rule = $rule != $original_rule; 246 247 my $and_nodes = $recce->[Marpa::Internal::Recognizer::AND_NODES]; 248 249 LIST_AND_NODES: { 250 my $and_node_ids = $or_node->[Marpa::Internal::Or_Node::AND_NODE_IDS]; 251 if ( not defined $and_node_ids ) { 252 $text .= $or_node_tag . "o$or_node_id: UNPOPULATED\n"; 253 last LIST_AND_NODES; 254 } 255 if ( not scalar @{$and_node_ids} ) { 256 $text .= $or_node_tag . "o$or_node_id: Empty and-node list!\n"; 257 last LIST_AND_NODES; 258 } 259 for my $index ( 0 .. $#{$and_node_ids} ) { 260 my $and_node_id = $and_node_ids->[$index]; 261 my $and_node = $and_nodes->[$and_node_id]; 262 my $and_node_tag = $or_node_tag . "a$and_node_id"; 263 if ( $verbose >= 2 ) { 264 $text .= $or_node_tag 265 . "o$or_node_id: $or_node_tag -> $and_node_tag\n"; 266 } 267 $text .= $recce->show_recce_and_node( $and_node, $verbose ); 268 } ## end for my $index ( 0 .. $#{$and_node_ids} ) 269 } ## end LIST_AND_NODES: 270 271 SHOW_RULE: { 272 if ( $is_virtual_rule and $verbose >= 2 ) { 273 $text 274 .= ' rule ' 275 . $rule->[Marpa::Internal::Rule::ID] . ': ' 276 . Marpa::show_dotted_rule( $rule, $position + 1 ) 277 . "\n " 278 . Marpa::brief_virtual_rule( $rule, $position + 1 ) . "\n"; 279 last SHOW_RULE; 280 } ## end if ( $is_virtual_rule and $verbose >= 2 ) 281 282 last SHOW_RULE if not $verbose; 283 $text 284 .= ' rule ' 285 . $rule->[Marpa::Internal::Rule::ID] . ': ' 286 . Marpa::brief_virtual_rule( $rule, $position + 1 ) . "\n"; 287 288 } ## end SHOW_RULE: 289 290 return $text; 291 292} ## end sub Marpa::Recognizer::show_recce_or_node 293 294sub Marpa::brief_iteration_node { 295 my ($iteration_node) = @_; 296 297 my $or_node = $iteration_node->[Marpa::Internal::Iteration_Node::OR_NODE]; 298 my $or_node_id = $or_node->[Marpa::Internal::Or_Node::ID]; 299 my $and_node_ids = $or_node->[Marpa::Internal::Or_Node::AND_NODE_IDS]; 300 my $text = "o$or_node_id"; 301 DESCRIBE_CHOICES: { 302 if ( not defined $and_node_ids ) { 303 $text .= ' UNPOPULATED'; 304 last DESCRIBE_CHOICES; 305 } 306 my $choices = 307 $iteration_node->[Marpa::Internal::Iteration_Node::CHOICES]; 308 if ( not defined $choices ) { 309 $text .= ' Choices not initialized'; 310 last DESCRIBE_CHOICES; 311 } 312 my $choice = $choices->[0]; 313 if ( defined $choice ) { 314 $text 315 .= " [$choice] == a" 316 . $choice->[Marpa::Internal::Choice::AND_NODE] 317 ->[Marpa::Internal::And_Node::ID]; 318 last DESCRIBE_CHOICES; 319 } ## end if ( defined $choice ) 320 $text .= "o$or_node_id has no choices left"; 321 } ## end DESCRIBE_CHOICES: 322 my $parent_ix = $iteration_node->[Marpa::Internal::Iteration_Node::PARENT] 323 // q{-}; 324 return "$text; p=$parent_ix"; 325} ## end sub Marpa::brief_iteration_node 326 327sub Marpa::show_rank_ref { 328 my ($rank_ref) = @_; 329 return 'undef' if not defined $rank_ref; 330 return 'SKIP' if $rank_ref == Marpa::Internal::Recce_Value::SKIP; 331 return ${$rank_ref}; 332} ## end sub Marpa::show_rank_ref 333 334sub Marpa::Recognizer::show_iteration_node { 335 my ( $recce, $iteration_node, $verbose ) = @_; 336 337 my $or_node = $iteration_node->[Marpa::Internal::Iteration_Node::OR_NODE]; 338 my $or_node_id = $or_node->[Marpa::Internal::Or_Node::ID]; 339 my $or_node_tag = $or_node->[Marpa::Internal::Or_Node::TAG]; 340 my $text = "o$or_node_id $or_node_tag; "; 341 given ( $iteration_node->[Marpa::Internal::Iteration_Node::CHILD_TYPE] ) { 342 when (Marpa::Internal::And_Node::CAUSE_ID) { 343 $text .= 'cause ' 344 } 345 when (Marpa::Internal::And_Node::PREDECESSOR_ID) { 346 $text .= 'predecessor ' 347 } 348 default { 349 $text .= '- ' 350 } 351 } ## end given 352 353 $text 354 .= 'pr=' 355 . ( $iteration_node->[Marpa::Internal::Iteration_Node::PREDECESSOR_IX] 356 // q{-} ) 357 . q{;c=} 358 . ( $iteration_node->[Marpa::Internal::Iteration_Node::CAUSE_IX] 359 // q{-} ) 360 . q{;p=} 361 . ( $iteration_node->[Marpa::Internal::Iteration_Node::PARENT] 362 // q{-} ) 363 . q{; rank=} 364 . ( $iteration_node->[Marpa::Internal::Iteration_Node::RANK] 365 // 'undef' ) 366 . ( 367 $iteration_node->[Marpa::Internal::Iteration_Node::CLEAN] 368 ? q{} 369 : ' (dirty)' 370 ) . "\n"; 371 372 DESCRIBE_CHOICES: { 373 my $and_node_ids = $or_node->[Marpa::Internal::Or_Node::AND_NODE_IDS]; 374 if ( not defined $and_node_ids ) { 375 $text .= " UNPOPULATED\n"; 376 last DESCRIBE_CHOICES; 377 } 378 my $choices = 379 $iteration_node->[Marpa::Internal::Iteration_Node::CHOICES]; 380 if ( not defined $choices ) { 381 $text .= " Choices not initialized\n"; 382 last DESCRIBE_CHOICES; 383 } 384 if ( not scalar @{$choices} ) { 385 $text .= " has no choices left\n"; 386 last DESCRIBE_CHOICES; 387 } 388 for my $choice_ix ( 0 .. $#{$choices} ) { 389 my $choice = $choices->[$choice_ix]; 390 $text .= " o$or_node_id" . '[' . $choice_ix . '] '; 391 my $and_node = $choice->[Marpa::Internal::Choice::AND_NODE]; 392 my $and_node_tag = $and_node->[Marpa::Internal::And_Node::TAG]; 393 my $and_node_id = $and_node->[Marpa::Internal::And_Node::ID]; 394 $text .= " ::= a$and_node_id $and_node_tag"; 395 no integer; 396 if ($verbose) { 397 $text 398 .= q{; rank=} . $choice->[Marpa::Internal::Choice::RANK]; 399 if ( my $saved_subtree = 400 $choice->[Marpa::Internal::Choice::ITERATION_SUBTREE] ) 401 { 402 $text 403 .= q{; } 404 . ( scalar @{$saved_subtree} ) 405 . ' nodes saved'; 406 } ## end if ( my $saved_subtree = $choice->[...]) 407 } ## end if ($verbose) 408 $text .= "\n"; 409 last CHOICE if not $verbose; 410 } ## end for my $choice_ix ( 0 .. $#{$choices} ) 411 } ## end DESCRIBE_CHOICES: 412 return $text; 413} ## end sub Marpa::Recognizer::show_iteration_node 414 415sub Marpa::Recognizer::show_iteration_stack { 416 my ( $recce, $verbose ) = @_; 417 my $iteration_stack = 418 $recce->[Marpa::Internal::Recognizer::ITERATION_STACK]; 419 my $text = q{}; 420 for my $ix ( 0 .. $#{$iteration_stack} ) { 421 my $iteration_node = $iteration_stack->[$ix]; 422 $text .= "$ix: " 423 . $recce->show_iteration_node( $iteration_node, $verbose ); 424 } 425 return $text; 426} ## end sub Marpa::Recognizer::show_iteration_stack 427 428package Marpa::Internal::Recognizer; 429our $DEFAULT_ACTION_VALUE = \undef; 430 431package Marpa::Internal::Recce_Value; 432 433sub Marpa::Internal::Recognizer::set_null_values { 434 my ($recce) = @_; 435 my $grammar = $recce->[Marpa::Internal::Recognizer::GRAMMAR]; 436 my $trace_values = $recce->[Marpa::Internal::Recognizer::TRACE_VALUES]; 437 438 my $rules = $grammar->[Marpa::Internal::Grammar::RULES]; 439 my $symbols = $grammar->[Marpa::Internal::Grammar::SYMBOLS]; 440 my $default_null_value = 441 $grammar->[Marpa::Internal::Grammar::DEFAULT_NULL_VALUE]; 442 443 my $null_values; 444 $#{$null_values} = $#{$symbols}; 445 446 SYMBOL: for my $symbol ( @{$symbols} ) { 447 next SYMBOL if not $symbol->[Marpa::Internal::Symbol::NULLING]; 448 449 my $null_value = undef; 450 if ( $symbol->[Marpa::Internal::Symbol::NULL_VALUE] ) { 451 $null_value = ${ $symbol->[Marpa::Internal::Symbol::NULL_VALUE] }; 452 } 453 else { 454 $null_value = $default_null_value; 455 } 456 next SYMBOL if not defined $null_value; 457 458 my $symbol_id = $symbol->[Marpa::Internal::Symbol::ID]; 459 $null_values->[$symbol_id] = $null_value; 460 461 if ($trace_values) { 462 print {$Marpa::Internal::TRACE_FH} 463 'Setting null value for symbol ', 464 $symbol->[Marpa::Internal::Symbol::NAME], 465 ' to ', Data::Dumper->new( [ \$null_value ] )->Terse(1)->Dump 466 or Marpa::exception('Could not print to trace file'); 467 } ## end if ($trace_values) 468 469 } ## end for my $symbol ( @{$symbols} ) 470 471 return $null_values; 472 473} # set_null_values 474 475# Given the grammar and an action name, resolve it to a closure, 476# or return undef 477sub Marpa::Internal::Recognizer::resolve_semantics { 478 my ( $recce, $closure_name ) = @_; 479 my $grammar = $recce->[Marpa::Internal::Recognizer::GRAMMAR]; 480 my $closures = $recce->[Marpa::Internal::Recognizer::CLOSURES]; 481 my $trace_actions = $recce->[Marpa::Internal::Recognizer::TRACE_ACTIONS]; 482 483 Marpa::exception(q{Trying to resolve 'undef' as closure name}) 484 if not defined $closure_name; 485 486 if ( my $closure = $closures->{$closure_name} ) { 487 if ($trace_actions) { 488 print {$Marpa::Internal::TRACE_FH} 489 qq{Resolved "$closure_name" to explicit closure\n} 490 or Marpa::exception('Could not print to trace file'); 491 } 492 493 return $closure; 494 } ## end if ( my $closure = $closures->{$closure_name} ) 495 496 my $fully_qualified_name; 497 DETERMINE_FULLY_QUALIFIED_NAME: { 498 if ( $closure_name =~ /([:][:])|[']/xms ) { 499 $fully_qualified_name = $closure_name; 500 last DETERMINE_FULLY_QUALIFIED_NAME; 501 } 502 if (defined( 503 my $actions_package = 504 $grammar->[Marpa::Internal::Grammar::ACTIONS] 505 ) 506 ) 507 { 508 $fully_qualified_name = $actions_package . q{::} . $closure_name; 509 last DETERMINE_FULLY_QUALIFIED_NAME; 510 } ## end if ( defined( my $actions_package = $grammar->[...])) 511 512 if (defined( 513 my $action_object_class = 514 $grammar->[Marpa::Internal::Grammar::ACTION_OBJECT] 515 ) 516 ) 517 { 518 $fully_qualified_name = 519 $action_object_class . q{::} . $closure_name; 520 } ## end if ( defined( my $action_object_class = $grammar->[...])) 521 } ## end DETERMINE_FULLY_QUALIFIED_NAME: 522 523 return if not defined $fully_qualified_name; 524 525 no strict 'refs'; 526 my $closure = *{$fully_qualified_name}{'CODE'}; 527 use strict 'refs'; 528 529 if ($trace_actions) { 530 print {$Marpa::Internal::TRACE_FH} 531 ( $closure ? 'Successful' : 'Failed' ) 532 . qq{ resolution of "$closure_name" }, 533 'to ', $fully_qualified_name, "\n" 534 or Marpa::exception('Could not print to trace file'); 535 } ## end if ($trace_actions) 536 537 return $closure; 538 539} ## end sub Marpa::Internal::Recognizer::resolve_semantics 540 541sub Marpa::Internal::Recognizer::set_actions { 542 my ($recce) = @_; 543 my $grammar = $recce->[Marpa::Internal::Recognizer::GRAMMAR]; 544 545 my ( $rules, $default_action, ) = @{$grammar}[ 546 Marpa::Internal::Grammar::RULES, 547 Marpa::Internal::Grammar::DEFAULT_ACTION, 548 ]; 549 550 my $evaluator_rules = []; 551 552 my $default_action_closure; 553 if ( defined $default_action ) { 554 $default_action_closure = 555 Marpa::Internal::Recognizer::resolve_semantics( $recce, 556 $default_action ); 557 Marpa::exception( 558 "Could not resolve default action named '$default_action'") 559 if not $default_action_closure; 560 } ## end if ( defined $default_action ) 561 562 RULE: for my $rule ( @{$rules} ) { 563 564 next RULE if not $rule->[Marpa::Internal::Rule::USED]; 565 566 my $rule_id = $rule->[Marpa::Internal::Rule::ID]; 567 my $ops = $evaluator_rules->[$rule_id] = []; 568 569 my $virtual_rhs = $rule->[Marpa::Internal::Rule::VIRTUAL_RHS]; 570 my $virtual_lhs = $rule->[Marpa::Internal::Rule::VIRTUAL_LHS]; 571 572 if ($virtual_lhs) { 573 push @{$ops}, 574 ( 575 $virtual_rhs 576 ? Marpa::Internal::Op::VIRTUAL_KERNEL 577 : Marpa::Internal::Op::VIRTUAL_TAIL 578 ), 579 $rule->[Marpa::Internal::Rule::REAL_SYMBOL_COUNT]; 580 next RULE; 581 } ## end if ($virtual_lhs) 582 583 # If we are here the LHS is real, not virtual 584 585 if ($virtual_rhs) { 586 push @{$ops}, 587 ( 588 $rule->[Marpa::Internal::Rule::DISCARD_SEPARATION] 589 ? Marpa::Internal::Op::VIRTUAL_HEAD_NO_SEP 590 : Marpa::Internal::Op::VIRTUAL_HEAD 591 ), 592 $rule->[Marpa::Internal::Rule::REAL_SYMBOL_COUNT]; 593 } ## end if ($virtual_rhs) 594 # assignment instead of comparison is deliberate 595 elsif ( my $argc = scalar @{ $rule->[Marpa::Internal::Rule::RHS] } ) { 596 push @{$ops}, Marpa::Internal::Op::ARGC, $argc; 597 } 598 599 if ( my $action = $rule->[Marpa::Internal::Rule::ACTION] ) { 600 my $closure = 601 Marpa::Internal::Recognizer::resolve_semantics( $recce, 602 $action ); 603 604 Marpa::exception(qq{Could not resolve action name: "$action"}) 605 if not defined $closure; 606 push @{$ops}, Marpa::Internal::Op::CALL, $closure; 607 next RULE; 608 } ## end if ( my $action = $rule->[Marpa::Internal::Rule::ACTION...]) 609 610 # Try to resolve the LHS as a closure name, 611 # if it is not internal. 612 # If we can't resolve 613 # the LHS as a closure name, it's not 614 # a fatal error. 615 if ( my $action = 616 $rule->[Marpa::Internal::Rule::LHS] 617 ->[Marpa::Internal::Symbol::NAME] ) 618 { 619 if ($action !~ /[\]] \z/xms 620 and defined( 621 my $closure = 622 Marpa::Internal::Recognizer::resolve_semantics( 623 $recce, $action 624 ) 625 ) 626 ) 627 { 628 push @{$ops}, Marpa::Internal::Op::CALL, $closure; 629 next RULE; 630 } ## end if ( $action !~ /[\]] \z/xms and defined( my $closure...)[) 631 } ## end if ( my $action = $rule->[Marpa::Internal::Rule::LHS...]) 632 633 if ( defined $default_action_closure ) { 634 push @{$ops}, Marpa::Internal::Op::CALL, $default_action_closure; 635 next RULE; 636 } 637 638 # If there is no default action specified, the fallback 639 # is to return an undef 640 push @{$ops}, Marpa::Internal::Op::CONSTANT_RESULT, 641 $Marpa::Internal::Recognizer::DEFAULT_ACTION_VALUE; 642 643 } ## end for my $rule ( @{$rules} ) 644 645 return $evaluator_rules; 646 647} # set_actions 648 649# Returns false if no parse 650sub do_rank_all { 651 my ( $recce, $depth_by_id ) = @_; 652 my $grammar = $recce->[Marpa::Internal::Recognizer::GRAMMAR]; 653 my $symbols = $grammar->[Marpa::Internal::Grammar::SYMBOLS]; 654 my $rules = $grammar->[Marpa::Internal::Grammar::RULES]; 655 656 my $cycle_ranking_action = 657 $grammar->[Marpa::Internal::Grammar::CYCLE_RANKING_ACTION]; 658 my $cycle_closure; 659 if ( defined $cycle_ranking_action ) { 660 $cycle_closure = 661 Marpa::Internal::Recognizer::resolve_semantics( $recce, 662 $cycle_ranking_action ); 663 Marpa::exception( 664 "Could not resolve cycle ranking action named '$cycle_ranking_action'" 665 ) if not $cycle_closure; 666 } ## end if ( defined $cycle_ranking_action ) 667 668 # Set up rank closures by symbol 669 my %ranking_closures_by_symbol = (); 670 SYMBOL: for my $symbol ( @{$symbols} ) { 671 my $ranking_action = 672 $symbol->[Marpa::Internal::Symbol::RANKING_ACTION]; 673 next SYMBOL if not defined $ranking_action; 674 my $ranking_closure = 675 Marpa::Internal::Recognizer::resolve_semantics( $recce, 676 $ranking_action ); 677 my $symbol_name = $symbol->[Marpa::Internal::Symbol::NAME]; 678 Marpa::exception( 679 "Could not resolve ranking action for symbol.\n", 680 qq{ Symbol was "$symbol_name".}, 681 qq{ Ranking action was "$ranking_action".} 682 ) if not defined $ranking_closure; 683 $ranking_closures_by_symbol{$symbol_name} = $ranking_closure; 684 } # end for my $symbol ( @{$symbols} ) 685 686 # Get closure used in ranking, by rule 687 my @ranking_closures_by_rule = (); 688 RULE: for my $rule ( @{$rules} ) { 689 690 my $ranking_action = $rule->[Marpa::Internal::Rule::RANKING_ACTION]; 691 my $ranking_closure; 692 my $cycle_rule = $rule->[Marpa::Internal::Rule::CYCLE]; 693 694 Marpa::exception( 695 "Rule which cycles has an explicit ranking action\n", 696 qq{ The ranking action is "$ranking_action"\n}, 697 qq{ To solve this problem,\n}, 698 qq{ Rewrite the grammar so that this rule does not cycle\n}, 699 qq{ Or eliminate its ranking action.\n} 700 ) if $ranking_action and $cycle_rule; 701 702 if ($ranking_action) { 703 $ranking_closure = 704 Marpa::Internal::Recognizer::resolve_semantics( $recce, 705 $ranking_action ); 706 Marpa::exception("Ranking closure '$ranking_action' not found") 707 if not defined $ranking_closure; 708 } ## end if ($ranking_action) 709 710 if ($cycle_rule) { 711 $ranking_closure = $cycle_closure; 712 } 713 714 next RULE if not $ranking_closure; 715 716 # If the RHS is empty ... 717 # Empty rules are never in cycles -- they are either 718 # unused (because of the CHAF rewrite) or the special 719 # null start rule. 720 if ( not scalar @{ $rule->[Marpa::Internal::Rule::RHS] } ) { 721 Marpa::exception("Ranking closure '$ranking_action' not found") 722 if not defined $ranking_closure; 723 724 $ranking_closures_by_symbol{ $rule->[Marpa::Internal::Rule::LHS] 725 ->[Marpa::Internal::Symbol::NULL_ALIAS] 726 ->[Marpa::Internal::Symbol::NAME] } = $ranking_closure; 727 } ## end if ( not scalar @{ $rule->[Marpa::Internal::Rule::RHS...]}) 728 729 next RULE if not $rule->[Marpa::Internal::Rule::USED]; 730 731 $ranking_closures_by_rule[ $rule->[Marpa::Internal::Rule::ID] ] = 732 $ranking_closure; 733 734 } ## end for my $rule ( @{$rules} ) 735 736 my $and_nodes = $recce->[Marpa::Internal::Recognizer::AND_NODES]; 737 my $or_nodes = $recce->[Marpa::Internal::Recognizer::OR_NODES]; 738 739 my @and_node_worklist = (); 740 AND_NODE: for my $and_node_id ( 0 .. $#{$and_nodes} ) { 741 742 my $and_node = $and_nodes->[$and_node_id]; 743 my $rule_id = $and_node->[Marpa::Internal::And_Node::RULE_ID]; 744 my $rule_closure = $ranking_closures_by_rule[$rule_id]; 745 my $token_name = $and_node->[Marpa::Internal::And_Node::TOKEN_NAME]; 746 my $token_closure; 747 if ($token_name) { 748 $token_closure = $ranking_closures_by_symbol{$token_name}; 749 } 750 751 my $token_rank_ref; 752 my $rule_rank_ref; 753 754 # It is a feature of the ranking closures that they are always 755 # called once per instance, even if the result is never used. 756 # This sometimes makes for unnecessary calls, 757 # but it makes these closures predictable enough 758 # to allow their use for side effects. 759 EVALUATION: 760 for my $evaluation_data ( 761 [ \$token_rank_ref, $token_closure ], 762 [ \$rule_rank_ref, $rule_closure ] 763 ) 764 { 765 my ( $rank_ref_ref, $closure ) = @{$evaluation_data}; 766 next EVALUATION if not defined $closure; 767 768 my @warnings; 769 my $eval_ok; 770 my $rank_ref; 771 DO_EVAL: { 772 local $Marpa::Internal::CONTEXT = [ 'and-node', $and_node ]; 773 local $SIG{__WARN__} = 774 sub { push @warnings, [ $_[0], ( caller 0 ) ]; }; 775 $eval_ok = eval { $rank_ref = $closure->(); 1; }; 776 } ## end DO_EVAL: 777 778 my $fatal_error; 779 CHECK_FOR_ERROR: { 780 if ( not $eval_ok or scalar @warnings ) { 781 $fatal_error = $EVAL_ERROR // 'Fatal Error'; 782 last CHECK_FOR_ERROR; 783 } 784 if ( defined $rank_ref and not ref $rank_ref ) { 785 $fatal_error = 786 "Invalid return value from ranking closure: $rank_ref"; 787 } 788 } ## end CHECK_FOR_ERROR: 789 790 if ( defined $fatal_error ) { 791 792 Marpa::Internal::code_problems( 793 { fatal_error => $fatal_error, 794 grammar => $grammar, 795 eval_ok => $eval_ok, 796 warnings => \@warnings, 797 where => 'ranking and-node ' 798 . $and_node->[Marpa::Internal::And_Node::TAG], 799 } 800 ); 801 } ## end if ( defined $fatal_error ) 802 803 ${$rank_ref_ref} = $rank_ref 804 // Marpa::Internal::Recce_Value::SKIP; 805 806 } ## end for my $evaluation_data ( [ \$token_rank_ref, $token_closure...]) 807 808 # Set the token rank if there is a token. 809 # It is zero if there is no token, or 810 # if there is one with no closure. 811 # Note: token can never cause a cycle, but they 812 # can cause an and-node to be skipped. 813 if ($token_name) { 814 $and_node->[Marpa::Internal::And_Node::TOKEN_RANK_REF] = 815 $token_rank_ref // \0; 816 } 817 818 # See if we can set the rank for this node to a constant. 819 my $constant_rank_ref; 820 SET_CONSTANT_RANK: { 821 822 if ( defined $token_rank_ref && !ref $token_rank_ref ) { 823 $constant_rank_ref = Marpa::Internal::Recce_Value::SKIP; 824 last SET_CONSTANT_RANK; 825 } 826 827 # If we have ranking closure for this rule, the rank 828 # is constant: 829 # 0 for a non-final node, 830 # the result of the closure for a final one 831 if ( defined $rule_rank_ref ) { 832 $constant_rank_ref = 833 $and_node->[Marpa::Internal::And_Node::VALUE_OPS] 834 ? $rule_rank_ref 835 : \0; 836 last SET_CONSTANT_RANK; 837 } ## end if ( defined $rule_rank_ref ) 838 839 # It there is a token and no predecessor, the rank 840 # of this rule is a constant: 841 # 0 is there was not token symbol closure 842 # the result of that closure if there was one 843 if ( $token_name 844 and not 845 defined $and_node->[Marpa::Internal::And_Node::PREDECESSOR_ID] 846 ) 847 { 848 $constant_rank_ref = $token_rank_ref // \0; 849 } ## end if ( $token_name and not defined $and_node->[...]) 850 851 } ## end SET_CONSTANT_RANK: 852 853 if ( defined $constant_rank_ref ) { 854 $and_node->[Marpa::Internal::And_Node::INITIAL_RANK_REF] = 855 $and_node->[Marpa::Internal::And_Node::CONSTANT_RANK_REF] = 856 $constant_rank_ref; 857 858 next AND_NODE; 859 } ## end if ( defined $constant_rank_ref ) 860 861 # If we are here there is (so far) no constant rank 862 # so we stack this and-node for depth-sensitive evaluation 863 push @and_node_worklist, $and_node_id; 864 865 } ## end for my $and_node_id ( 0 .. $#{$and_nodes} ) 866 867 # Now go through the and-nodes that require context to be ranked 868 # This loop assumes that all cycles has been taken care of 869 # with constant ranks 870 AND_NODE: while ( defined( my $and_node_id = pop @and_node_worklist ) ) { 871 872 no integer; 873 874 my $and_node = $and_nodes->[$and_node_id]; 875 876 # Go to next if we have already ranked this and-node 877 next AND_NODE 878 if 879 defined $and_node->[Marpa::Internal::And_Node::INITIAL_RANK_REF]; 880 881 # The rank calculated so far from the 882 # children 883 my $calculated_rank = 0; 884 885 my $is_cycle = 0; 886 my $is_skip = 0; 887 OR_NODE: 888 for my $field ( 889 Marpa::Internal::And_Node::PREDECESSOR_ID, 890 Marpa::Internal::And_Node::CAUSE_ID, 891 ) 892 { 893 my $or_node_id = $and_node->[$field]; 894 next OR_NODE if not defined $or_node_id; 895 896 my $or_node = $or_nodes->[$or_node_id]; 897 if (defined( 898 my $or_node_initial_rank_ref = 899 $or_node->[Marpa::Internal::Or_Node::INITIAL_RANK_REF] 900 ) 901 ) 902 { 903 if ( ref $or_node_initial_rank_ref ) { 904 $calculated_rank += ${$or_node_initial_rank_ref}; 905 next OR_NODE; 906 } 907 908 # At this point only possible value is skip 909 $and_node->[Marpa::Internal::And_Node::INITIAL_RANK_REF] = 910 $and_node->[Marpa::Internal::And_Node::CONSTANT_RANK_REF] 911 = Marpa::Internal::Recce_Value::SKIP; 912 913 next AND_NODE; 914 } ## end if ( defined( my $or_node_initial_rank_ref = $or_node...)) 915 my @ranks = (); 916 my @unranked_and_nodes = (); 917 CHILD_AND_NODE: 918 for my $child_and_node_id ( 919 @{ $or_node->[Marpa::Internal::Or_Node::AND_NODE_IDS] } ) 920 { 921 my $rank_ref = 922 $and_nodes->[$child_and_node_id] 923 ->[Marpa::Internal::And_Node::INITIAL_RANK_REF]; 924 if ( not defined $rank_ref ) { 925 push @unranked_and_nodes, $child_and_node_id; 926 927# say STDERR "rank for a$child_and_node_id not defined -- re-adding to worklist"; 928 929 next CHILD_AND_NODE; 930 } ## end if ( not defined $rank_ref ) 931 932 # Right now the only defined scalar value for a rank is 933 # Marpa::Internal::Recce_Value::SKIP 934 next CHILD_AND_NODE if not ref $rank_ref; 935 936 push @ranks, ${$rank_ref}; 937 938 } ## end for my $child_and_node_id ( @{ $or_node->[...]}) 939 940 # If we have unranked child and nodes, those have to be 941 # ranked first. Schedule the work and move on. 942 if ( scalar @unranked_and_nodes ) { 943 944 push @and_node_worklist, $and_node_id, @unranked_and_nodes; 945 next AND_NODE; 946 } 947 948 # If there were no non-skipped and-nodes, the 949 # parent and-node must also be skipped 950 if ( not scalar @ranks ) { 951 $or_node->[Marpa::Internal::Or_Node::INITIAL_RANK_REF] = 952 $and_node->[Marpa::Internal::And_Node::INITIAL_RANK_REF] = 953 $and_node->[Marpa::Internal::And_Node::CONSTANT_RANK_REF] 954 = Marpa::Internal::Recce_Value::SKIP; 955 956 next AND_NODE; 957 } ## end if ( not scalar @ranks ) 958 959 my $or_calculated_rank = List::Util::max @ranks; 960 $or_node->[Marpa::Internal::Or_Node::INITIAL_RANK_REF] = 961 \$or_calculated_rank; 962 $calculated_rank += $or_calculated_rank; 963 964 } ## end for my $field ( Marpa::Internal::And_Node::PREDECESSOR_ID...) 965 966 my $token_rank_ref = 967 $and_node->[Marpa::Internal::And_Node::TOKEN_RANK_REF]; 968 $calculated_rank += defined $token_rank_ref ? ${$token_rank_ref} : 0; 969 $and_node->[Marpa::Internal::And_Node::INITIAL_RANK_REF] = 970 \$calculated_rank; 971 972 } ## end while ( defined( my $and_node_id = pop @and_node_worklist...)) 973 974 return; 975 976} ## end sub do_rank_all 977 978# Does not modify stack 979sub Marpa::Internal::Recognizer::evaluate { 980 my ( $recce, $stack ) = @_; 981 my $grammar = $recce->[Marpa::Internal::Recognizer::GRAMMAR]; 982 my $trace_values = $recce->[Marpa::Internal::Recognizer::TRACE_VALUES] 983 // 0; 984 985 my $rules = $grammar->[Marpa::Internal::Grammar::RULES]; 986 my $action_object_class = 987 $grammar->[Marpa::Internal::Grammar::ACTION_OBJECT]; 988 989 my $action_object_constructor; 990 if ( defined $action_object_class ) { 991 my $constructor_name = $action_object_class . q{::new}; 992 my $closure = Marpa::Internal::Recognizer::resolve_semantics( $recce, 993 $constructor_name ); 994 Marpa::exception(qq{Could not find constructor "$constructor_name"}) 995 if not defined $closure; 996 $action_object_constructor = $closure; 997 } ## end if ( defined $action_object_class ) 998 999 my $action_object; 1000 if ($action_object_constructor) { 1001 my @warnings; 1002 my $eval_ok; 1003 my $fatal_error; 1004 DO_EVAL: { 1005 local $EVAL_ERROR = undef; 1006 local $SIG{__WARN__} = sub { 1007 push @warnings, [ $_[0], ( caller 0 ) ]; 1008 }; 1009 1010 $eval_ok = eval { 1011 $action_object = 1012 $action_object_constructor->($action_object_class); 1013 1; 1014 }; 1015 $fatal_error = $EVAL_ERROR; 1016 } ## end DO_EVAL: 1017 1018 if ( not $eval_ok or @warnings ) { 1019 Marpa::Internal::code_problems( 1020 { fatal_error => $fatal_error, 1021 grammar => $grammar, 1022 eval_ok => $eval_ok, 1023 warnings => \@warnings, 1024 where => 'constructing action object', 1025 } 1026 ); 1027 } ## end if ( not $eval_ok or @warnings ) 1028 } ## end if ($action_object_constructor) 1029 1030 $action_object //= {}; 1031 1032 my @evaluation_stack = (); 1033 my @virtual_rule_stack = (); 1034 TREE_NODE: for my $and_node ( reverse @{$stack} ) { 1035 1036 if ( $trace_values >= 3 ) { 1037 for my $i ( reverse 0 .. $#evaluation_stack ) { 1038 printf {$Marpa::Internal::TRACE_FH} 'Stack position %3d:', $i 1039 or Marpa::exception('print to trace handle failed'); 1040 print {$Marpa::Internal::TRACE_FH} q{ }, 1041 Data::Dumper->new( [ $evaluation_stack[$i] ] )->Terse(1) 1042 ->Dump 1043 or Marpa::exception('print to trace handle failed'); 1044 } ## end for my $i ( reverse 0 .. $#evaluation_stack ) 1045 } ## end if ( $trace_values >= 3 ) 1046 1047 my $value_ref = $and_node->[Marpa::Internal::And_Node::VALUE_REF]; 1048 1049 if ( defined $value_ref ) { 1050 1051 push @evaluation_stack, $value_ref; 1052 1053 if ($trace_values) { 1054 my $token_name = 1055 $and_node->[Marpa::Internal::And_Node::TOKEN_NAME]; 1056 1057 print {$Marpa::Internal::TRACE_FH} 1058 'Pushed value from a', 1059 $and_node->[Marpa::Internal::And_Node::ID], 1060 q{ }, 1061 $and_node->[Marpa::Internal::And_Node::TAG], ': ', 1062 ( $token_name ? qq{$token_name = } : q{} ), 1063 Data::Dumper->new( [$value_ref] )->Terse(1)->Dump 1064 or Marpa::exception('print to trace handle failed'); 1065 } ## end if ($trace_values) 1066 1067 } # defined $value_ref 1068 1069 my $ops = $and_node->[Marpa::Internal::And_Node::VALUE_OPS]; 1070 1071 next TREE_NODE if not defined $ops; 1072 1073 my $current_data = []; 1074 my $op_ix = 0; 1075 while ( $op_ix < scalar @{$ops} ) { 1076 given ( $ops->[ $op_ix++ ] ) { 1077 1078 when (Marpa::Internal::Op::ARGC) { 1079 1080 my $argc = $ops->[ $op_ix++ ]; 1081 1082 if ($trace_values) { 1083 my $rule_id = 1084 $and_node->[Marpa::Internal::And_Node::RULE_ID]; 1085 my $rule = $rules->[$rule_id]; 1086 say {$Marpa::Internal::TRACE_FH} 1087 'Popping ', 1088 $argc, 1089 ' values to evaluate a', 1090 $and_node->[Marpa::Internal::And_Node::ID], 1091 q{ }, 1092 $and_node->[Marpa::Internal::And_Node::TAG], 1093 ', rule: ', Marpa::brief_rule($rule) 1094 or 1095 Marpa::exception('Could not print to trace file'); 1096 } ## end if ($trace_values) 1097 1098 $current_data = 1099 [ map { ${$_} } 1100 ( splice @evaluation_stack, -$argc ) ]; 1101 1102 } ## end when (Marpa::Internal::Op::ARGC) 1103 1104 when (Marpa::Internal::Op::VIRTUAL_HEAD) { 1105 my $real_symbol_count = $ops->[ $op_ix++ ]; 1106 1107 if ($trace_values) { 1108 my $rule_id = 1109 $and_node->[Marpa::Internal::And_Node::RULE_ID]; 1110 my $rule = $rules->[$rule_id]; 1111 say {$Marpa::Internal::TRACE_FH} 1112 'Head of Virtual Rule: a', 1113 $and_node->[Marpa::Internal::And_Node::ID], 1114 q{ }, 1115 $and_node->[Marpa::Internal::And_Node::TAG], 1116 ', rule: ', Marpa::brief_rule($rule), 1117 "\n", 1118 "Incrementing virtual rule by $real_symbol_count symbols\n", 1119 'Currently ', 1120 ( scalar @virtual_rule_stack ), 1121 ' rules; ', $virtual_rule_stack[-1], ' symbols;', 1122 or 1123 Marpa::exception('Could not print to trace file'); 1124 } ## end if ($trace_values) 1125 1126 $real_symbol_count += pop @virtual_rule_stack; 1127 $current_data = 1128 [ map { ${$_} } 1129 ( splice @evaluation_stack, -$real_symbol_count ) 1130 ]; 1131 1132 } ## end when (Marpa::Internal::Op::VIRTUAL_HEAD) 1133 1134 when (Marpa::Internal::Op::VIRTUAL_HEAD_NO_SEP) { 1135 my $real_symbol_count = $ops->[ $op_ix++ ]; 1136 1137 if ($trace_values) { 1138 my $rule_id = 1139 $and_node->[Marpa::Internal::And_Node::RULE_ID]; 1140 my $rule = $rules->[$rule_id]; 1141 say {$Marpa::Internal::TRACE_FH} 1142 'Head of Virtual Rule (discards separation): a', 1143 $and_node->[Marpa::Internal::And_Node::ID], 1144 q{ }, 1145 $and_node->[Marpa::Internal::And_Node::TAG], 1146 ', rule: ', Marpa::brief_rule($rule), 1147 "\nAdding $real_symbol_count symbols; currently ", 1148 ( scalar @virtual_rule_stack ), 1149 ' rules; ', $virtual_rule_stack[-1], ' symbols' 1150 or 1151 Marpa::exception('Could not print to trace file'); 1152 } ## end if ($trace_values) 1153 1154 $real_symbol_count += pop @virtual_rule_stack; 1155 my $base = 1156 ( scalar @evaluation_stack ) - $real_symbol_count; 1157 $current_data = [ 1158 map { ${$_} } @evaluation_stack[ 1159 map { $base + 2 * $_ } 1160 ( 0 .. ( $real_symbol_count + 1 ) / 2 - 1 ) 1161 ] 1162 ]; 1163 1164 # truncate the evaluation stack 1165 $#evaluation_stack = $base - 1; 1166 1167 } ## end when (Marpa::Internal::Op::VIRTUAL_HEAD_NO_SEP) 1168 1169 when (Marpa::Internal::Op::VIRTUAL_KERNEL) { 1170 my $real_symbol_count = $ops->[ $op_ix++ ]; 1171 $virtual_rule_stack[-1] += $real_symbol_count; 1172 1173 if ($trace_values) { 1174 my $rule_id = 1175 $and_node->[Marpa::Internal::And_Node::RULE_ID]; 1176 my $rule = $rules->[$rule_id]; 1177 say {$Marpa::Internal::TRACE_FH} 1178 'Virtual Rule: a', 1179 $and_node->[Marpa::Internal::And_Node::ID], 1180 q{ }, 1181 $and_node->[Marpa::Internal::And_Node::TAG], 1182 ', rule: ', Marpa::brief_rule($rule), 1183 "\nAdding $real_symbol_count, now ", 1184 ( scalar @virtual_rule_stack ), 1185 ' rules; ', $virtual_rule_stack[-1], ' symbols' 1186 or 1187 Marpa::exception('Could not print to trace file'); 1188 } ## end if ($trace_values) 1189 1190 } ## end when (Marpa::Internal::Op::VIRTUAL_KERNEL) 1191 1192 when (Marpa::Internal::Op::VIRTUAL_TAIL) { 1193 my $real_symbol_count = $ops->[ $op_ix++ ]; 1194 1195 if ($trace_values) { 1196 my $rule_id = 1197 $and_node->[Marpa::Internal::And_Node::RULE_ID]; 1198 my $rule = $rules->[$rule_id]; 1199 say {$Marpa::Internal::TRACE_FH} 1200 'New Virtual Rule: a', 1201 $and_node->[Marpa::Internal::And_Node::ID], 1202 q{ }, 1203 $and_node->[Marpa::Internal::And_Node::TAG], 1204 ', rule: ', Marpa::brief_rule($rule), 1205 "\nSymbol count is $real_symbol_count, now ", 1206 ( scalar @virtual_rule_stack + 1 ), ' rules', 1207 or 1208 Marpa::exception('Could not print to trace file'); 1209 } ## end if ($trace_values) 1210 1211 push @virtual_rule_stack, $real_symbol_count; 1212 1213 } ## end when (Marpa::Internal::Op::VIRTUAL_TAIL) 1214 1215 when (Marpa::Internal::Op::CONSTANT_RESULT) { 1216 my $result = $ops->[ $op_ix++ ]; 1217 if ($trace_values) { 1218 print {$Marpa::Internal::TRACE_FH} 1219 'Constant result: ', 1220 'Pushing 1 value on stack: ', 1221 Data::Dumper->new( [$result] )->Terse(1)->Dump 1222 or 1223 Marpa::exception('Could not print to trace file'); 1224 } ## end if ($trace_values) 1225 push @evaluation_stack, $result; 1226 } ## end when (Marpa::Internal::Op::CONSTANT_RESULT) 1227 1228 when (Marpa::Internal::Op::CALL) { 1229 my $closure = $ops->[ $op_ix++ ]; 1230 my $result; 1231 1232 my @warnings; 1233 my $eval_ok; 1234 DO_EVAL: { 1235 local $SIG{__WARN__} = sub { 1236 push @warnings, [ $_[0], ( caller 0 ) ]; 1237 }; 1238 1239 $eval_ok = eval { 1240 $result = 1241 $closure->( $action_object, 1242 @{$current_data} ); 1243 1; 1244 }; 1245 1246 } ## end DO_EVAL: 1247 1248 if ( not $eval_ok or @warnings ) { 1249 my $rule_id = 1250 $and_node->[Marpa::Internal::And_Node::RULE_ID]; 1251 my $rule = $rules->[$rule_id]; 1252 my $fatal_error = $EVAL_ERROR; 1253 Marpa::Internal::code_problems( 1254 { fatal_error => $fatal_error, 1255 grammar => $grammar, 1256 eval_ok => $eval_ok, 1257 warnings => \@warnings, 1258 where => 'computing value', 1259 long_where => 'Computing value for rule: ' 1260 . Marpa::brief_rule($rule), 1261 } 1262 ); 1263 } ## end if ( not $eval_ok or @warnings ) 1264 1265 if ($trace_values) { 1266 print {$Marpa::Internal::TRACE_FH} 1267 'Calculated and pushed value: ', 1268 Data::Dumper->new( [$result] )->Terse(1)->Dump 1269 or 1270 Marpa::exception('print to trace handle failed'); 1271 } ## end if ($trace_values) 1272 1273 push @evaluation_stack, \$result; 1274 1275 } ## end when (Marpa::Internal::Op::CALL) 1276 1277 default { 1278 Marpa::Exception("Unknown evaluator Op: $_"); 1279 } 1280 1281 } ## end given 1282 } ## end while ( $op_ix < scalar @{$ops} ) 1283 1284 } # TREE_NODE 1285 1286 return pop @evaluation_stack; 1287} ## end sub Marpa::Internal::Recognizer::evaluate 1288 1289# null parse is special case 1290sub Marpa::Internal::Recognizer::do_null_parse { 1291 my ( $recce, $start_rule ) = @_; 1292 1293 my $start_symbol = $start_rule->[Marpa::Internal::Rule::LHS]; 1294 1295 # Cannot increment the null parse 1296 return if $recce->[Marpa::Internal::Recognizer::PARSE_COUNT]++; 1297 my $null_values = $recce->[Marpa::Internal::Recognizer::NULL_VALUES]; 1298 my $evaluator_rules = 1299 $recce->[Marpa::Internal::Recognizer::EVALUATOR_RULES]; 1300 1301 my $start_symbol_id = $start_symbol->[Marpa::Internal::Symbol::ID]; 1302 my $start_rule_id = $start_rule->[Marpa::Internal::Rule::ID]; 1303 1304 my $and_node = []; 1305 $#{$and_node} = Marpa::Internal::And_Node::LAST_FIELD; 1306 $and_node->[Marpa::Internal::And_Node::VALUE_REF] = 1307 \( $null_values->[$start_symbol_id] ); 1308 $and_node->[Marpa::Internal::And_Node::RULE_ID] = 1309 $start_rule->[Marpa::Internal::Rule::ID]; 1310 $and_node->[Marpa::Internal::And_Node::VALUE_OPS] = 1311 $evaluator_rules->[$start_rule_id]; 1312 1313 $and_node->[Marpa::Internal::And_Node::POSITION] = 0; 1314 $and_node->[Marpa::Internal::And_Node::START_EARLEME] = 0; 1315 $and_node->[Marpa::Internal::And_Node::CAUSE_EARLEME] = 0; 1316 $and_node->[Marpa::Internal::And_Node::END_EARLEME] = 0; 1317 $and_node->[Marpa::Internal::And_Node::ID] = 0; 1318 1319 $recce->[Marpa::Internal::Recognizer::AND_NODES]->[0] = $and_node; 1320 1321 my $symbol_name = $start_symbol->[Marpa::Internal::Symbol::NAME]; 1322 $and_node->[Marpa::Internal::And_Node::TAG] = q{T@0-0_} . $symbol_name; 1323 1324 return Marpa::Internal::Recognizer::evaluate( $recce, [$and_node] ); 1325 1326} ## end sub Marpa::Internal::Recognizer::do_null_parse 1327 1328# Returns false if no parse 1329sub Marpa::Recognizer::value { 1330 my ( $recce, @arg_hashes ) = @_; 1331 1332 my $parse_set_arg = $recce->[Marpa::Internal::Recognizer::END]; 1333 1334 my $trace_tasks = $recce->[Marpa::Internal::Recognizer::TRACE_TASKS]; 1335 local $Marpa::Internal::TRACE_FH = 1336 $recce->[Marpa::Internal::Recognizer::TRACE_FILE_HANDLE]; 1337 1338 my $and_nodes = $recce->[Marpa::Internal::Recognizer::AND_NODES]; 1339 my $or_nodes = $recce->[Marpa::Internal::Recognizer::OR_NODES]; 1340 my $cycle_hash; 1341 my $ranking_method = 1342 $recce->[Marpa::Internal::Recognizer::RANKING_METHOD]; 1343 1344 if ( $recce->[Marpa::Internal::Recognizer::SINGLE_PARSE_MODE] ) { 1345 Marpa::exception( 1346 qq{Arguments were passed directly to value() in a previous call\n}, 1347 qq{Only one call to value() is allowed per recognizer when arguments are passed directly\n}, 1348 qq{This is the second call to value()\n} 1349 ); 1350 } ## end if ( $recce->[Marpa::Internal::Recognizer::SINGLE_PARSE_MODE...]) 1351 1352 my $parse_count = $recce->[Marpa::Internal::Recognizer::PARSE_COUNT]; 1353 my $max_parses = $recce->[Marpa::Internal::Recognizer::MAX_PARSES]; 1354 if ( $max_parses and $parse_count > $max_parses ) { 1355 Marpa::exception("Maximum parse count ($max_parses) exceeded"); 1356 } 1357 1358 for my $arg_hash (@arg_hashes) { 1359 1360 if ( exists $arg_hash->{end} ) { 1361 if ($parse_count) { 1362 Marpa::exception( 1363 q{Cannot change "end" after first parse result}); 1364 } 1365 $recce->[Marpa::Internal::Recognizer::SINGLE_PARSE_MODE] = 1; 1366 $parse_set_arg = $arg_hash->{end}; 1367 delete $arg_hash->{end}; 1368 } ## end if ( exists $arg_hash->{end} ) 1369 1370 if ( exists $arg_hash->{closures} ) { 1371 if ($parse_count) { 1372 Marpa::exception( 1373 q{Cannot change "closures" after first parse result}); 1374 } 1375 $recce->[Marpa::Internal::Recognizer::SINGLE_PARSE_MODE] = 1; 1376 my $closures = $arg_hash->{closures}; 1377 while ( my ( $action, $closure ) = each %{$closures} ) { 1378 Marpa::exception(qq{Bad closure for action "$action"}) 1379 if ref $closure ne 'CODE'; 1380 } 1381 $recce->[Marpa::Internal::Recognizer::CLOSURES] = $closures; 1382 delete $arg_hash->{closures}; 1383 } ## end if ( exists $arg_hash->{closures} ) 1384 1385 if ( exists $arg_hash->{trace_actions} ) { 1386 $recce->[Marpa::Internal::Recognizer::SINGLE_PARSE_MODE] = 1; 1387 $recce->[Marpa::Internal::Recognizer::TRACE_ACTIONS] = 1388 $arg_hash->{trace_actions}; 1389 delete $arg_hash->{trace_actions}; 1390 } ## end if ( exists $arg_hash->{trace_actions} ) 1391 1392 if ( exists $arg_hash->{trace_values} ) { 1393 $recce->[Marpa::Internal::Recognizer::SINGLE_PARSE_MODE] = 1; 1394 $recce->[Marpa::Internal::Recognizer::TRACE_VALUES] = 1395 $arg_hash->{trace_values}; 1396 delete $arg_hash->{trace_values}; 1397 } ## end if ( exists $arg_hash->{trace_values} ) 1398 1399 # A typo made its way into the documentation, so now it's a 1400 # synonym. 1401 for my $trace_fh_alias (qw(trace_fh trace_file_handle)) { 1402 if ( exists $arg_hash->{$trace_fh_alias} ) { 1403 $recce->[Marpa::Internal::Recognizer::TRACE_FILE_HANDLE] = 1404 $Marpa::Internal::TRACE_FH = $arg_hash->{$trace_fh_alias}; 1405 delete $arg_hash->{$trace_fh_alias}; 1406 } 1407 } ## end for my $trace_fh_alias (qw(trace_fh trace_file_handle)) 1408 1409 my @unknown_arg_names = keys %{$arg_hash}; 1410 Marpa::exception( 1411 'Unknown named argument(s) to Marpa::Recognizer::value: ', 1412 ( join q{ }, @unknown_arg_names ) ) 1413 if @unknown_arg_names; 1414 1415 } ## end for my $arg_hash (@arg_hashes) 1416 1417 my $grammar = $recce->[Marpa::Internal::Recognizer::GRAMMAR]; 1418 my $earley_sets = $recce->[Marpa::Internal::Recognizer::EARLEY_SETS]; 1419 my $earley_hash = $recce->[Marpa::Internal::Recognizer::EARLEY_HASH]; 1420 1421 my $furthest_earleme = 1422 $recce->[Marpa::Internal::Recognizer::FURTHEST_EARLEME]; 1423 my $last_completed_earleme = 1424 $recce->[Marpa::Internal::Recognizer::LAST_COMPLETED_EARLEME]; 1425 Marpa::exception( 1426 "Attempt to evaluate incompletely recognized parse:\n", 1427 " Last token ends at location $furthest_earleme\n", 1428 " Recognition done only as far as location $last_completed_earleme\n" 1429 ) if $furthest_earleme > $last_completed_earleme; 1430 1431 my $rules = $grammar->[Marpa::Internal::Grammar::RULES]; 1432 my $symbols = $grammar->[Marpa::Internal::Grammar::SYMBOLS]; 1433 my $grammar_has_cycle = $grammar->[Marpa::Internal::Grammar::HAS_CYCLE]; 1434 1435 my $current_parse_set = $parse_set_arg 1436 // $recce->[Marpa::Internal::Recognizer::FURTHEST_EARLEME]; 1437 1438 # Look for the start item and start rule 1439 my $earley_set = $earley_sets->[$current_parse_set]; 1440 1441 # Perhaps this call should be moved. 1442 # The null values are currently a function of the grammar, 1443 # and should be constant for the life of a recognizer. 1444 my $null_values = $recce->[Marpa::Internal::Recognizer::NULL_VALUES] //= 1445 Marpa::Internal::Recognizer::set_null_values($recce); 1446 1447 my @task_list; 1448 my $start_item; 1449 my $start_rule; 1450 if ($parse_count) { 1451 @task_list = ( [Marpa::Internal::Task::ITERATE] ); 1452 } 1453 else { 1454 my $start_state; 1455 1456 EARLEY_ITEM: for my $item ( @{$earley_set} ) { 1457 $start_state = $item->[Marpa::Internal::Earley_Item::STATE]; 1458 $start_rule = $start_state->[Marpa::Internal::AHFA::START_RULE]; 1459 next EARLEY_ITEM if not $start_rule; 1460 $start_item = $item; 1461 last EARLEY_ITEM; 1462 } ## end for my $item ( @{$earley_set} ) 1463 1464 return if not $start_rule; 1465 1466 $recce->[Marpa::Internal::Recognizer::EVALUATOR_RULES] = 1467 Marpa::Internal::Recognizer::set_actions($recce); 1468 1469 return Marpa::Internal::Recognizer::do_null_parse( $recce, 1470 $start_rule ) 1471 if $start_rule->[Marpa::Internal::Rule::LHS] 1472 ->[Marpa::Internal::Symbol::NULLING]; 1473 1474 @task_list = (); 1475 push @task_list, [Marpa::Internal::Task::INITIALIZE]; 1476 } ## end else [ if ($parse_count) ] 1477 1478 $recce->[Marpa::Internal::Recognizer::PARSE_COUNT]++; 1479 1480 my $evaluator_rules = 1481 $recce->[Marpa::Internal::Recognizer::EVALUATOR_RULES]; 1482 my $iteration_stack = 1483 $recce->[Marpa::Internal::Recognizer::ITERATION_STACK]; 1484 1485 my $iteration_node_worklist; 1486 1487 TASK: while ( my $task = pop @task_list ) { 1488 1489 my ( $task_type, @task_data ) = @{$task}; 1490 1491 # Create the unpopulated top or-node 1492 if ( $task_type == Marpa::Internal::Task::INITIALIZE ) { 1493 1494 if ($trace_tasks) { 1495 print {$Marpa::Internal::TRACE_FH} 1496 'Task: INITIALIZE; ', 1497 ( scalar @task_list ), " tasks pending\n" 1498 or Marpa::exception('print to trace handle failed'); 1499 } ## end if ($trace_tasks) 1500 1501 my $start_rule_id = $start_rule->[Marpa::Internal::Rule::ID]; 1502 1503 my $start_or_node = []; 1504 { 1505 my $start_or_node_tag = 1506 $start_or_node->[Marpa::Internal::Or_Node::TAG] = 1507 "F$start_rule_id" 1508 . 1509 ## no critic (ValuesAndExpressions::RequireInterpolationOfMetachars) 1510 '@0-' . 1511 ## use critic 1512 $current_parse_set; 1513 $recce->[Marpa::Internal::Recognizer::OR_NODE_HASH] 1514 ->{$start_or_node_tag} = $start_or_node; 1515 } 1516 $start_or_node->[Marpa::Internal::Or_Node::ID] = 0; 1517 $start_or_node->[Marpa::Internal::Or_Node::ITEMS] = 1518 { $start_item->[Marpa::Internal::Earley_Item::NAME] => 1519 $start_item }; 1520 $start_or_node->[Marpa::Internal::Or_Node::RULE_ID] = 1521 $start_rule_id; 1522 1523 # Start or-node cannot cycle 1524 $start_or_node->[Marpa::Internal::Or_Node::CYCLE] = 0; 1525 $start_or_node->[Marpa::Internal::Or_Node::POSITION] = 1526 scalar @{ $start_rule->[Marpa::Internal::Rule::RHS] }; 1527 1528 # No source or-node for the start or-node 1529 $start_or_node->[Marpa::Internal::Or_Node::SOURCE_OR_NODE] = 1530 '[TOP]'; 1531 1532 # Zero out the evaluation 1533 $#{$and_nodes} = -1; 1534 $#{$or_nodes} = -1; 1535 $#{$iteration_stack} = -1; 1536 1537 # Populate the start or-node 1538 $or_nodes->[0] = $start_or_node; 1539 1540 my $start_iteration_node = []; 1541 $start_iteration_node->[Marpa::Internal::Iteration_Node::OR_NODE] 1542 = $start_or_node; 1543 1544 @task_list = (); 1545 push @task_list, 1546 [Marpa::Internal::Task::FIX_TREE], 1547 [ Marpa::Internal::Task::STACK_INODE, $start_iteration_node ]; 1548 1549 if ( $ranking_method eq 'constant' ) { 1550 push @task_list, [Marpa::Internal::Task::RANK_ALL], 1551 [ 1552 Marpa::Internal::Task::POPULATE_DEPTH, 0, 1553 [$start_or_node] 1554 ], 1555 [ 1556 Marpa::Internal::Task::POPULATE_OR_NODE, 1557 $start_or_node 1558 ]; 1559 } ## end if ( $ranking_method eq 'constant' ) 1560 1561 next TASK; 1562 1563 } ## end if ( $task_type == Marpa::Internal::Task::INITIALIZE) 1564 1565 # Special processing for the top iteration node 1566 if ( $task_type == Marpa::Internal::Task::ITERATE ) { 1567 1568 if ($trace_tasks) { 1569 print {$Marpa::Internal::TRACE_FH} 1570 'Task: ITERATE; ', 1571 ( scalar @task_list ), " tasks pending\n" 1572 or Marpa::exception('print to trace handle failed'); 1573 } ## end if ($trace_tasks) 1574 1575 $iteration_node_worklist = undef; 1576 1577 # In this pass, we go up the iteration stack, 1578 # looking a node which we can iterate. 1579 my $iteration_node; 1580 my $choices; 1581 ITERATION_NODE: 1582 while ( $iteration_node = pop @{$iteration_stack} ) { 1583 1584 # Climb the parent links, marking the ranks 1585 # of the nodes "dirty", until we hit one this is 1586 # already dirty 1587 my $direct_parent = $iteration_node 1588 ->[Marpa::Internal::Iteration_Node::PARENT]; 1589 PARENT: 1590 for ( my $parent = $direct_parent; defined $parent; ) { 1591 my $parent_node = $iteration_stack->[$parent]; 1592 last PARENT 1593 if not $parent_node 1594 ->[Marpa::Internal::Iteration_Node::CLEAN]; 1595 $parent_node->[Marpa::Internal::Iteration_Node::CLEAN] = 1596 0; 1597 $parent = $parent_node 1598 ->[Marpa::Internal::Iteration_Node::PARENT]; 1599 } ## end for ( my $parent = $direct_parent; defined $parent; ) 1600 1601 # This or-node is already populated, 1602 # or it would not have been put 1603 # onto the iteration stack 1604 $choices = $iteration_node 1605 ->[Marpa::Internal::Iteration_Node::CHOICES]; 1606 1607 if ( scalar @{$choices} <= 1 ) { 1608 1609 # For the node just popped off the stack 1610 # unset the pointer to it in its parent 1611 if ( defined $direct_parent ) { 1612 my $child_type = $iteration_node 1613 ->[Marpa::Internal::Iteration_Node::CHILD_TYPE]; 1614 $iteration_stack->[$direct_parent]->[ 1615 $child_type 1616 == Marpa::Internal::And_Node::PREDECESSOR_ID 1617 ? Marpa::Internal::Iteration_Node::PREDECESSOR_IX 1618 : Marpa::Internal::Iteration_Node::CAUSE_IX 1619 ] 1620 = undef; 1621 } ## end if ( defined $direct_parent ) 1622 next ITERATION_NODE; 1623 } ## end if ( scalar @{$choices} <= 1 ) 1624 1625 # Dirty the iteration node and put it back 1626 # on the stack 1627 $iteration_node 1628 ->[Marpa::Internal::Iteration_Node::PREDECESSOR_IX] = 1629 undef; 1630 $iteration_node->[Marpa::Internal::Iteration_Node::CAUSE_IX] = 1631 undef; 1632 $iteration_node->[Marpa::Internal::Iteration_Node::CLEAN] = 0; 1633 push @{$iteration_stack}, $iteration_node; 1634 1635 shift @{$choices}; 1636 1637 last ITERATION_NODE; 1638 1639 } ## end while ( $iteration_node = pop @{$iteration_stack} ) 1640 1641 # If we hit the top of the stack without finding any node 1642 # to iterate, that is it for parsing. 1643 return if not defined $iteration_node; 1644 1645 push @task_list, [Marpa::Internal::Task::FIX_TREE]; 1646 1647 if ( $choices->[0]->[Marpa::Internal::Choice::ITERATION_SUBTREE] ) 1648 { 1649 push @task_list, [Marpa::Internal::Task::GRAFT_SUBTREE]; 1650 next TASK; 1651 } 1652 1653 if ($grammar_has_cycle) { 1654 push @task_list, [Marpa::Internal::Task::CHECK_FOR_CYCLE]; 1655 next TASK; 1656 } 1657 1658 next TASK; 1659 1660 } ## end if ( $task_type == Marpa::Internal::Task::ITERATE ) 1661 1662 if ( $task_type == Marpa::Internal::Task::CHECK_FOR_CYCLE ) { 1663 1664 next TASK if not $grammar_has_cycle; 1665 1666 # This task assumes the top node and the ranks of all its 1667 # ancestores are already dirtied. 1668 if ( not defined $cycle_hash ) { 1669 my @and_node_tags = map { 1670 $_->[Marpa::Internal::Iteration_Node::CHOICES]->[0] 1671 ->[Marpa::Internal::Choice::AND_NODE] 1672 ->[Marpa::Internal::And_Node::TAG] 1673 } @{$iteration_stack}[ 0 .. $#{$iteration_stack} - 1 ]; 1674 my %cycle_hash; 1675 @cycle_hash{@and_node_tags} = @and_node_tags; 1676 $cycle_hash = \%cycle_hash; 1677 } ## end if ( not defined $cycle_hash ) 1678 1679 my $top_inode = $iteration_stack->[-1]; 1680 my $choices = 1681 $top_inode->[Marpa::Internal::Iteration_Node::CHOICES]; 1682 my $or_node = 1683 $top_inode->[Marpa::Internal::Iteration_Node::OR_NODE]; 1684 1685 # If we can't cycle, we are done 1686 next TASK if not $or_node->[Marpa::Internal::Or_Node::CYCLE]; 1687 1688 CHOICE: while ( scalar @{$choices} ) { 1689 my $and_node_tag = 1690 $choices->[0]->[Marpa::Internal::Choice::AND_NODE] 1691 ->[Marpa::Internal::And_Node::TAG]; 1692 1693 # Would this node cycle? 1694 # Shift it off the choice list and try the next choice 1695 if ( exists $cycle_hash->{$and_node_tag} ) { 1696 shift @{$choices}; 1697 next CHOICE; 1698 } 1699 1700 # No cycle 1701 # Add this node to the hash and move on the next 1702 # task, which presumably a FIX_TREE 1703 $cycle_hash->{$and_node_tag} = $and_node_tag; 1704 next TASK; 1705 1706 } ## end while ( scalar @{$choices} ) 1707 1708 # No non-cycling choices -- 1709 # Pop this node off the iteration stack, 1710 # clear the task stack and iterate. 1711 pop @{$iteration_stack}; 1712 @task_list = ( [Marpa::Internal::Task::ITERATE] ); 1713 next TASK; 1714 1715 } ## end if ( $task_type == Marpa::Internal::Task::CHECK_FOR_CYCLE) 1716 1717 # This task is set up to rerun itself until explicitly exited 1718 FIX_TREE_LOOP: 1719 while ( $task_type == Marpa::Internal::Task::FIX_TREE ) { 1720 1721 # If the work list is undefined, initialize it to the entire stack 1722 $iteration_node_worklist //= [ 0 .. $#{$iteration_stack} ]; 1723 next TASK if not scalar @{$iteration_node_worklist}; 1724 my $working_node_ix = $iteration_node_worklist->[-1]; 1725 1726 if ($trace_tasks) { 1727 print {$Marpa::Internal::TRACE_FH} 1728 q{Task: FIX_TREE; }, 1729 ( scalar @{$iteration_node_worklist} ), 1730 " current iteration node #$working_node_ix; ", 1731 ( scalar @task_list ), " tasks pending\n" 1732 or Marpa::exception('print to trace handle failed'); 1733 } ## end if ($trace_tasks) 1734 1735 # We are done fixing the tree is the worklist is empty 1736 1737 my $working_node = $iteration_stack->[$working_node_ix]; 1738 my $choices = 1739 $working_node->[Marpa::Internal::Iteration_Node::CHOICES]; 1740 my $choice = $choices->[0]; 1741 my $working_and_node = 1742 $choice->[Marpa::Internal::Choice::AND_NODE]; 1743 1744 FIELD: 1745 for my $field ( Marpa::Internal::Iteration_Node::CAUSE_IX, 1746 Marpa::Internal::Iteration_Node::PREDECESSOR_IX 1747 ) 1748 { 1749 my $ix = $working_node->[$field]; 1750 next FIELD if defined $ix; 1751 my $and_node_field = 1752 $field == Marpa::Internal::Iteration_Node::PREDECESSOR_IX 1753 ? Marpa::Internal::And_Node::PREDECESSOR_ID 1754 : Marpa::Internal::And_Node::CAUSE_ID; 1755 1756 my $or_node_id = $working_and_node->[$and_node_field]; 1757 if ( not defined $or_node_id ) { 1758 $working_node->[$field] = -999_999_999; 1759 next FIELD; 1760 } 1761 1762 my $new_iteration_node = []; 1763 $new_iteration_node 1764 ->[Marpa::Internal::Iteration_Node::OR_NODE] = 1765 $or_nodes->[$or_node_id]; 1766 $new_iteration_node->[Marpa::Internal::Iteration_Node::PARENT] 1767 = $working_node_ix; 1768 $new_iteration_node 1769 ->[Marpa::Internal::Iteration_Node::CHILD_TYPE] = 1770 $and_node_field; 1771 1772 # Restack the current task, adding a task to create 1773 # the child iteration node 1774 push @task_list, $task, 1775 [ 1776 Marpa::Internal::Task::STACK_INODE, 1777 $new_iteration_node 1778 ]; 1779 next TASK; 1780 } ## end for my $field ( ...) 1781 1782 # If we have all the child nodes and the rank is clean, 1783 # pop this node from the worklist and move on. 1784 if ( $working_node->[Marpa::Internal::Iteration_Node::CLEAN] ) { 1785 pop @{$iteration_node_worklist}; 1786 next FIX_TREE_LOOP; 1787 } 1788 1789 # If this is a constant rank node, set the rank, 1790 # mark it clean and move on. 1791 # Constant ranked nodes never lower in rank and 1792 # therefore, until they become exhausted, 1793 # they never lose their place to another choice. 1794 if (defined( 1795 my $constant_rank_ref = 1796 $working_and_node 1797 ->[Marpa::Internal::And_Node::CONSTANT_RANK_REF] 1798 ) 1799 ) 1800 { 1801 1802 # Set the new rank 1803 $choice->[Marpa::Internal::Choice::RANK] = 1804 $working_node->[Marpa::Internal::Iteration_Node::RANK] = 1805 ${$constant_rank_ref}; 1806 1807 $working_node->[Marpa::Internal::Iteration_Node::CLEAN] = 1; 1808 pop @{$iteration_node_worklist}; 1809 next FIX_TREE_LOOP; 1810 } ## end if ( defined( my $constant_rank_ref = $working_and_node...)) 1811 1812 # Rank is dirty and not constant, 1813 # so recalculate it 1814 no integer; 1815 1816 # Sum up the new rank, if it is not constant: 1817 my $token_rank_ref = $working_and_node 1818 ->[Marpa::Internal::And_Node::TOKEN_RANK_REF]; 1819 my $new_rank = defined $token_rank_ref ? ${$token_rank_ref} : 0; 1820 1821 my $predecessor_ix = $working_node 1822 ->[Marpa::Internal::Iteration_Node::PREDECESSOR_IX]; 1823 1824 $new_rank += 1825 $predecessor_ix >= 0 1826 ? $iteration_stack->[$predecessor_ix] 1827 ->[Marpa::Internal::Iteration_Node::RANK] 1828 : 0; 1829 1830 my $cause_ix = 1831 $working_node->[Marpa::Internal::Iteration_Node::CAUSE_IX]; 1832 1833 $new_rank += 1834 $cause_ix >= 0 1835 ? $iteration_stack->[$cause_ix] 1836 ->[Marpa::Internal::Iteration_Node::RANK] 1837 : 0; 1838 1839 # Set the new rank 1840 $choice->[Marpa::Internal::Choice::RANK] = 1841 $working_node->[Marpa::Internal::Iteration_Node::RANK] = 1842 $new_rank; 1843 1844 # Now to determine if the new rank puts this choice out 1845 # of proper order. 1846 # First off, unless there are 2 or more choices, the 1847 # current choice is clearly the right one. 1848 # 1849 # Secondly, if the current choice is still greater 1850 # than or equal to the next highest, it is the right 1851 # one 1852 # 1853 # Mark the current node clean, pop it off the work list 1854 # and look at the next one 1855 if ( scalar @{$choices} < 2 1856 or $new_rank 1857 >= $choices->[1]->[Marpa::Internal::Choice::RANK] ) 1858 { 1859 $working_node->[Marpa::Internal::Iteration_Node::CLEAN] = 1; 1860 pop @{$iteration_node_worklist}; 1861 1862 next FIX_TREE_LOOP; 1863 } ## end if ( scalar @{$choices} < 2 or $new_rank >= $choices...) 1864 1865 # Now we know we have to swap choices. But 1866 # with which other choice? We look for the 1867 # first one not greater than (less than or 1868 # equal to) the current choice. 1869 my $first_le_choice = 1; 1870 FIND_LE: while ( ++$first_le_choice <= $#{$choices} ) { 1871 last FIND_LE 1872 if $new_rank >= $choices->[$first_le_choice] 1873 ->[Marpa::Internal::Choice::RANK]; 1874 } 1875 1876 # Next we determine how big a chunk of stack needs to be saved 1877 # when we swap in the new choice 1878 my $last_descendant_ix = $working_node_ix; 1879 LOOK_FOR_DESCENDANT: while (1) { 1880 my $inode = $iteration_stack->[$last_descendant_ix]; 1881 my $child_ix = 1882 $inode->[Marpa::Internal::Iteration_Node::PREDECESSOR_IX]; 1883 if ( $child_ix >= 0 ) { 1884 $last_descendant_ix = $child_ix; 1885 next LOOK_FOR_DESCENDANT; 1886 } 1887 $child_ix = 1888 $inode->[Marpa::Internal::Iteration_Node::CAUSE_IX]; 1889 last LOOK_FOR_DESCENDANT if $child_ix < 0; 1890 $last_descendant_ix = $child_ix; 1891 } ## end while (1) 1892 1893 # We need to save the part of iteration stack 1894 # below the node being reordered 1895 $choice->[Marpa::Internal::Choice::ITERATION_SUBTREE] = 1896 [ @{$iteration_stack} 1897 [ $working_node_ix + 1 .. $last_descendant_ix ] ]; 1898 1899 # Get the list of parent nodes 1900 # in the portion of the stack not deleted 1901 my @parents = (); 1902 for ( 1903 my $ix = $last_descendant_ix + 1; 1904 $ix <= $#{$iteration_stack}; 1905 $ix++ 1906 ) 1907 { 1908 my $parent = 1909 $iteration_stack->[$ix] 1910 ->[Marpa::Internal::Iteration_Node::PARENT]; 1911 defined $_ and $_ < $working_node_ix and push @parents, $ix; 1912 } ## end for ( my $ix = $last_descendant_ix + 1; $ix <= $#{...}) 1913 1914 # "Dirty" the predecessor indexes in the undeleted parents 1915 # No causes will be eliminated. 1916 for my $direct_parent (@parents) { 1917 $iteration_stack->[$direct_parent] 1918 ->[Marpa::Internal::Iteration_Node::PREDECESSOR_IX] = 1919 undef; 1920 } 1921 1922 # Now "dirty" the ranks of the ancestors 1923 # Climb the parent links, marking the ranks 1924 # of the nodes "dirty", until we hit one that is 1925 # already dirty 1926 push @parents, $working_node_ix; 1927 PARENT: while ( defined( my $parent_ix = pop @parents ) ) { 1928 my $parent_node = $iteration_stack->[$parent_ix]; 1929 1930 # We could also stop ascending at the first constant ranks, 1931 # but it's not clear that the saved work later makes up 1932 # for the cost of the test here. 1933 next PARENT 1934 if not $parent_node 1935 ->[Marpa::Internal::Iteration_Node::CLEAN]; 1936 $parent_node->[Marpa::Internal::Iteration_Node::CLEAN] = 0; 1937 push @parents, 1938 $parent_node->[Marpa::Internal::Iteration_Node::PARENT]; 1939 } ## end while ( defined( my $parent_ix = pop @parents ) ) 1940 1941 # "Dirty" the working node. 1942 $working_node->[Marpa::Internal::Iteration_Node::PREDECESSOR_IX] = 1943 undef; 1944 $working_node->[Marpa::Internal::Iteration_Node::CAUSE_IX] = 1945 undef; 1946 1947 # Prune the iteration stack 1948 $#{$iteration_stack} = $working_node_ix; 1949 1950 # Our worklist of iteration nodes is now 1951 # almost 100% wrong. 1952 # Throw it away and start over. 1953 # The cycle hash also needs to be cleared. 1954 $iteration_node_worklist = undef; 1955 $cycle_hash = undef; 1956 1957 my $swap_choice = $first_le_choice - 1; 1958 1959 ( $choices->[0], $choices->[$swap_choice] ) = 1960 ( $choices->[$swap_choice], $choices->[0] ); 1961 1962 push @task_list, [Marpa::Internal::Task::FIX_TREE]; 1963 1964 if ( $choices->[0]->[Marpa::Internal::Choice::ITERATION_SUBTREE] ) 1965 { 1966 push @task_list, [Marpa::Internal::Task::GRAFT_SUBTREE]; 1967 next TASK; 1968 } 1969 1970 if ($grammar_has_cycle) { 1971 push @task_list, [Marpa::Internal::Task::CHECK_FOR_CYCLE]; 1972 next TASK; 1973 } 1974 1975 next TASK; 1976 1977 } ## end while ( $task_type == Marpa::Internal::Task::FIX_TREE ) 1978 1979 if ( $task_type == Marpa::Internal::Task::POPULATE_OR_NODE ) { 1980 1981 my $work_or_node = $task_data[0]; 1982 1983 if ($trace_tasks) { 1984 print {$Marpa::Internal::TRACE_FH} 1985 'Task: POPULATE_OR_NODE o', 1986 $work_or_node->[Marpa::Internal::Or_Node::ID], 1987 q{; }, ( scalar @task_list ), " tasks pending\n" 1988 or Marpa::exception('print to trace handle failed'); 1989 } ## end if ($trace_tasks) 1990 1991 my $work_node_name = 1992 $work_or_node->[Marpa::Internal::Or_Node::TAG]; 1993 1994 # SET Should be the same for all items 1995 my $or_node_items = [ 1996 values %{ $work_or_node->[Marpa::Internal::Or_Node::ITEMS] } 1997 ]; 1998 my $work_set; 1999 my $work_node_origin; 2000 { 2001 my $first_item = $or_node_items->[0]; 2002 $work_set = $first_item->[Marpa::Internal::Earley_Item::SET]; 2003 $work_node_origin = 2004 $first_item->[Marpa::Internal::Earley_Item::PARENT]; 2005 } 2006 2007 my $work_rule_id = 2008 $work_or_node->[Marpa::Internal::Or_Node::RULE_ID]; 2009 my $work_rule = $rules->[$work_rule_id]; 2010 my $work_position = 2011 $work_or_node->[Marpa::Internal::Or_Node::POSITION] - 1; 2012 my $work_symbol = 2013 $work_rule->[Marpa::Internal::Rule::RHS]->[$work_position]; 2014 2015 for my $item ( @{$or_node_items} ) { 2016 2017 my $or_sapling_set = $work_set; 2018 2019# Marpa::Display 2020# name: Leo Expansion 2021# inline: 1 2022 2023 my $leo_links = 2024 $item->[Marpa::Internal::Earley_Item::LEO_LINKS] // []; 2025 2026 # If this is a Leo completion, translate the Leo links 2027 for my $leo_link ( @{$leo_links} ) { 2028 2029 my ( $leo_item, $cause, $token_name, $token_value ) = 2030 @{$leo_link}; 2031 2032 my ( $next_leo_item, $leo_base_item ) = 2033 @{ $leo_item->[Marpa::Internal::Earley_Item::LINKS] 2034 ->[0] }; 2035 2036 my $next_links = []; 2037 if ($token_name) { 2038 push @{$next_links}, 2039 [ 2040 $leo_base_item, undef, 2041 $token_name, $token_value 2042 ]; 2043 } ## end if ($token_name) 2044 if ($cause) { 2045 push @{$next_links}, [ $leo_base_item, $cause ]; 2046 } 2047 2048 LEO_ITEM: for ( ;; ) { 2049 2050 if ( not $next_leo_item ) { 2051 2052 push @{ $item 2053 ->[Marpa::Internal::Earley_Item::LINKS] }, 2054 @{$next_links}; 2055 2056 # Now that the Leo links are translated, remove them 2057 $item->[Marpa::Internal::Earley_Item::LEO_LINKS] = 2058 undef; 2059 last LEO_ITEM; 2060 2061 } ## end if ( not $next_leo_item ) 2062 2063 my $state = 2064 $leo_item 2065 ->[ Marpa::Internal::Earley_Item::LEO_ACTUAL_STATE 2066 ]; 2067 my $origin = $next_leo_item 2068 ->[Marpa::Internal::Earley_Item::SET]; 2069 my $name = sprintf 2070 'S%d@%d-%d', 2071 $state->[Marpa::Internal::AHFA::ID], 2072 $origin, 2073 $or_sapling_set; 2074 my $target_item = $earley_hash->{$name}; 2075 if ( not defined $target_item ) { 2076 $target_item = []; 2077 $target_item->[Marpa::Internal::Earley_Item::NAME] 2078 = $name; 2079 $target_item 2080 ->[Marpa::Internal::Earley_Item::PARENT] = 2081 $origin; 2082 $target_item 2083 ->[Marpa::Internal::Earley_Item::STATE] = 2084 $state; 2085 $target_item 2086 ->[Marpa::Internal::Earley_Item::LINKS] = []; 2087 $target_item->[Marpa::Internal::Earley_Item::SET] 2088 = $or_sapling_set; 2089 $earley_hash->{$name} = $target_item; 2090 push @{ $earley_sets->[$or_sapling_set] }, 2091 $target_item; 2092 } ## end if ( not defined $target_item ) 2093 2094 push @{ $target_item 2095 ->[Marpa::Internal::Earley_Item::LINKS] }, 2096 @{$next_links}; 2097 2098 $leo_item = $next_leo_item; 2099 2100 ( $next_leo_item, $leo_base_item ) = 2101 @{ $leo_item 2102 ->[Marpa::Internal::Earley_Item::LINKS]->[0] 2103 }; 2104 2105 $next_links = [ [ $leo_base_item, $target_item ] ]; 2106 2107 } ## end for ( ;; ) 2108 } ## end for my $leo_link ( @{$leo_links} ) 2109 2110# Marpa::Display::End 2111 2112 } ## end for my $item ( @{$or_node_items} ) 2113 2114 my @link_worklist; 2115 2116 CREATE_LINK_WORKLIST: { 2117 2118 # link worklist item is $predecessor, $cause, $token_name, $value_ref 2119 my ( $predecessor, $cause, $token_name, $value_ref ); 2120 2121 # All predecessors apply to a 2122 # nulling work symbol. 2123 2124 if ( $work_symbol->[Marpa::Internal::Symbol::NULLING] ) { 2125 my $nulling_symbol_id = 2126 $work_symbol->[Marpa::Internal::Symbol::ID]; 2127 $value_ref = \$null_values->[$nulling_symbol_id]; 2128 $token_name = 2129 $work_symbol->[Marpa::Internal::Symbol::NAME]; 2130 @link_worklist = 2131 map { [ $_, undef, $token_name, $value_ref ] } 2132 @{$or_node_items}; 2133 last CREATE_LINK_WORKLIST; 2134 } ## end if ( $work_symbol->[Marpa::Internal::Symbol::NULLING...]) 2135 2136 # Maps token links ($predecessor, $token_name, $value_ref) 2137 # to link work items 2138 @link_worklist = 2139 map { @{ $_->[Marpa::Internal::Earley_Item::LINKS] } } 2140 @{$or_node_items}; 2141 2142 } ## end CREATE_LINK_WORKLIST: 2143 2144 # The and node data is put into the hash, only to be taken out immediately, 2145 # but in the process the very important step of eliminating duplicates 2146 # is accomplished. 2147 my %and_node_data = (); 2148 2149 LINK_WORK_ITEM: for my $link_work_item (@link_worklist) { 2150 2151 # CHOICE POINT 2152 my ( $predecessor, $cause, $token_name, $value_ref ) = 2153 @{$link_work_item}; 2154 2155 my $cause_earleme = $work_node_origin; 2156 my $predecessor_id; 2157 2158 if ( $work_position > 0 ) { 2159 2160 $cause_earleme = 2161 $predecessor->[Marpa::Internal::Earley_Item::SET]; 2162 2163 my $predecessor_name = 2164 "R$work_rule_id:$work_position" . q{@} 2165 . $predecessor->[Marpa::Internal::Earley_Item::ORIGIN] 2166 . q{-} 2167 . $cause_earleme; 2168 2169 FIND_PREDECESSOR: { 2170 my $predecessor_or_node = 2171 $recce 2172 ->[Marpa::Internal::Recognizer::OR_NODE_HASH] 2173 ->{$predecessor_name}; 2174 if ($predecessor_or_node) { 2175 $predecessor_id = $predecessor_or_node 2176 ->[Marpa::Internal::Or_Node::ID]; 2177 last FIND_PREDECESSOR 2178 if $predecessor_or_node->[ 2179 Marpa::Internal::Or_Node::SOURCE_OR_NODE 2180 ] ne $work_node_name; 2181 2182 # If the working or node is the grandparent of this new or-node, 2183 # we are building it, and need to populate the list of Earley items 2184 $predecessor_or_node 2185 ->[Marpa::Internal::Or_Node::ITEMS] 2186 ->{ $predecessor 2187 ->[Marpa::Internal::Earley_Item::NAME] } = 2188 $predecessor; 2189 2190 last FIND_PREDECESSOR; 2191 2192 } ## end if ($predecessor_or_node) 2193 2194 $predecessor_or_node = []; 2195 $predecessor_or_node->[Marpa::Internal::Or_Node::TAG] 2196 = $predecessor_name; 2197 $recce->[Marpa::Internal::Recognizer::OR_NODE_HASH] 2198 ->{$predecessor_name} = $predecessor_or_node; 2199 $predecessor_or_node 2200 ->[Marpa::Internal::Or_Node::RULE_ID] = 2201 $work_rule_id; 2202 2203 # nulling nodes are never part of cycles 2204 # thanks to the CHAF rewrite 2205 $predecessor_or_node 2206 ->[Marpa::Internal::Or_Node::CYCLE] = 2207 $work_rule->[Marpa::Internal::Rule::VIRTUAL_CYCLE] 2208 && $cause_earleme != $work_node_origin; 2209 $predecessor_or_node 2210 ->[Marpa::Internal::Or_Node::POSITION] = 2211 $work_position; 2212 $predecessor_or_node 2213 ->[Marpa::Internal::Or_Node::ITEMS] = 2214 { $predecessor 2215 ->[Marpa::Internal::Earley_Item::NAME] => 2216 $predecessor }; 2217 $predecessor_or_node 2218 ->[Marpa::Internal::Or_Node::SOURCE_OR_NODE] = 2219 $work_node_name; 2220 $predecessor_id = 2221 ( push @{$or_nodes}, $predecessor_or_node ) - 1; 2222 2223 Marpa::exception( 2224 "Too many or-nodes for evaluator: $predecessor_id" 2225 ) 2226 if $predecessor_id 2227 & ~(Marpa::Internal::N_FORMAT_MAX); 2228 $predecessor_or_node->[Marpa::Internal::Or_Node::ID] = 2229 $predecessor_id; 2230 2231 } ## end FIND_PREDECESSOR: 2232 2233 } ## end if ( $work_position > 0 ) 2234 2235 my $cause_id; 2236 2237 if ( defined $cause ) { 2238 2239 my $cause_symbol_id = 2240 $work_symbol->[Marpa::Internal::Symbol::ID]; 2241 2242 my $state = $cause->[Marpa::Internal::Earley_Item::STATE]; 2243 2244 for my $cause_rule ( 2245 @{ $state->[Marpa::Internal::AHFA::COMPLETE_RULES] 2246 ->[$cause_symbol_id] 2247 } 2248 ) 2249 { 2250 2251 my $cause_rule_id = 2252 $cause_rule->[Marpa::Internal::Rule::ID]; 2253 2254 my $cause_name = 2255 "F$cause_rule_id" . q{@} 2256 . $cause->[Marpa::Internal::Earley_Item::ORIGIN] 2257 . q{-} 2258 . $cause->[Marpa::Internal::Earley_Item::SET]; 2259 2260 FIND_CAUSE: { 2261 my $cause_or_node = 2262 $recce 2263 ->[Marpa::Internal::Recognizer::OR_NODE_HASH] 2264 ->{$cause_name}; 2265 if ($cause_or_node) { 2266 $cause_id = $cause_or_node 2267 ->[Marpa::Internal::Or_Node::ID]; 2268 last FIND_CAUSE 2269 if $cause_or_node->[ 2270 Marpa::Internal::Or_Node::SOURCE_OR_NODE 2271 ] ne $work_node_name; 2272 2273 # If the working or node is the grandparent of this new or-node, 2274 # we are building it, and need to populate the list of Earley items 2275 $cause_or_node 2276 ->[Marpa::Internal::Or_Node::ITEMS] 2277 ->{ $cause 2278 ->[Marpa::Internal::Earley_Item::NAME] 2279 } = $cause; 2280 last FIND_CAUSE if $cause_or_node; 2281 } ## end if ($cause_or_node) 2282 2283 $cause_or_node = []; 2284 $cause_or_node->[Marpa::Internal::Or_Node::TAG] = 2285 $cause_name; 2286 $recce 2287 ->[Marpa::Internal::Recognizer::OR_NODE_HASH] 2288 ->{$cause_name} = $cause_or_node; 2289 $cause_or_node 2290 ->[Marpa::Internal::Or_Node::RULE_ID] = 2291 $cause_rule_id; 2292 2293 # nulling nodes are never part of cycles 2294 # thanks to the CHAF rewrite 2295 $cause_or_node->[Marpa::Internal::Or_Node::CYCLE] 2296 = $cause_rule 2297 ->[Marpa::Internal::Rule::VIRTUAL_CYCLE] 2298 && $cause_earleme != $work_set; 2299 $cause_or_node 2300 ->[Marpa::Internal::Or_Node::POSITION] = 2301 scalar 2302 @{ $cause_rule->[Marpa::Internal::Rule::RHS] 2303 }; 2304 $cause_or_node->[Marpa::Internal::Or_Node::ITEMS] 2305 = { 2306 $cause->[Marpa::Internal::Earley_Item::NAME] 2307 => $cause }; 2308 $cause_or_node 2309 ->[Marpa::Internal::Or_Node::SOURCE_OR_NODE] = 2310 $work_node_name; 2311 $cause_id = 2312 ( push @{$or_nodes}, $cause_or_node ) - 1; 2313 2314 Marpa::exception( 2315 "Too many or-nodes for evaluator: $cause_id") 2316 if $cause_id 2317 & ~(Marpa::Internal::N_FORMAT_MAX); 2318 $cause_or_node->[Marpa::Internal::Or_Node::ID] = 2319 $cause_id; 2320 2321 } ## end FIND_CAUSE: 2322 2323 my $and_node = []; 2324 #<<< cycles in perltidy as of 5 Jul 2010 2325 $and_node 2326 ->[Marpa::Internal::And_Node::PREDECESSOR_ID 2327 ] = $predecessor_id; 2328 #>>> 2329 $and_node->[Marpa::Internal::And_Node::CAUSE_EARLEME] 2330 = $cause_earleme; 2331 $and_node->[Marpa::Internal::And_Node::CAUSE_ID] = 2332 $cause_id; 2333 2334 $and_node_data{ 2335 join q{:}, 2336 ( $predecessor_id // q{} ), 2337 $cause_id 2338 } 2339 = $and_node; 2340 2341 } ## end for my $cause_rule ( @{ $state->[...]}) 2342 2343 next LINK_WORK_ITEM; 2344 2345 } # if cause 2346 2347 my $and_node = []; 2348 $and_node->[Marpa::Internal::And_Node::PREDECESSOR_ID] = 2349 $predecessor_id; 2350 $and_node->[Marpa::Internal::And_Node::CAUSE_EARLEME] = 2351 $cause_earleme; 2352 $and_node->[Marpa::Internal::And_Node::TOKEN_NAME] = 2353 $token_name; 2354 $and_node->[Marpa::Internal::And_Node::VALUE_REF] = 2355 $value_ref; 2356 2357 $and_node_data{ 2358 join q{:}, ( $predecessor_id // q{} ), 2359 q{}, $token_name 2360 } 2361 = $and_node; 2362 2363 } ## end for my $link_work_item (@link_worklist) 2364 2365 my @child_and_nodes = values %and_node_data; 2366 2367 for my $and_node (@child_and_nodes) { 2368 2369 $and_node->[Marpa::Internal::And_Node::RULE_ID] = 2370 $work_rule_id; 2371 2372 $and_node->[Marpa::Internal::And_Node::VALUE_OPS] = 2373 $work_position 2374 == $#{ $work_rule->[Marpa::Internal::Rule::RHS] } 2375 ? $evaluator_rules 2376 ->[ $work_rule->[Marpa::Internal::Rule::ID] ] 2377 : undef; 2378 2379 $and_node->[Marpa::Internal::And_Node::POSITION] = 2380 $work_position; 2381 $and_node->[Marpa::Internal::And_Node::START_EARLEME] = 2382 $work_node_origin; 2383 $and_node->[Marpa::Internal::And_Node::END_EARLEME] = 2384 $work_set; 2385 my $id = ( push @{$and_nodes}, $and_node ) - 1; 2386 Marpa::exception("Too many and-nodes for evaluator: $id") 2387 if $id & ~(Marpa::Internal::N_FORMAT_MAX); 2388 $and_node->[Marpa::Internal::And_Node::ID] = $id; 2389 2390 { 2391 my $token_name = 2392 $and_node->[Marpa::Internal::And_Node::TOKEN_NAME]; 2393 my $cause_earleme = 2394 $and_node->[Marpa::Internal::And_Node::CAUSE_EARLEME]; 2395 my $tag = q{}; 2396 my $predecessor_id = $and_node 2397 ->[Marpa::Internal::And_Node::PREDECESSOR_ID]; 2398 my $predecessor_or_node = 2399 $predecessor_id 2400 ? $or_nodes->[$predecessor_id] 2401 : undef; 2402 $predecessor_or_node 2403 and $tag 2404 .= $predecessor_or_node 2405 ->[Marpa::Internal::Or_Node::TAG]; 2406 my $cause_id = 2407 $and_node->[Marpa::Internal::And_Node::CAUSE_ID]; 2408 my $cause_or_node = 2409 $cause_id ? $or_nodes->[$cause_id] : undef; 2410 $cause_or_node 2411 and $tag 2412 .= $cause_or_node->[Marpa::Internal::Or_Node::TAG]; 2413 $token_name 2414 and $tag 2415 .= q{T@} 2416 . $cause_earleme . q{-} 2417 . $work_set . q{_} 2418 . $token_name; 2419 $and_node->[Marpa::Internal::And_Node::TAG] = $tag; 2420 2421 } 2422 } ## end for my $and_node (@child_and_nodes) 2423 2424 # Populate the or-node, now that we have ID's for all the and-nodes 2425 $work_or_node->[Marpa::Internal::Or_Node::AND_NODE_IDS] = 2426 [ map { $_->[Marpa::Internal::And_Node::ID] } 2427 @child_and_nodes ]; 2428 2429 next TASK; 2430 } ## end if ( $task_type == Marpa::Internal::Task::POPULATE_OR_NODE) 2431 2432 if ( $task_type == Marpa::Internal::Task::STACK_INODE ) { 2433 2434 my $work_iteration_node = $task_data[0]; 2435 my $or_node = $work_iteration_node 2436 ->[Marpa::Internal::Iteration_Node::OR_NODE]; 2437 2438 if ($trace_tasks) { 2439 print {$Marpa::Internal::TRACE_FH} 2440 'Task: STACK_INODE o', 2441 $or_node->[Marpa::Internal::Or_Node::ID], 2442 q{; }, ( scalar @task_list ), " tasks pending\n" 2443 or Marpa::exception('print to trace handle failed'); 2444 } ## end if ($trace_tasks) 2445 2446 my $and_node_ids = 2447 $or_node->[Marpa::Internal::Or_Node::AND_NODE_IDS]; 2448 2449 # If the or-node is not populated, 2450 # restack this task, and stack a task to populate the 2451 # or-node on top of it. 2452 if ( not defined $and_node_ids ) { 2453 push @task_list, $task, 2454 [ Marpa::Internal::Task::POPULATE_OR_NODE, $or_node ]; 2455 next TASK; 2456 } 2457 2458 my $choices = $work_iteration_node 2459 ->[Marpa::Internal::Iteration_Node::CHOICES]; 2460 2461 # At this point we know the iteration node is populated, so if we don't 2462 # have the choices list initialized, we can do so now. 2463 if ( not defined $choices ) { 2464 2465 if ( $ranking_method eq 'constant' ) { 2466 no integer; 2467 my @choices = (); 2468 AND_NODE: for my $and_node_id ( @{$and_node_ids} ) { 2469 my $and_node = $and_nodes->[$and_node_id]; 2470 my $new_choice = []; 2471 $new_choice->[Marpa::Internal::Choice::AND_NODE] = 2472 $and_node; 2473 my $rank_ref = $and_node 2474 ->[Marpa::Internal::And_Node::INITIAL_RANK_REF]; 2475 die "Undefined rank for a$and_node_id" 2476 if not defined $rank_ref; 2477 next AND_NODE if not ref $rank_ref; 2478 $new_choice->[Marpa::Internal::Choice::RANK] = 2479 ${$rank_ref}; 2480 push @choices, $new_choice; 2481 } ## end for my $and_node_id ( @{$and_node_ids} ) 2482 ## no critic (BuiltinFunctions::ProhibitReverseSortBlock) 2483 $choices = [ 2484 sort { 2485 $b->[Marpa::Internal::Choice::RANK] 2486 <=> $a->[Marpa::Internal::Choice::RANK] 2487 } @choices 2488 ]; 2489 } ## end if ( $ranking_method eq 'constant' ) 2490 else { 2491 $choices = 2492 [ map { [ $and_nodes->[$_], 0 ] } @{$and_node_ids} ]; 2493 } 2494 $work_iteration_node 2495 ->[Marpa::Internal::Iteration_Node::CHOICES] = $choices; 2496 2497 } ## end if ( not defined $choices ) 2498 2499 # Due to skipping, even an initialized set of choices 2500 # may be empty. If it is, throw away the stack and iterate. 2501 if ( not scalar @{$choices} ) { 2502 2503# say STDERR "Initialized iteration-node has no choices"; 2504 @task_list = ( [Marpa::Internal::Task::ITERATE] ); 2505 next TASK; 2506 } ## end if ( not scalar @{$choices} ) 2507 2508 # Make our choice and set RANK 2509 my $choice = $choices->[0]; 2510 2511 # Rank is left until later to be initialized 2512 2513 my $and_node = $choice->[Marpa::Internal::Choice::AND_NODE]; 2514 my $next_iteration_stack_ix = scalar @{$iteration_stack}; 2515 2516 my $and_node_tag = $and_node->[Marpa::Internal::And_Node::TAG]; 2517 2518 if ($grammar_has_cycle) { 2519 2520 if ( not defined $cycle_hash ) { 2521 my @and_node_tags = map { 2522 $_->[Marpa::Internal::Iteration_Node::CHOICES]->[0] 2523 ->[Marpa::Internal::Choice::AND_NODE] 2524 ->[Marpa::Internal::And_Node::TAG] 2525 } @{$iteration_stack}; 2526 my %cycle_hash; 2527 @cycle_hash{@and_node_tags} = @and_node_tags; 2528 $cycle_hash = \%cycle_hash; 2529 } ## end if ( not defined $cycle_hash ) 2530 2531 # Check if we are about to cycle. 2532 if ( $or_node->[Marpa::Internal::Or_Node::CYCLE] 2533 and exists $cycle_hash->{$and_node_tag} ) 2534 { 2535 2536 # If there is another choice, increment choice and restack 2537 # this task ... 2538 # 2539 # This iteration node is not yet on the stack, so we 2540 # don't need to do anything with the pointers. 2541 if ( scalar @{$choices} > 1 ) { 2542 shift @{$choices}; 2543 push @task_list, $task; 2544 next TASK; 2545 } 2546 2547 # Otherwise, throw away all pending tasks and 2548 # iterate 2549 @task_list = ( [Marpa::Internal::Task::ITERATE] ); 2550 next TASK; 2551 } ## end if ( $or_node->[Marpa::Internal::Or_Node::CYCLE] and...) 2552 $cycle_hash->{$and_node_tag} = $and_node_tag; 2553 2554 } ## end if ($grammar_has_cycle) 2555 2556 # Tell the parent that the new iteration node is its child. 2557 if (defined( 2558 my $child_type = 2559 $work_iteration_node 2560 ->[Marpa::Internal::Iteration_Node::CHILD_TYPE] 2561 ) 2562 ) 2563 { 2564 my $parent_ix = $work_iteration_node 2565 ->[Marpa::Internal::Iteration_Node::PARENT]; 2566 $iteration_stack->[$parent_ix]->[ 2567 $child_type == Marpa::Internal::And_Node::PREDECESSOR_ID 2568 ? Marpa::Internal::Iteration_Node::PREDECESSOR_IX 2569 : Marpa::Internal::Iteration_Node::CAUSE_IX 2570 ] 2571 = scalar @{$iteration_stack}; 2572 } ## end if ( defined( my $child_type = $work_iteration_node->...)) 2573 2574 # If we are keeping an iteration node worklist, 2575 # add this node to it. 2576 defined $iteration_node_worklist 2577 and push @{$iteration_node_worklist}, 2578 scalar @{$iteration_stack}; 2579 2580 push @{$iteration_stack}, $work_iteration_node; 2581 next TASK; 2582 2583 } ## end if ( $task_type == Marpa::Internal::Task::STACK_INODE) 2584 2585 if ( $task_type == Marpa::Internal::Task::GRAFT_SUBTREE ) { 2586 2587 my $subtree_parent_node = $iteration_stack->[-1]; 2588 my $or_node = $subtree_parent_node 2589 ->[Marpa::Internal::Iteration_Node::OR_NODE]; 2590 2591 if ($trace_tasks) { 2592 print {$Marpa::Internal::TRACE_FH} 2593 'Task: GRAFT_SUBTREE o', 2594 $or_node->[Marpa::Internal::Or_Node::ID], 2595 q{; }, ( scalar @task_list ), " tasks pending\n" 2596 or Marpa::exception('print to trace handle failed'); 2597 } ## end if ($trace_tasks) 2598 2599 my $subtree_parent_ix = $#{$iteration_stack}; 2600 my $and_node_ids = 2601 $or_node->[Marpa::Internal::Or_Node::AND_NODE_IDS]; 2602 2603 my $choices = $subtree_parent_node 2604 ->[Marpa::Internal::Iteration_Node::CHOICES]; 2605 2606 # set RANK 2607 my $choice = $choices->[0]; 2608 { 2609 no integer; 2610 $subtree_parent_node->[Marpa::Internal::Iteration_Node::RANK] 2611 = $choice->[Marpa::Internal::Choice::RANK]; 2612 2613 } 2614 2615 my $subtree = 2616 $choice->[Marpa::Internal::Choice::ITERATION_SUBTREE]; 2617 2618 # Undef the old "frozen" values, 2619 # now that we are putting them back into play. 2620 $choice->[Marpa::Internal::Choice::ITERATION_SUBTREE] = undef; 2621 2622 # Clear the cycle hash 2623 $cycle_hash = undef; 2624 2625 push @{$iteration_stack}, @{$subtree}; 2626 my $top_of_stack = $#{$iteration_stack}; 2627 2628 # Reset the parent's cause and predecessor 2629 IX: 2630 for ( 2631 my $ix = $subtree_parent_ix + 1; 2632 $ix <= $top_of_stack; 2633 $ix++ 2634 ) 2635 { 2636 my $iteration_node = $iteration_stack->[$ix]; 2637 if ($iteration_node->[Marpa::Internal::Iteration_Node::PARENT] 2638 == $subtree_parent_ix ) 2639 { 2640 my $child_type = $iteration_node 2641 ->[Marpa::Internal::Iteration_Node::CHILD_TYPE]; 2642 $iteration_stack->[$subtree_parent_ix]->[ 2643 $child_type 2644 == Marpa::Internal::And_Node::PREDECESSOR_ID 2645 ? Marpa::Internal::Iteration_Node::PREDECESSOR_IX 2646 : Marpa::Internal::Iteration_Node::CAUSE_IX 2647 ] 2648 = $ix; 2649 } ## end if ( $iteration_node->[...]) 2650 } ## end for ( my $ix = $subtree_parent_ix + 1; $ix <= ...) 2651 2652 # We are done. 2653 next TASK; 2654 2655 } ## end if ( $task_type == Marpa::Internal::Task::GRAFT_SUBTREE) 2656 2657 if ( $task_type == Marpa::Internal::Task::RANK_ALL ) { 2658 2659 if ($trace_tasks) { 2660 print {$Marpa::Internal::TRACE_FH} 'Task: RANK_ALL; ', 2661 ( scalar @task_list ), " tasks pending\n" 2662 or Marpa::exception('print to trace handle failed'); 2663 } 2664 2665 do_rank_all($recce); 2666 2667 next TASK; 2668 } ## end if ( $task_type == Marpa::Internal::Task::RANK_ALL ) 2669 2670 # This task is for pre-populating the entire and-node and or-node 2671 # space one "depth level" at a time. It is used when ranking is 2672 # being done, because to rank you need to make a pre-pass through 2673 # the entire and-node and or-node space. 2674 # 2675 # As a side effect, depths are calculated for all the and-nodes. 2676 if ( $task_type == Marpa::Internal::Task::POPULATE_DEPTH ) { 2677 my ( $depth, $or_node_list ) = @task_data; 2678 2679 if ($trace_tasks) { 2680 print {$Marpa::Internal::TRACE_FH} 'Task: POPULATE_DEPTH; ', 2681 ( scalar @task_list ), " tasks pending\n" 2682 or Marpa::exception('print to trace handle failed'); 2683 } 2684 2685 # We can assume all or-nodes in the list are populated 2686 2687 my %or_nodes_at_next_depth = (); 2688 2689 # Assign a depth to all the and-node children which 2690 # do not already have one assigned. 2691 for my $and_node_id ( 2692 map { @{ $_->[Marpa::Internal::Or_Node::AND_NODE_IDS] } } 2693 @{$or_node_list} ) 2694 { 2695 my $and_node = $and_nodes->[$and_node_id]; 2696 FIELD: 2697 for my $field ( 2698 Marpa::Internal::And_Node::PREDECESSOR_ID, 2699 Marpa::Internal::And_Node::CAUSE_ID 2700 ) 2701 { 2702 my $child_or_node_id = $and_node->[$field]; 2703 next FIELD if not defined $child_or_node_id; 2704 2705 my $next_depth_or_node = $or_nodes->[$child_or_node_id]; 2706 2707 # Push onto list only if child or-node 2708 # is not already populated 2709 $next_depth_or_node 2710 ->[Marpa::Internal::Or_Node::AND_NODE_IDS] 2711 or $or_nodes_at_next_depth{$next_depth_or_node} = 2712 $next_depth_or_node; 2713 2714 } ## end for my $field ( ...) 2715 2716 } ## end for my $and_node_id ( map { @{ $_->[...]}}) 2717 2718 # No or-nodes at next depth? 2719 # Great, we are done! 2720 my @or_nodes_at_next_depth = values %or_nodes_at_next_depth; 2721 next TASK if not scalar @or_nodes_at_next_depth; 2722 2723 push @task_list, 2724 [ 2725 Marpa::Internal::Task::POPULATE_DEPTH, $depth + 1, 2726 \@or_nodes_at_next_depth 2727 ], 2728 map { [ Marpa::Internal::Task::POPULATE_OR_NODE, $_ ] } 2729 @or_nodes_at_next_depth; 2730 2731 next TASK; 2732 2733 } ## end if ( $task_type == Marpa::Internal::Task::POPULATE_DEPTH) 2734 2735 Marpa::internal_error( 2736 "Internal error: Unknown task type: $task_type"); 2737 2738 } ## end while ( my $task = pop @task_list ) 2739 2740 my @stack = map { 2741 $_->[Marpa::Internal::Iteration_Node::CHOICES]->[0] 2742 ->[Marpa::Internal::Choice::AND_NODE] 2743 } @{$iteration_stack}; 2744 2745 return Marpa::Internal::Recognizer::evaluate( $recce, \@stack ); 2746 2747} ## end sub Marpa::Recognizer::value 2748 27491; 2750