1 /************************************************************** 2 * 3 * Licensed to the Apache Software Foundation (ASF) under one 4 * or more contributor license agreements. See the NOTICE file 5 * distributed with this work for additional information 6 * regarding copyright ownership. The ASF licenses this file 7 * to you under the Apache License, Version 2.0 (the 8 * "License"); you may not use this file except in compliance 9 * with the License. You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, 14 * software distributed under the License is distributed on an 15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16 * KIND, either express or implied. See the License for the 17 * specific language governing permissions and limitations 18 * under the License. 19 * 20 *************************************************************/ 21 22 package org.apache.openoffice.ooxml.schema.automaton; 23 24 import java.io.File; 25 import java.util.Iterator; 26 import java.util.Stack; 27 import java.util.Vector; 28 29 import org.apache.openoffice.ooxml.schema.iterator.DereferencingNodeIterator; 30 import org.apache.openoffice.ooxml.schema.iterator.PermutationIterator; 31 import org.apache.openoffice.ooxml.schema.model.attribute.Attribute; 32 import org.apache.openoffice.ooxml.schema.model.attribute.AttributeGroup; 33 import org.apache.openoffice.ooxml.schema.model.attribute.AttributeGroupReference; 34 import org.apache.openoffice.ooxml.schema.model.attribute.AttributeReference; 35 import org.apache.openoffice.ooxml.schema.model.base.INode; 36 import org.apache.openoffice.ooxml.schema.model.base.INodeVisitor; 37 import org.apache.openoffice.ooxml.schema.model.base.Location; 38 import org.apache.openoffice.ooxml.schema.model.base.NodeVisitorAdapter; 39 import org.apache.openoffice.ooxml.schema.model.complex.All; 40 import org.apache.openoffice.ooxml.schema.model.complex.Any; 41 import org.apache.openoffice.ooxml.schema.model.complex.Choice; 42 import org.apache.openoffice.ooxml.schema.model.complex.ComplexContent; 43 import org.apache.openoffice.ooxml.schema.model.complex.ComplexType; 44 import org.apache.openoffice.ooxml.schema.model.complex.ComplexTypeReference; 45 import org.apache.openoffice.ooxml.schema.model.complex.Element; 46 import org.apache.openoffice.ooxml.schema.model.complex.ElementReference; 47 import org.apache.openoffice.ooxml.schema.model.complex.Extension; 48 import org.apache.openoffice.ooxml.schema.model.complex.Group; 49 import org.apache.openoffice.ooxml.schema.model.complex.GroupReference; 50 import org.apache.openoffice.ooxml.schema.model.complex.OccurrenceIndicator; 51 import org.apache.openoffice.ooxml.schema.model.complex.Sequence; 52 import org.apache.openoffice.ooxml.schema.model.schema.SchemaBase; 53 import org.apache.openoffice.ooxml.schema.model.simple.BuiltIn; 54 import org.apache.openoffice.ooxml.schema.model.simple.List; 55 import org.apache.openoffice.ooxml.schema.model.simple.Restriction; 56 import org.apache.openoffice.ooxml.schema.model.simple.SimpleContent; 57 import org.apache.openoffice.ooxml.schema.model.simple.SimpleType; 58 import org.apache.openoffice.ooxml.schema.model.simple.SimpleTypeReference; 59 import org.apache.openoffice.ooxml.schema.model.simple.Union; 60 61 /** Create a set of validating stack automatons for a set of schemas. 62 * There is one DFA (deterministic finite automaton) for each complex type and 63 * one for the top level elements. 64 */ 65 public class ValidatingCreator 66 extends CreatorBase 67 implements INodeVisitor 68 { ValidatingCreator( final SchemaBase aSchemaBase, final File aLogFile)69 public ValidatingCreator ( 70 final SchemaBase aSchemaBase, 71 final File aLogFile) 72 { 73 super(aSchemaBase, aLogFile); 74 maContextStack = new Stack<>(); 75 maCurrentContext = null; 76 } 77 78 79 80 81 /** Create one automaton for the top-level elements and one for each complex 82 * type. 83 */ Create()84 public FiniteAutomatonContainer Create () 85 { 86 final FiniteAutomatonContainer aAutomatons = new FiniteAutomatonContainer(maStateContainer); 87 88 // Create the automaton for the top-level elements. 89 aAutomatons.AddAutomaton( 90 null, 91 CreateForTopLevelElements()); 92 93 // Create one automation for each complex type. 94 for (final ComplexType aComplexType : maSchemaBase.ComplexTypes.GetSorted()) 95 aAutomatons.AddAutomaton( 96 aComplexType.GetName(), 97 CreateForComplexType(aComplexType)); 98 99 // Create one automaton for each simple type that is referenced by an element. 100 for (final INode aSimpleType : maElementSimpleTypes) 101 aAutomatons.AddAutomaton( 102 aSimpleType.GetName(), 103 CreateForSimpleType(aSimpleType)); 104 105 maLog.Close(); 106 107 return aAutomatons; 108 } 109 110 111 112 CreateForTopLevelElements()113 private FiniteAutomaton CreateForTopLevelElements () 114 { 115 maStateContext = new StateContext( 116 maStateContainer, 117 "<top-level>"); 118 final State aEndState = maStateContext.CreateEndState(); 119 120 assert(maContextStack.isEmpty()); 121 msLogIndentation = ""; 122 123 // top level elements 124 for (final Element aElement : maSchemaBase.TopLevelElements.GetSorted()) 125 ProcessType( 126 aElement, 127 maStateContext.GetStartState(), 128 maStateContext.GetStartState(), 129 aEndState); 130 131 return new FiniteAutomaton(maStateContext, null, null); 132 } 133 134 135 136 CreateForComplexType(final ComplexType aComplexType)137 private FiniteAutomaton CreateForComplexType (final ComplexType aComplexType) 138 { 139 maStateContext = new StateContext( 140 maStateContainer, 141 aComplexType.GetName().GetStateName()); 142 maAttributes = new Vector<>(); 143 final State aEndState = maStateContext.CreateEndState(); 144 ProcessType( 145 aComplexType, 146 maStateContext.GetStartState(), 147 maStateContext.GetStartState(), 148 aEndState); 149 return new FiniteAutomaton( 150 maStateContext, 151 maAttributes, 152 aComplexType.GetLocation()); 153 } 154 155 156 157 158 @Override Visit(final All aAll)159 public void Visit (final All aAll) 160 { 161 maLog.AddComment("All"); 162 ProcessAttributes(aAll); 163 164 // Make a transformation of the children into a choice of sequences that 165 // can then be processed by already existing Visit() methods. 166 // These sequences enumerate all permutations of the original children. 167 final INode aReplacement = GetAllReplacement(aAll); 168 169 final State aLocalStartState = maStateContext.CreateState( 170 maCurrentContext.BaseState, 171 "As"); 172 final State aLocalEndState = maStateContext.CreateState( 173 maCurrentContext.BaseState, 174 "Ae"); 175 176 maLog.StartBlock(); 177 AddEpsilonTransition(maCurrentContext.StartState, aLocalStartState); 178 final long nStartTime = System.currentTimeMillis(); 179 ProcessType( 180 aReplacement, 181 maStateContext.CreateState(maCurrentContext.BaseState, "A"), 182 aLocalStartState, 183 aLocalEndState); 184 final long nEndTime = System.currentTimeMillis(); 185 System.out.printf("processed 'all' children in %fs\n", (nEndTime-nStartTime)/1000.0); 186 AddEpsilonTransition(aLocalEndState, maCurrentContext.EndState); 187 maLog.EndBlock(); 188 } 189 190 191 192 193 @Override Visit(final Any aAny)194 public void Visit (final Any aAny) 195 { 196 assert(aAny.GetChildCount() == 0); 197 198 maLog.AddComment("Any"); 199 ProcessAttributes(aAny); 200 201 AddSkipTransition( 202 maCurrentContext.StartState, 203 new SkipData( 204 aAny.GetProcessContentsFlag(), 205 aAny.GetNamespaces())); 206 AddEpsilonTransition(maCurrentContext.StartState, maCurrentContext.EndState); 207 } 208 209 210 211 212 @Override Visit(final ComplexContent aComplexContent)213 public void Visit (final ComplexContent aComplexContent) 214 { 215 assert(aComplexContent.GetChildCount() == 1); 216 217 maLog.AddComment ("Complex Content."); 218 ProcessAttributes(aComplexContent); 219 220 maLog.StartBlock(); 221 ProcessType( 222 aComplexContent.GetChildren().iterator().next(), 223 maCurrentContext.BaseState, 224 maCurrentContext.StartState, 225 maCurrentContext.EndState); 226 maLog.EndBlock(); 227 } 228 229 230 231 232 @Override Visit(final ComplexType aComplexType)233 public void Visit (final ComplexType aComplexType) 234 { 235 if (maLog != null) 236 { 237 maLog.printf("\n"); 238 maLog.AddComment ("Complex Type %s defined in %s.", 239 aComplexType.GetName().GetDisplayName(), 240 aComplexType.GetLocation()); 241 } 242 ProcessAttributes(aComplexType); 243 244 maLog.StartBlock(); 245 maLog.printf("%sstarting at state %s\n", msLogIndentation, maCurrentContext.StartState.GetFullname()); 246 247 if (GetElementCount(aComplexType) == 0) 248 { 249 // There are elements. Therefore there will be no transitions. 250 // The start state is accepting and the end state is not necessary. 251 maCurrentContext.StartState.SetIsAccepting(); 252 maStateContext.RemoveState(maCurrentContext.EndState); 253 } 254 255 for (final INode aChild : aComplexType.GetChildren()) 256 ProcessType(aChild, maCurrentContext.BaseState, maCurrentContext.StartState, maCurrentContext.EndState); 257 258 maLog.EndBlock(); 259 } 260 261 262 263 264 @Override Visit(final ComplexTypeReference aNode)265 public void Visit (final ComplexTypeReference aNode) 266 { 267 throw new RuntimeException("can not handle "+aNode.toString()); 268 } 269 270 271 272 273 @Override Visit(final Choice aChoice)274 public void Visit (final Choice aChoice) 275 { 276 maLog.AddComment("Choice"); 277 ProcessAttributes(aChoice); 278 279 final State aLocalStartState = maStateContext.CreateState(maCurrentContext.BaseState, "Cs"); 280 final State aLocalEndState = maStateContext.CreateState(maCurrentContext.BaseState, "Ce"); 281 maLog.StartBlock(); 282 AddEpsilonTransition(maCurrentContext.StartState, aLocalStartState); 283 284 int nStateIndex = 0; 285 for (final INode aChild : aChoice.GetChildren()) 286 { 287 ProcessType( 288 aChild, 289 maStateContext.CreateState(maCurrentContext.BaseState, "C"+nStateIndex++), 290 aLocalStartState, 291 aLocalEndState); 292 } 293 AddEpsilonTransition(aLocalEndState, maCurrentContext.EndState); 294 maLog.EndBlock(); 295 } 296 297 298 299 300 @Override Visit(final Element aElement)301 public void Visit (final Element aElement) 302 { 303 assert(aElement.GetChildCount()==0); 304 305 maLog.AddComment("Element: on '%s' go from %s to %s via %s", 306 aElement.GetElementName().GetDisplayName(), 307 maCurrentContext.StartState.GetFullname(), 308 maCurrentContext.EndState.GetFullname(), 309 aElement.GetTypeName().GetStateName()); 310 ProcessAttributes(aElement); 311 312 final Transition aTransition = new Transition( 313 maCurrentContext.StartState, 314 maCurrentContext.EndState, 315 aElement.GetElementName(), 316 aElement.GetTypeName().GetStateName()); 317 maCurrentContext.StartState.AddTransition(aTransition); 318 319 // For elements whose type is a simple type we have to remember that 320 // simple type for later (and then create an NFA for it.) 321 final INode aSimpleType = maSchemaBase.GetSimpleTypeForName( 322 aElement.GetTypeName()); 323 if (aSimpleType != null) 324 maElementSimpleTypes.add(aSimpleType); 325 } 326 327 328 329 330 @Override Visit(final ElementReference aReference)331 public void Visit (final ElementReference aReference) 332 { 333 assert(aReference.GetChildCount() == 0); 334 335 maLog.AddComment("Element reference to %s", aReference.GetReferencedElementName()); 336 ProcessAttributes(aReference); 337 338 final Element aElement = aReference.GetReferencedElement(maSchemaBase); 339 if (aElement == null) 340 throw new RuntimeException("can't find referenced element "+aReference.GetReferencedElementName()); 341 maLog.StartBlock(); 342 ProcessType(aElement, maCurrentContext.BaseState, maCurrentContext.StartState, maCurrentContext.EndState); 343 maLog.EndBlock(); 344 } 345 346 347 348 349 /** Treat extension nodes like sequences (for now). 350 */ 351 @Override Visit(final Extension aExtension)352 public void Visit (final Extension aExtension) 353 { 354 assert(aExtension.GetChildCount() <= 1); 355 356 maLog.AddComment("Extension of base type %s", aExtension.GetBaseTypeName()); 357 ProcessAttributes(aExtension); 358 359 final Vector<INode> aNodes = aExtension.GetTypeNodes(maSchemaBase); 360 361 maLog.StartBlock(); 362 int nStateIndex = 0; 363 State aCurrentState = maStateContext.CreateState(maCurrentContext.BaseState, "E"+nStateIndex++); 364 AddEpsilonTransition(maCurrentContext.StartState, aCurrentState); 365 366 State aNextState = maStateContext.CreateState(maCurrentContext.BaseState, "E"+nStateIndex++); 367 ProcessType(aExtension.GetReferencedNode(maSchemaBase), aCurrentState, aCurrentState, aNextState); 368 aCurrentState = aNextState; 369 370 for (final INode aChild : aNodes) 371 { 372 aNextState = maStateContext.CreateState(maCurrentContext.BaseState, "E"+nStateIndex++); 373 ProcessType(aChild, aCurrentState, aCurrentState, aNextState); 374 aCurrentState = aNextState; 375 } 376 AddEpsilonTransition(aCurrentState, maCurrentContext.EndState); 377 maLog.EndBlock(); 378 } 379 380 381 382 383 @Override Visit(final Group aGroup)384 public void Visit (final Group aGroup) 385 { 386 assert(aGroup.GetChildCount() == 1); 387 388 maLog.AddComment("Group %s", aGroup.GetName()); 389 ProcessAttributes(aGroup); 390 391 maLog.StartBlock(); 392 final State aGroupBaseState = maStateContext.CreateState(maCurrentContext.BaseState, "G"); 393 ProcessType( 394 aGroup.GetOnlyChild(), 395 aGroupBaseState, 396 maCurrentContext.StartState, 397 maCurrentContext.EndState); 398 maLog.EndBlock(); 399 } 400 401 402 403 404 @Override Visit(final GroupReference aReference)405 public void Visit (final GroupReference aReference) 406 { 407 maLog.AddComment("Group reference to %s", aReference.GetReferencedGroupName()); 408 ProcessAttributes(aReference); 409 410 final Group aGroup = aReference.GetReferencedGroup(maSchemaBase); 411 if (aGroup == null) 412 throw new RuntimeException("can't find referenced group "+aReference.GetReferencedGroupName()); 413 414 maLog.StartBlock(); 415 ProcessType(aGroup, maCurrentContext.BaseState, maCurrentContext.StartState, maCurrentContext.EndState); 416 maLog.EndBlock(); 417 } 418 419 420 421 422 /** An occurrence indicator defines how many times the single child can occur. 423 * The minimum value defines the mandatory number of times. The maximum value 424 * defines the optional number. 425 */ 426 @Override Visit(final OccurrenceIndicator aOccurrence)427 public void Visit (final OccurrenceIndicator aOccurrence) 428 { 429 assert(aOccurrence.GetChildCount() == 1); 430 431 maLog.AddComment("OccurrenceIndicator %s->%s", 432 aOccurrence.GetDisplayMinimum(), 433 aOccurrence.GetDisplayMaximum()); 434 ProcessAttributes(aOccurrence); 435 436 maLog.StartBlock(); 437 438 final INode aChild = aOccurrence.GetChildren().iterator().next(); 439 440 int nIndex = 0; 441 State aCurrentState = maStateContext.CreateState(maCurrentContext.BaseState, "O"+nIndex++); 442 AddEpsilonTransition(maCurrentContext.StartState, aCurrentState); 443 444 if (aOccurrence.GetMinimum() == 0) 445 { 446 // A zero minimum means that all occurrences are optional. 447 // Add a short circuit from start to end. 448 maLog.AddComment("Occurrence: make whole element optional (min==0)"); 449 AddEpsilonTransition(maCurrentContext.StartState, maCurrentContext.EndState); 450 } 451 else 452 { 453 // Write a row of mandatory transitions for the minimum. 454 for (; nIndex<=aOccurrence.GetMinimum(); ++nIndex) 455 { 456 // Add transition i-1 -> i (i == nIndex). 457 final State aNextState = maStateContext.CreateState(maCurrentContext.BaseState, "O"+nIndex); 458 maLog.AddComment("Occurrence: move from %d -> %d (%s -> %s) (minimum)", 459 nIndex-1, 460 nIndex, 461 aCurrentState, 462 aNextState); 463 maLog.StartBlock(); 464 ProcessType(aChild, aCurrentState, aCurrentState, aNextState); 465 maLog.EndBlock(); 466 aCurrentState = aNextState; 467 } 468 } 469 470 if (aOccurrence.GetMaximum() == OccurrenceIndicator.unbounded) 471 { 472 // Write loop on last state when max is unbounded. 473 474 // last -> loop 475 final State aLoopState = maStateContext.CreateState(maCurrentContext.BaseState, "OL"); 476 maLog.AddComment("Occurrence: forward to loop (maximum)"); 477 AddEpsilonTransition(aCurrentState, aLoopState); 478 479 // loop -> loop 480 maLog.AddComment("Occurrence: loop"); 481 maLog.StartBlock(); 482 ProcessType(aChild, aLoopState, aLoopState, aLoopState); 483 maLog.EndBlock(); 484 485 // -> end 486 maLog.AddComment("Occurrence: forward to local end"); 487 AddEpsilonTransition(aLoopState, maCurrentContext.EndState); 488 } 489 else 490 { 491 // Write a row of optional transitions for the maximum. 492 for (; nIndex<=aOccurrence.GetMaximum(); ++nIndex) 493 { 494 if (nIndex > 0) 495 { 496 // i-1 -> end 497 maLog.AddComment("Occurrence: make %d optional (maximum)", nIndex-1); 498 AddEpsilonTransition(aCurrentState, maCurrentContext.EndState); 499 } 500 501 // i-1 -> i 502 final State aNextState = maStateContext.CreateState(maCurrentContext.BaseState, "O"+nIndex); 503 maLog.AddComment("Occurrence: %d -> %d (%s -> %s) (maximum)", 504 nIndex-1, 505 nIndex, 506 aCurrentState, 507 aNextState); 508 maLog.StartBlock(); 509 ProcessType(aChild, aCurrentState, aCurrentState, aNextState); 510 maLog.EndBlock(); 511 512 aCurrentState = aNextState; 513 } 514 515 // max -> end 516 maLog.AddComment("Occurrence: forward to local end"); 517 AddEpsilonTransition(aCurrentState, maCurrentContext.EndState); 518 } 519 maLog.EndBlock(); 520 } 521 522 523 524 525 /** Ordered sequence of nodes. 526 * For n nodes create states S0 to Sn where Si and Si+1 become start and 527 * end states for the i-th child. 528 */ 529 @Override Visit(final Sequence aSequence)530 public void Visit (final Sequence aSequence) 531 { 532 maLog.AddComment("Sequence."); 533 ProcessAttributes(aSequence); 534 535 maLog.StartBlock(); 536 int nStateIndex = 0; 537 State aCurrentState = maStateContext.CreateState(maCurrentContext.BaseState, "S"+nStateIndex++); 538 AddEpsilonTransition(maCurrentContext.StartState, aCurrentState); 539 for (final INode aChild : aSequence.GetChildren()) 540 { 541 final State aNextState = maStateContext.CreateState(maCurrentContext.BaseState, "S"+nStateIndex++); 542 ProcessType(aChild, aCurrentState, aCurrentState, aNextState); 543 aCurrentState = aNextState; 544 } 545 AddEpsilonTransition(aCurrentState, maCurrentContext.EndState); 546 maLog.EndBlock(); 547 } 548 549 550 551 552 @Override Visit(final BuiltIn aNode)553 public void Visit (final BuiltIn aNode) 554 { 555 // Ignored. 556 //throw new RuntimeException("can not handle "+aNode.toString()); 557 } 558 559 560 561 562 @Override Visit(final List aNode)563 public void Visit (final List aNode) 564 { 565 throw new RuntimeException("can not handle "+aNode.toString()); 566 } 567 568 569 570 571 @Override Visit(final Restriction aNode)572 public void Visit (final Restriction aNode) 573 { 574 throw new RuntimeException("can not handle "+aNode.toString()); 575 } 576 577 578 579 @Override Visit(final SimpleContent aNode)580 public void Visit (final SimpleContent aNode) 581 { 582 maLog.AddComment("SimpleContent."); 583 ProcessAttributes(aNode); 584 585 for (final INode aChild : aNode.GetChildren()) 586 ProcessType(aChild, maCurrentContext.BaseState, maCurrentContext.StartState, maCurrentContext.EndState); 587 } 588 589 590 591 592 @Override Visit(final SimpleType aNode)593 public void Visit (final SimpleType aNode) 594 { 595 maLog.AddComment("SimpleType."); 596 //for (final INode aChild : aNode.GetChildren()) 597 //ProcessType(aChild, maCurrentContext.BaseState, maCurrentContext.StartState, maCurrentContext.EndState); 598 } 599 600 601 602 603 @Override Visit(final SimpleTypeReference aNode)604 public void Visit (final SimpleTypeReference aNode) 605 { 606 throw new RuntimeException("can not handle "+aNode.toString()); 607 } 608 609 610 611 612 @Override Visit(final Union aNode)613 public void Visit (final Union aNode) 614 { 615 throw new RuntimeException("can not handle "+aNode.toString()); 616 } 617 618 619 620 621 @Override Visit(final AttributeGroup aNode)622 public void Visit (final AttributeGroup aNode) 623 { 624 throw new RuntimeException("can not handle "+aNode.toString()); 625 } 626 627 628 629 630 @Override Visit(final AttributeReference aNode)631 public void Visit (final AttributeReference aNode) 632 { 633 throw new RuntimeException("can not handle "+aNode.toString()); 634 } 635 636 637 638 639 @Override Visit(final Attribute aNode)640 public void Visit (final Attribute aNode) 641 { 642 throw new RuntimeException("can not handle "+aNode.toString()); 643 } 644 645 646 647 648 @Override Visit(final AttributeGroupReference aNode)649 public void Visit (final AttributeGroupReference aNode) 650 { 651 throw new RuntimeException("can not handle "+aNode.toString()); 652 } 653 654 655 656 ProcessType( final INode aNode, final State aBaseState, final State aStartState, final State aEndState)657 private void ProcessType ( 658 final INode aNode, 659 final State aBaseState, 660 final State aStartState, 661 final State aEndState) 662 { 663 maContextStack.push(maCurrentContext); 664 maCurrentContext = new Context(aBaseState, aStartState, aEndState); 665 aNode.AcceptVisitor(this); 666 maCurrentContext = maContextStack.pop(); 667 } 668 669 670 671 AddEpsilonTransition( final State aStartState, final State aEndState)672 private void AddEpsilonTransition ( 673 final State aStartState, 674 final State aEndState) 675 { 676 // Silently ignore epsilon transitions from a state to itself. 677 // They may indicate a problem but usually are just artifacts 678 // that can be safely ignored. 679 if (aStartState == aEndState) 680 return; 681 else 682 { 683 final EpsilonTransition aTransition = new EpsilonTransition( 684 aStartState, 685 aEndState); 686 aStartState.AddEpsilonTransition(aTransition); 687 688 if (maLog != null) 689 { 690 maLog.printf("%sepsilon transition from %s to %s\n", 691 msLogIndentation, 692 aStartState.GetFullname(), 693 aEndState.GetFullname()); 694 } 695 } 696 } 697 698 699 700 GetElementCount(final INode aNode)701 private int GetElementCount (final INode aNode) 702 { 703 704 class Visitor extends NodeVisitorAdapter 705 { 706 int nElementCount = 0; 707 @Override public void Visit (final Element aElement) 708 { 709 ++nElementCount; 710 } 711 int GetElementCount () 712 { 713 return nElementCount; 714 } 715 }; 716 final Visitor aVisitor = new Visitor(); 717 for (final INode aChildNode : new DereferencingNodeIterator(aNode, maSchemaBase, false)) 718 { 719 aChildNode.AcceptVisitor(aVisitor); 720 } 721 return aVisitor.GetElementCount(); 722 } 723 724 725 726 GetAllReplacement(final All aAll)727 private INode GetAllReplacement (final All aAll) 728 { 729 final long nStartTime = System.currentTimeMillis(); 730 731 // By default each child of this node can appear exactly once, however 732 // the order is undefined. This corresponds to an enumeration of all 733 // permutations of the children. 734 735 // Set up an array of all children. This array will be modified to contain 736 // all permutations. 737 final INode[] aNodes = new INode[aAll.GetChildCount()]; 738 final Iterator<INode> aChildren = aAll.GetChildren().iterator(); 739 for (int nIndex=0; aChildren.hasNext(); ++nIndex) 740 aNodes[nIndex] = aChildren.next(); 741 742 final Location aLocation = aAll.GetLocation(); 743 final Choice aChoice = new Choice(aAll, aLocation); 744 745 // Treat every permutation as sequence so that the whole set of permutations 746 // is equivalent to a choice of sequences. 747 int nCount = 0; 748 for (final PermutationIterator<INode> aIterator = new PermutationIterator<>(aNodes); aIterator.HasMore(); aIterator.Next()) 749 { 750 // Create a Sequence node for the current permutation and add it as 751 // choice to the Choice node. 752 final Sequence aSequence = new Sequence(aChoice, null, aLocation); 753 aChoice.AddChild(aSequence); 754 755 for (final INode aNode : aNodes) 756 aSequence.AddChild(aNode); 757 758 ++nCount; 759 } 760 final long nEndTime = System.currentTimeMillis(); 761 System.out.printf("created %d permutations in %fs\n", 762 nCount, 763 (nEndTime-nStartTime)/1000.0); 764 765 return aChoice; 766 } 767 768 769 770 771 class Context 772 { Context( final State aBaseState, final State aStartState, final State aEndState)773 Context ( 774 final State aBaseState, 775 final State aStartState, 776 final State aEndState) 777 { 778 BaseState = aBaseState; 779 StartState = aStartState; 780 EndState = aEndState; 781 } 782 final State BaseState; 783 final State StartState; 784 final State EndState; 785 } 786 787 788 789 790 private StateContext maStateContext; 791 private final Stack<Context> maContextStack; 792 private Context maCurrentContext; 793 } 794