16cde7e4aSAndre Fischer /************************************************************** 26cde7e4aSAndre Fischer * 36cde7e4aSAndre Fischer * Licensed to the Apache Software Foundation (ASF) under one 46cde7e4aSAndre Fischer * or more contributor license agreements. See the NOTICE file 56cde7e4aSAndre Fischer * distributed with this work for additional information 66cde7e4aSAndre Fischer * regarding copyright ownership. The ASF licenses this file 76cde7e4aSAndre Fischer * to you under the Apache License, Version 2.0 (the 86cde7e4aSAndre Fischer * "License"); you may not use this file except in compliance 96cde7e4aSAndre Fischer * with the License. You may obtain a copy of the License at 106cde7e4aSAndre Fischer * 116cde7e4aSAndre Fischer * http://www.apache.org/licenses/LICENSE-2.0 126cde7e4aSAndre Fischer * 136cde7e4aSAndre Fischer * Unless required by applicable law or agreed to in writing, 146cde7e4aSAndre Fischer * software distributed under the License is distributed on an 156cde7e4aSAndre Fischer * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 166cde7e4aSAndre Fischer * KIND, either express or implied. See the License for the 176cde7e4aSAndre Fischer * specific language governing permissions and limitations 186cde7e4aSAndre Fischer * under the License. 196cde7e4aSAndre Fischer * 206cde7e4aSAndre Fischer *************************************************************/ 216cde7e4aSAndre Fischer 226cde7e4aSAndre Fischer package org.apache.openoffice.ooxml.schema.automaton; 236cde7e4aSAndre Fischer 246cde7e4aSAndre Fischer import java.io.File; 2562886075SAndre Fischer import java.util.Iterator; 2662886075SAndre Fischer import java.util.Stack; 276cde7e4aSAndre Fischer import java.util.Vector; 286cde7e4aSAndre Fischer 2962886075SAndre Fischer import org.apache.openoffice.ooxml.schema.iterator.DereferencingNodeIterator; 3062886075SAndre Fischer import org.apache.openoffice.ooxml.schema.iterator.PermutationIterator; 316cde7e4aSAndre Fischer import org.apache.openoffice.ooxml.schema.model.attribute.Attribute; 3262886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.attribute.AttributeGroup; 3362886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.attribute.AttributeGroupReference; 3462886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.attribute.AttributeReference; 3562886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.base.INode; 366cde7e4aSAndre Fischer import org.apache.openoffice.ooxml.schema.model.base.INodeVisitor; 3762886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.base.Location; 3862886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.base.NodeVisitorAdapter; 3962886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.complex.All; 4062886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.complex.Any; 4162886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.complex.Choice; 4262886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.complex.ComplexContent; 436cde7e4aSAndre Fischer import org.apache.openoffice.ooxml.schema.model.complex.ComplexType; 4462886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.complex.ComplexTypeReference; 456cde7e4aSAndre Fischer import org.apache.openoffice.ooxml.schema.model.complex.Element; 4662886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.complex.ElementReference; 4762886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.complex.Extension; 4862886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.complex.Group; 4962886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.complex.GroupReference; 5062886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.complex.OccurrenceIndicator; 5162886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.complex.Sequence; 526cde7e4aSAndre Fischer import org.apache.openoffice.ooxml.schema.model.schema.SchemaBase; 5362886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.simple.BuiltIn; 5462886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.simple.List; 5562886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.simple.Restriction; 5662886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.simple.SimpleContent; 5762886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.simple.SimpleType; 5862886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.simple.SimpleTypeReference; 5962886075SAndre Fischer import org.apache.openoffice.ooxml.schema.model.simple.Union; 606cde7e4aSAndre Fischer 616cde7e4aSAndre Fischer /** Create a set of validating stack automatons for a set of schemas. 626cde7e4aSAndre Fischer * There is one DFA (deterministic finite automaton) for each complex type and 636cde7e4aSAndre Fischer * one for the top level elements. 646cde7e4aSAndre Fischer */ 656cde7e4aSAndre Fischer public class ValidatingCreator 6662886075SAndre Fischer extends CreatorBase 6762886075SAndre Fischer implements INodeVisitor 686cde7e4aSAndre Fischer { ValidatingCreator( final SchemaBase aSchemaBase, final File aLogFile)696cde7e4aSAndre Fischer public ValidatingCreator ( 706cde7e4aSAndre Fischer final SchemaBase aSchemaBase, 716cde7e4aSAndre Fischer final File aLogFile) 726cde7e4aSAndre Fischer { 7362886075SAndre Fischer super(aSchemaBase, aLogFile); 7462886075SAndre Fischer maContextStack = new Stack<>(); 7562886075SAndre Fischer maCurrentContext = null; 766cde7e4aSAndre Fischer } 776cde7e4aSAndre Fischer 786cde7e4aSAndre Fischer 796cde7e4aSAndre Fischer 806cde7e4aSAndre Fischer 816cde7e4aSAndre Fischer /** Create one automaton for the top-level elements and one for each complex 826cde7e4aSAndre Fischer * type. 836cde7e4aSAndre Fischer */ Create()846cde7e4aSAndre Fischer public FiniteAutomatonContainer Create () 856cde7e4aSAndre Fischer { 866cde7e4aSAndre Fischer final FiniteAutomatonContainer aAutomatons = new FiniteAutomatonContainer(maStateContainer); 87*7d97ce35SAndre Fischer 88*7d97ce35SAndre Fischer // Create the automaton for the top-level elements. 896cde7e4aSAndre Fischer aAutomatons.AddAutomaton( 906cde7e4aSAndre Fischer null, 916cde7e4aSAndre Fischer CreateForTopLevelElements()); 926cde7e4aSAndre Fischer 93*7d97ce35SAndre Fischer // Create one automation for each complex type. 946cde7e4aSAndre Fischer for (final ComplexType aComplexType : maSchemaBase.ComplexTypes.GetSorted()) 956cde7e4aSAndre Fischer aAutomatons.AddAutomaton( 966cde7e4aSAndre Fischer aComplexType.GetName(), 976cde7e4aSAndre Fischer CreateForComplexType(aComplexType)); 98*7d97ce35SAndre Fischer 99*7d97ce35SAndre Fischer // Create one automaton for each simple type that is referenced by an element. 100*7d97ce35SAndre Fischer for (final INode aSimpleType : maElementSimpleTypes) 101*7d97ce35SAndre Fischer aAutomatons.AddAutomaton( 102*7d97ce35SAndre Fischer aSimpleType.GetName(), 103*7d97ce35SAndre Fischer CreateForSimpleType(aSimpleType)); 1046cde7e4aSAndre Fischer 105*7d97ce35SAndre Fischer maLog.Close(); 1066cde7e4aSAndre Fischer 1076cde7e4aSAndre Fischer return aAutomatons; 1086cde7e4aSAndre Fischer } 1096cde7e4aSAndre Fischer 1106cde7e4aSAndre Fischer 1116cde7e4aSAndre Fischer 1126cde7e4aSAndre Fischer CreateForTopLevelElements()1136cde7e4aSAndre Fischer private FiniteAutomaton CreateForTopLevelElements () 1146cde7e4aSAndre Fischer { 11562886075SAndre Fischer maStateContext = new StateContext( 1166cde7e4aSAndre Fischer maStateContainer, 1176cde7e4aSAndre Fischer "<top-level>"); 11862886075SAndre Fischer final State aEndState = maStateContext.CreateEndState(); 11962886075SAndre Fischer 12062886075SAndre Fischer assert(maContextStack.isEmpty()); 12162886075SAndre Fischer msLogIndentation = ""; 1226cde7e4aSAndre Fischer 1236cde7e4aSAndre Fischer // top level elements 1246cde7e4aSAndre Fischer for (final Element aElement : maSchemaBase.TopLevelElements.GetSorted()) 12562886075SAndre Fischer ProcessType( 12662886075SAndre Fischer aElement, 12762886075SAndre Fischer maStateContext.GetStartState(), 12862886075SAndre Fischer maStateContext.GetStartState(), 12962886075SAndre Fischer aEndState); 1306cde7e4aSAndre Fischer 131*7d97ce35SAndre Fischer return new FiniteAutomaton(maStateContext, null, null); 1326cde7e4aSAndre Fischer } 1336cde7e4aSAndre Fischer 1346cde7e4aSAndre Fischer 1356cde7e4aSAndre Fischer 1366cde7e4aSAndre Fischer CreateForComplexType(final ComplexType aComplexType)1376cde7e4aSAndre Fischer private FiniteAutomaton CreateForComplexType (final ComplexType aComplexType) 1386cde7e4aSAndre Fischer { 13962886075SAndre Fischer maStateContext = new StateContext( 1406cde7e4aSAndre Fischer maStateContainer, 1416cde7e4aSAndre Fischer aComplexType.GetName().GetStateName()); 14262886075SAndre Fischer maAttributes = new Vector<>(); 14362886075SAndre Fischer final State aEndState = maStateContext.CreateEndState(); 14462886075SAndre Fischer ProcessType( 14562886075SAndre Fischer aComplexType, 14662886075SAndre Fischer maStateContext.GetStartState(), 14762886075SAndre Fischer maStateContext.GetStartState(), 14862886075SAndre Fischer aEndState); 14962886075SAndre Fischer return new FiniteAutomaton( 15062886075SAndre Fischer maStateContext, 151*7d97ce35SAndre Fischer maAttributes, 152*7d97ce35SAndre Fischer aComplexType.GetLocation()); 15362886075SAndre Fischer } 15462886075SAndre Fischer 15562886075SAndre Fischer 15662886075SAndre Fischer 157*7d97ce35SAndre Fischer 15862886075SAndre Fischer @Override Visit(final All aAll)15962886075SAndre Fischer public void Visit (final All aAll) 16062886075SAndre Fischer { 161*7d97ce35SAndre Fischer maLog.AddComment("All"); 16262886075SAndre Fischer ProcessAttributes(aAll); 16362886075SAndre Fischer 16462886075SAndre Fischer // Make a transformation of the children into a choice of sequences that 16562886075SAndre Fischer // can then be processed by already existing Visit() methods. 16662886075SAndre Fischer // These sequences enumerate all permutations of the original children. 16762886075SAndre Fischer final INode aReplacement = GetAllReplacement(aAll); 16862886075SAndre Fischer 16962886075SAndre Fischer final State aLocalStartState = maStateContext.CreateState( 17062886075SAndre Fischer maCurrentContext.BaseState, 17162886075SAndre Fischer "As"); 17262886075SAndre Fischer final State aLocalEndState = maStateContext.CreateState( 17362886075SAndre Fischer maCurrentContext.BaseState, 17462886075SAndre Fischer "Ae"); 17562886075SAndre Fischer 176*7d97ce35SAndre Fischer maLog.StartBlock(); 17762886075SAndre Fischer AddEpsilonTransition(maCurrentContext.StartState, aLocalStartState); 178*7d97ce35SAndre Fischer final long nStartTime = System.currentTimeMillis(); 17962886075SAndre Fischer ProcessType( 18062886075SAndre Fischer aReplacement, 18162886075SAndre Fischer maStateContext.CreateState(maCurrentContext.BaseState, "A"), 18262886075SAndre Fischer aLocalStartState, 18362886075SAndre Fischer aLocalEndState); 184*7d97ce35SAndre Fischer final long nEndTime = System.currentTimeMillis(); 185*7d97ce35SAndre Fischer System.out.printf("processed 'all' children in %fs\n", (nEndTime-nStartTime)/1000.0); 18662886075SAndre Fischer AddEpsilonTransition(aLocalEndState, maCurrentContext.EndState); 187*7d97ce35SAndre Fischer maLog.EndBlock(); 18862886075SAndre Fischer } 18962886075SAndre Fischer 19062886075SAndre Fischer 19162886075SAndre Fischer 19262886075SAndre Fischer 19362886075SAndre Fischer @Override Visit(final Any aAny)19462886075SAndre Fischer public void Visit (final Any aAny) 19562886075SAndre Fischer { 19662886075SAndre Fischer assert(aAny.GetChildCount() == 0); 19762886075SAndre Fischer 198*7d97ce35SAndre Fischer maLog.AddComment("Any"); 19962886075SAndre Fischer ProcessAttributes(aAny); 20062886075SAndre Fischer 20162886075SAndre Fischer AddSkipTransition( 20262886075SAndre Fischer maCurrentContext.StartState, 20362886075SAndre Fischer new SkipData( 20462886075SAndre Fischer aAny.GetProcessContentsFlag(), 20562886075SAndre Fischer aAny.GetNamespaces())); 20662886075SAndre Fischer AddEpsilonTransition(maCurrentContext.StartState, maCurrentContext.EndState); 20762886075SAndre Fischer } 20862886075SAndre Fischer 20962886075SAndre Fischer 21062886075SAndre Fischer 21162886075SAndre Fischer 21262886075SAndre Fischer @Override Visit(final ComplexContent aComplexContent)21362886075SAndre Fischer public void Visit (final ComplexContent aComplexContent) 21462886075SAndre Fischer { 21562886075SAndre Fischer assert(aComplexContent.GetChildCount() == 1); 21662886075SAndre Fischer 217*7d97ce35SAndre Fischer maLog.AddComment ("Complex Content."); 21862886075SAndre Fischer ProcessAttributes(aComplexContent); 21962886075SAndre Fischer 220*7d97ce35SAndre Fischer maLog.StartBlock(); 22162886075SAndre Fischer ProcessType( 22262886075SAndre Fischer aComplexContent.GetChildren().iterator().next(), 22362886075SAndre Fischer maCurrentContext.BaseState, 22462886075SAndre Fischer maCurrentContext.StartState, 22562886075SAndre Fischer maCurrentContext.EndState); 226*7d97ce35SAndre Fischer maLog.EndBlock(); 22762886075SAndre Fischer } 22862886075SAndre Fischer 22962886075SAndre Fischer 23062886075SAndre Fischer 23162886075SAndre Fischer 23262886075SAndre Fischer @Override Visit(final ComplexType aComplexType)23362886075SAndre Fischer public void Visit (final ComplexType aComplexType) 23462886075SAndre Fischer { 23562886075SAndre Fischer if (maLog != null) 23662886075SAndre Fischer { 237*7d97ce35SAndre Fischer maLog.printf("\n"); 238*7d97ce35SAndre Fischer maLog.AddComment ("Complex Type %s defined in %s.", 23962886075SAndre Fischer aComplexType.GetName().GetDisplayName(), 24062886075SAndre Fischer aComplexType.GetLocation()); 24162886075SAndre Fischer } 24262886075SAndre Fischer ProcessAttributes(aComplexType); 24362886075SAndre Fischer 244*7d97ce35SAndre Fischer maLog.StartBlock(); 24562886075SAndre Fischer maLog.printf("%sstarting at state %s\n", msLogIndentation, maCurrentContext.StartState.GetFullname()); 24662886075SAndre Fischer 24762886075SAndre Fischer if (GetElementCount(aComplexType) == 0) 24862886075SAndre Fischer { 24962886075SAndre Fischer // There are elements. Therefore there will be no transitions. 25062886075SAndre Fischer // The start state is accepting and the end state is not necessary. 25162886075SAndre Fischer maCurrentContext.StartState.SetIsAccepting(); 25262886075SAndre Fischer maStateContext.RemoveState(maCurrentContext.EndState); 25362886075SAndre Fischer } 25462886075SAndre Fischer 25562886075SAndre Fischer for (final INode aChild : aComplexType.GetChildren()) 25662886075SAndre Fischer ProcessType(aChild, maCurrentContext.BaseState, maCurrentContext.StartState, maCurrentContext.EndState); 25762886075SAndre Fischer 258*7d97ce35SAndre Fischer maLog.EndBlock(); 25962886075SAndre Fischer } 26062886075SAndre Fischer 26162886075SAndre Fischer 26262886075SAndre Fischer 26362886075SAndre Fischer 26462886075SAndre Fischer @Override Visit(final ComplexTypeReference aNode)26562886075SAndre Fischer public void Visit (final ComplexTypeReference aNode) 26662886075SAndre Fischer { 26762886075SAndre Fischer throw new RuntimeException("can not handle "+aNode.toString()); 26862886075SAndre Fischer } 26962886075SAndre Fischer 27062886075SAndre Fischer 27162886075SAndre Fischer 27262886075SAndre Fischer 27362886075SAndre Fischer @Override Visit(final Choice aChoice)27462886075SAndre Fischer public void Visit (final Choice aChoice) 27562886075SAndre Fischer { 276*7d97ce35SAndre Fischer maLog.AddComment("Choice"); 27762886075SAndre Fischer ProcessAttributes(aChoice); 27862886075SAndre Fischer 27962886075SAndre Fischer final State aLocalStartState = maStateContext.CreateState(maCurrentContext.BaseState, "Cs"); 28062886075SAndre Fischer final State aLocalEndState = maStateContext.CreateState(maCurrentContext.BaseState, "Ce"); 281*7d97ce35SAndre Fischer maLog.StartBlock(); 28262886075SAndre Fischer AddEpsilonTransition(maCurrentContext.StartState, aLocalStartState); 28362886075SAndre Fischer 28462886075SAndre Fischer int nStateIndex = 0; 28562886075SAndre Fischer for (final INode aChild : aChoice.GetChildren()) 28662886075SAndre Fischer { 28762886075SAndre Fischer ProcessType( 28862886075SAndre Fischer aChild, 28962886075SAndre Fischer maStateContext.CreateState(maCurrentContext.BaseState, "C"+nStateIndex++), 29062886075SAndre Fischer aLocalStartState, 29162886075SAndre Fischer aLocalEndState); 29262886075SAndre Fischer } 29362886075SAndre Fischer AddEpsilonTransition(aLocalEndState, maCurrentContext.EndState); 294*7d97ce35SAndre Fischer maLog.EndBlock(); 29562886075SAndre Fischer } 29662886075SAndre Fischer 29762886075SAndre Fischer 29862886075SAndre Fischer 29962886075SAndre Fischer 30062886075SAndre Fischer @Override Visit(final Element aElement)30162886075SAndre Fischer public void Visit (final Element aElement) 30262886075SAndre Fischer { 30362886075SAndre Fischer assert(aElement.GetChildCount()==0); 30462886075SAndre Fischer 305*7d97ce35SAndre Fischer maLog.AddComment("Element: on '%s' go from %s to %s via %s", 30662886075SAndre Fischer aElement.GetElementName().GetDisplayName(), 30762886075SAndre Fischer maCurrentContext.StartState.GetFullname(), 30862886075SAndre Fischer maCurrentContext.EndState.GetFullname(), 30962886075SAndre Fischer aElement.GetTypeName().GetStateName()); 31062886075SAndre Fischer ProcessAttributes(aElement); 31162886075SAndre Fischer 31262886075SAndre Fischer final Transition aTransition = new Transition( 31362886075SAndre Fischer maCurrentContext.StartState, 31462886075SAndre Fischer maCurrentContext.EndState, 31562886075SAndre Fischer aElement.GetElementName(), 31662886075SAndre Fischer aElement.GetTypeName().GetStateName()); 31762886075SAndre Fischer maCurrentContext.StartState.AddTransition(aTransition); 318*7d97ce35SAndre Fischer 319*7d97ce35SAndre Fischer // For elements whose type is a simple type we have to remember that 320*7d97ce35SAndre Fischer // simple type for later (and then create an NFA for it.) 321*7d97ce35SAndre Fischer final INode aSimpleType = maSchemaBase.GetSimpleTypeForName( 322*7d97ce35SAndre Fischer aElement.GetTypeName()); 323*7d97ce35SAndre Fischer if (aSimpleType != null) 324*7d97ce35SAndre Fischer maElementSimpleTypes.add(aSimpleType); 32562886075SAndre Fischer } 32662886075SAndre Fischer 32762886075SAndre Fischer 32862886075SAndre Fischer 32962886075SAndre Fischer 33062886075SAndre Fischer @Override Visit(final ElementReference aReference)33162886075SAndre Fischer public void Visit (final ElementReference aReference) 33262886075SAndre Fischer { 33362886075SAndre Fischer assert(aReference.GetChildCount() == 0); 33462886075SAndre Fischer 335*7d97ce35SAndre Fischer maLog.AddComment("Element reference to %s", aReference.GetReferencedElementName()); 33662886075SAndre Fischer ProcessAttributes(aReference); 33762886075SAndre Fischer 33862886075SAndre Fischer final Element aElement = aReference.GetReferencedElement(maSchemaBase); 33962886075SAndre Fischer if (aElement == null) 34062886075SAndre Fischer throw new RuntimeException("can't find referenced element "+aReference.GetReferencedElementName()); 341*7d97ce35SAndre Fischer maLog.StartBlock(); 34262886075SAndre Fischer ProcessType(aElement, maCurrentContext.BaseState, maCurrentContext.StartState, maCurrentContext.EndState); 343*7d97ce35SAndre Fischer maLog.EndBlock(); 34462886075SAndre Fischer } 34562886075SAndre Fischer 34662886075SAndre Fischer 34762886075SAndre Fischer 34862886075SAndre Fischer 34962886075SAndre Fischer /** Treat extension nodes like sequences (for now). 35062886075SAndre Fischer */ 35162886075SAndre Fischer @Override Visit(final Extension aExtension)35262886075SAndre Fischer public void Visit (final Extension aExtension) 35362886075SAndre Fischer { 35462886075SAndre Fischer assert(aExtension.GetChildCount() <= 1); 35562886075SAndre Fischer 356*7d97ce35SAndre Fischer maLog.AddComment("Extension of base type %s", aExtension.GetBaseTypeName()); 35762886075SAndre Fischer ProcessAttributes(aExtension); 35862886075SAndre Fischer 35962886075SAndre Fischer final Vector<INode> aNodes = aExtension.GetTypeNodes(maSchemaBase); 36062886075SAndre Fischer 361*7d97ce35SAndre Fischer maLog.StartBlock(); 36262886075SAndre Fischer int nStateIndex = 0; 36362886075SAndre Fischer State aCurrentState = maStateContext.CreateState(maCurrentContext.BaseState, "E"+nStateIndex++); 36462886075SAndre Fischer AddEpsilonTransition(maCurrentContext.StartState, aCurrentState); 36562886075SAndre Fischer 36662886075SAndre Fischer State aNextState = maStateContext.CreateState(maCurrentContext.BaseState, "E"+nStateIndex++); 36762886075SAndre Fischer ProcessType(aExtension.GetReferencedNode(maSchemaBase), aCurrentState, aCurrentState, aNextState); 36862886075SAndre Fischer aCurrentState = aNextState; 36962886075SAndre Fischer 37062886075SAndre Fischer for (final INode aChild : aNodes) 37162886075SAndre Fischer { 37262886075SAndre Fischer aNextState = maStateContext.CreateState(maCurrentContext.BaseState, "E"+nStateIndex++); 37362886075SAndre Fischer ProcessType(aChild, aCurrentState, aCurrentState, aNextState); 37462886075SAndre Fischer aCurrentState = aNextState; 37562886075SAndre Fischer } 37662886075SAndre Fischer AddEpsilonTransition(aCurrentState, maCurrentContext.EndState); 377*7d97ce35SAndre Fischer maLog.EndBlock(); 37862886075SAndre Fischer } 37962886075SAndre Fischer 38062886075SAndre Fischer 38162886075SAndre Fischer 38262886075SAndre Fischer 38362886075SAndre Fischer @Override Visit(final Group aGroup)38462886075SAndre Fischer public void Visit (final Group aGroup) 38562886075SAndre Fischer { 38662886075SAndre Fischer assert(aGroup.GetChildCount() == 1); 38762886075SAndre Fischer 388*7d97ce35SAndre Fischer maLog.AddComment("Group %s", aGroup.GetName()); 38962886075SAndre Fischer ProcessAttributes(aGroup); 39062886075SAndre Fischer 391*7d97ce35SAndre Fischer maLog.StartBlock(); 39262886075SAndre Fischer final State aGroupBaseState = maStateContext.CreateState(maCurrentContext.BaseState, "G"); 39362886075SAndre Fischer ProcessType( 39462886075SAndre Fischer aGroup.GetOnlyChild(), 39562886075SAndre Fischer aGroupBaseState, 39662886075SAndre Fischer maCurrentContext.StartState, 39762886075SAndre Fischer maCurrentContext.EndState); 398*7d97ce35SAndre Fischer maLog.EndBlock(); 39962886075SAndre Fischer } 40062886075SAndre Fischer 40162886075SAndre Fischer 40262886075SAndre Fischer 40362886075SAndre Fischer 40462886075SAndre Fischer @Override Visit(final GroupReference aReference)40562886075SAndre Fischer public void Visit (final GroupReference aReference) 40662886075SAndre Fischer { 407*7d97ce35SAndre Fischer maLog.AddComment("Group reference to %s", aReference.GetReferencedGroupName()); 40862886075SAndre Fischer ProcessAttributes(aReference); 40962886075SAndre Fischer 41062886075SAndre Fischer final Group aGroup = aReference.GetReferencedGroup(maSchemaBase); 41162886075SAndre Fischer if (aGroup == null) 41262886075SAndre Fischer throw new RuntimeException("can't find referenced group "+aReference.GetReferencedGroupName()); 41362886075SAndre Fischer 414*7d97ce35SAndre Fischer maLog.StartBlock(); 41562886075SAndre Fischer ProcessType(aGroup, maCurrentContext.BaseState, maCurrentContext.StartState, maCurrentContext.EndState); 416*7d97ce35SAndre Fischer maLog.EndBlock(); 41762886075SAndre Fischer } 41862886075SAndre Fischer 41962886075SAndre Fischer 42062886075SAndre Fischer 42162886075SAndre Fischer 42262886075SAndre Fischer /** An occurrence indicator defines how many times the single child can occur. 42362886075SAndre Fischer * The minimum value defines the mandatory number of times. The maximum value 42462886075SAndre Fischer * defines the optional number. 42562886075SAndre Fischer */ 42662886075SAndre Fischer @Override Visit(final OccurrenceIndicator aOccurrence)42762886075SAndre Fischer public void Visit (final OccurrenceIndicator aOccurrence) 42862886075SAndre Fischer { 42962886075SAndre Fischer assert(aOccurrence.GetChildCount() == 1); 43062886075SAndre Fischer 431*7d97ce35SAndre Fischer maLog.AddComment("OccurrenceIndicator %s->%s", 43262886075SAndre Fischer aOccurrence.GetDisplayMinimum(), 43362886075SAndre Fischer aOccurrence.GetDisplayMaximum()); 43462886075SAndre Fischer ProcessAttributes(aOccurrence); 43562886075SAndre Fischer 436*7d97ce35SAndre Fischer maLog.StartBlock(); 43762886075SAndre Fischer 43862886075SAndre Fischer final INode aChild = aOccurrence.GetChildren().iterator().next(); 43962886075SAndre Fischer 44062886075SAndre Fischer int nIndex = 0; 44162886075SAndre Fischer State aCurrentState = maStateContext.CreateState(maCurrentContext.BaseState, "O"+nIndex++); 44262886075SAndre Fischer AddEpsilonTransition(maCurrentContext.StartState, aCurrentState); 44362886075SAndre Fischer 44462886075SAndre Fischer if (aOccurrence.GetMinimum() == 0) 44562886075SAndre Fischer { 44662886075SAndre Fischer // A zero minimum means that all occurrences are optional. 44762886075SAndre Fischer // Add a short circuit from start to end. 448*7d97ce35SAndre Fischer maLog.AddComment("Occurrence: make whole element optional (min==0)"); 44962886075SAndre Fischer AddEpsilonTransition(maCurrentContext.StartState, maCurrentContext.EndState); 45062886075SAndre Fischer } 45162886075SAndre Fischer else 45262886075SAndre Fischer { 45362886075SAndre Fischer // Write a row of mandatory transitions for the minimum. 45462886075SAndre Fischer for (; nIndex<=aOccurrence.GetMinimum(); ++nIndex) 45562886075SAndre Fischer { 45662886075SAndre Fischer // Add transition i-1 -> i (i == nIndex). 45762886075SAndre Fischer final State aNextState = maStateContext.CreateState(maCurrentContext.BaseState, "O"+nIndex); 458*7d97ce35SAndre Fischer maLog.AddComment("Occurrence: move from %d -> %d (%s -> %s) (minimum)", 45962886075SAndre Fischer nIndex-1, 46062886075SAndre Fischer nIndex, 46162886075SAndre Fischer aCurrentState, 46262886075SAndre Fischer aNextState); 463*7d97ce35SAndre Fischer maLog.StartBlock(); 46462886075SAndre Fischer ProcessType(aChild, aCurrentState, aCurrentState, aNextState); 465*7d97ce35SAndre Fischer maLog.EndBlock(); 46662886075SAndre Fischer aCurrentState = aNextState; 46762886075SAndre Fischer } 46862886075SAndre Fischer } 46962886075SAndre Fischer 47062886075SAndre Fischer if (aOccurrence.GetMaximum() == OccurrenceIndicator.unbounded) 47162886075SAndre Fischer { 47262886075SAndre Fischer // Write loop on last state when max is unbounded. 47362886075SAndre Fischer 47462886075SAndre Fischer // last -> loop 47562886075SAndre Fischer final State aLoopState = maStateContext.CreateState(maCurrentContext.BaseState, "OL"); 476*7d97ce35SAndre Fischer maLog.AddComment("Occurrence: forward to loop (maximum)"); 47762886075SAndre Fischer AddEpsilonTransition(aCurrentState, aLoopState); 47862886075SAndre Fischer 47962886075SAndre Fischer // loop -> loop 480*7d97ce35SAndre Fischer maLog.AddComment("Occurrence: loop"); 481*7d97ce35SAndre Fischer maLog.StartBlock(); 48262886075SAndre Fischer ProcessType(aChild, aLoopState, aLoopState, aLoopState); 483*7d97ce35SAndre Fischer maLog.EndBlock(); 48462886075SAndre Fischer 48562886075SAndre Fischer // -> end 486*7d97ce35SAndre Fischer maLog.AddComment("Occurrence: forward to local end"); 48762886075SAndre Fischer AddEpsilonTransition(aLoopState, maCurrentContext.EndState); 48862886075SAndre Fischer } 48962886075SAndre Fischer else 49062886075SAndre Fischer { 49162886075SAndre Fischer // Write a row of optional transitions for the maximum. 49262886075SAndre Fischer for (; nIndex<=aOccurrence.GetMaximum(); ++nIndex) 49362886075SAndre Fischer { 49462886075SAndre Fischer if (nIndex > 0) 49562886075SAndre Fischer { 49662886075SAndre Fischer // i-1 -> end 497*7d97ce35SAndre Fischer maLog.AddComment("Occurrence: make %d optional (maximum)", nIndex-1); 49862886075SAndre Fischer AddEpsilonTransition(aCurrentState, maCurrentContext.EndState); 49962886075SAndre Fischer } 50062886075SAndre Fischer 50162886075SAndre Fischer // i-1 -> i 50262886075SAndre Fischer final State aNextState = maStateContext.CreateState(maCurrentContext.BaseState, "O"+nIndex); 503*7d97ce35SAndre Fischer maLog.AddComment("Occurrence: %d -> %d (%s -> %s) (maximum)", 50462886075SAndre Fischer nIndex-1, 50562886075SAndre Fischer nIndex, 50662886075SAndre Fischer aCurrentState, 50762886075SAndre Fischer aNextState); 508*7d97ce35SAndre Fischer maLog.StartBlock(); 50962886075SAndre Fischer ProcessType(aChild, aCurrentState, aCurrentState, aNextState); 510*7d97ce35SAndre Fischer maLog.EndBlock(); 51162886075SAndre Fischer 51262886075SAndre Fischer aCurrentState = aNextState; 51362886075SAndre Fischer } 51462886075SAndre Fischer 51562886075SAndre Fischer // max -> end 516*7d97ce35SAndre Fischer maLog.AddComment("Occurrence: forward to local end"); 51762886075SAndre Fischer AddEpsilonTransition(aCurrentState, maCurrentContext.EndState); 51862886075SAndre Fischer } 519*7d97ce35SAndre Fischer maLog.EndBlock(); 52062886075SAndre Fischer } 52162886075SAndre Fischer 52262886075SAndre Fischer 52362886075SAndre Fischer 52462886075SAndre Fischer 52562886075SAndre Fischer /** Ordered sequence of nodes. 52662886075SAndre Fischer * For n nodes create states S0 to Sn where Si and Si+1 become start and 52762886075SAndre Fischer * end states for the i-th child. 52862886075SAndre Fischer */ 52962886075SAndre Fischer @Override Visit(final Sequence aSequence)53062886075SAndre Fischer public void Visit (final Sequence aSequence) 53162886075SAndre Fischer { 532*7d97ce35SAndre Fischer maLog.AddComment("Sequence."); 53362886075SAndre Fischer ProcessAttributes(aSequence); 53462886075SAndre Fischer 535*7d97ce35SAndre Fischer maLog.StartBlock(); 53662886075SAndre Fischer int nStateIndex = 0; 53762886075SAndre Fischer State aCurrentState = maStateContext.CreateState(maCurrentContext.BaseState, "S"+nStateIndex++); 53862886075SAndre Fischer AddEpsilonTransition(maCurrentContext.StartState, aCurrentState); 53962886075SAndre Fischer for (final INode aChild : aSequence.GetChildren()) 54062886075SAndre Fischer { 54162886075SAndre Fischer final State aNextState = maStateContext.CreateState(maCurrentContext.BaseState, "S"+nStateIndex++); 54262886075SAndre Fischer ProcessType(aChild, aCurrentState, aCurrentState, aNextState); 54362886075SAndre Fischer aCurrentState = aNextState; 54462886075SAndre Fischer } 54562886075SAndre Fischer AddEpsilonTransition(aCurrentState, maCurrentContext.EndState); 546*7d97ce35SAndre Fischer maLog.EndBlock(); 54762886075SAndre Fischer } 54862886075SAndre Fischer 54962886075SAndre Fischer 55062886075SAndre Fischer 55162886075SAndre Fischer 55262886075SAndre Fischer @Override Visit(final BuiltIn aNode)55362886075SAndre Fischer public void Visit (final BuiltIn aNode) 55462886075SAndre Fischer { 555*7d97ce35SAndre Fischer // Ignored. 556*7d97ce35SAndre Fischer //throw new RuntimeException("can not handle "+aNode.toString()); 55762886075SAndre Fischer } 55862886075SAndre Fischer 55962886075SAndre Fischer 56062886075SAndre Fischer 56162886075SAndre Fischer 56262886075SAndre Fischer @Override Visit(final List aNode)56362886075SAndre Fischer public void Visit (final List aNode) 56462886075SAndre Fischer { 56562886075SAndre Fischer throw new RuntimeException("can not handle "+aNode.toString()); 56662886075SAndre Fischer } 56762886075SAndre Fischer 56862886075SAndre Fischer 56962886075SAndre Fischer 57062886075SAndre Fischer 57162886075SAndre Fischer @Override Visit(final Restriction aNode)57262886075SAndre Fischer public void Visit (final Restriction aNode) 57362886075SAndre Fischer { 57462886075SAndre Fischer throw new RuntimeException("can not handle "+aNode.toString()); 57562886075SAndre Fischer } 57662886075SAndre Fischer 57762886075SAndre Fischer 57862886075SAndre Fischer 57962886075SAndre Fischer @Override Visit(final SimpleContent aNode)58062886075SAndre Fischer public void Visit (final SimpleContent aNode) 58162886075SAndre Fischer { 582*7d97ce35SAndre Fischer maLog.AddComment("SimpleContent."); 58362886075SAndre Fischer ProcessAttributes(aNode); 58462886075SAndre Fischer 58562886075SAndre Fischer for (final INode aChild : aNode.GetChildren()) 58662886075SAndre Fischer ProcessType(aChild, maCurrentContext.BaseState, maCurrentContext.StartState, maCurrentContext.EndState); 58762886075SAndre Fischer } 58862886075SAndre Fischer 58962886075SAndre Fischer 59062886075SAndre Fischer 59162886075SAndre Fischer 59262886075SAndre Fischer @Override Visit(final SimpleType aNode)59362886075SAndre Fischer public void Visit (final SimpleType aNode) 59462886075SAndre Fischer { 595*7d97ce35SAndre Fischer maLog.AddComment("SimpleType."); 596*7d97ce35SAndre Fischer //for (final INode aChild : aNode.GetChildren()) 597*7d97ce35SAndre Fischer //ProcessType(aChild, maCurrentContext.BaseState, maCurrentContext.StartState, maCurrentContext.EndState); 59862886075SAndre Fischer } 59962886075SAndre Fischer 60062886075SAndre Fischer 60162886075SAndre Fischer 60262886075SAndre Fischer 60362886075SAndre Fischer @Override Visit(final SimpleTypeReference aNode)60462886075SAndre Fischer public void Visit (final SimpleTypeReference aNode) 60562886075SAndre Fischer { 60662886075SAndre Fischer throw new RuntimeException("can not handle "+aNode.toString()); 60762886075SAndre Fischer } 60862886075SAndre Fischer 60962886075SAndre Fischer 61062886075SAndre Fischer 61162886075SAndre Fischer 61262886075SAndre Fischer @Override Visit(final Union aNode)61362886075SAndre Fischer public void Visit (final Union aNode) 61462886075SAndre Fischer { 61562886075SAndre Fischer throw new RuntimeException("can not handle "+aNode.toString()); 61662886075SAndre Fischer } 61762886075SAndre Fischer 61862886075SAndre Fischer 61962886075SAndre Fischer 62062886075SAndre Fischer 62162886075SAndre Fischer @Override Visit(final AttributeGroup aNode)62262886075SAndre Fischer public void Visit (final AttributeGroup aNode) 62362886075SAndre Fischer { 62462886075SAndre Fischer throw new RuntimeException("can not handle "+aNode.toString()); 62562886075SAndre Fischer } 62662886075SAndre Fischer 62762886075SAndre Fischer 62862886075SAndre Fischer 62962886075SAndre Fischer 63062886075SAndre Fischer @Override Visit(final AttributeReference aNode)63162886075SAndre Fischer public void Visit (final AttributeReference aNode) 63262886075SAndre Fischer { 63362886075SAndre Fischer throw new RuntimeException("can not handle "+aNode.toString()); 63462886075SAndre Fischer } 63562886075SAndre Fischer 63662886075SAndre Fischer 63762886075SAndre Fischer 63862886075SAndre Fischer 63962886075SAndre Fischer @Override Visit(final Attribute aNode)64062886075SAndre Fischer public void Visit (final Attribute aNode) 64162886075SAndre Fischer { 64262886075SAndre Fischer throw new RuntimeException("can not handle "+aNode.toString()); 64362886075SAndre Fischer } 64462886075SAndre Fischer 64562886075SAndre Fischer 64662886075SAndre Fischer 64762886075SAndre Fischer 64862886075SAndre Fischer @Override Visit(final AttributeGroupReference aNode)64962886075SAndre Fischer public void Visit (final AttributeGroupReference aNode) 65062886075SAndre Fischer { 65162886075SAndre Fischer throw new RuntimeException("can not handle "+aNode.toString()); 65262886075SAndre Fischer } 65362886075SAndre Fischer 65462886075SAndre Fischer 65562886075SAndre Fischer 65662886075SAndre Fischer ProcessType( final INode aNode, final State aBaseState, final State aStartState, final State aEndState)65762886075SAndre Fischer private void ProcessType ( 65862886075SAndre Fischer final INode aNode, 65962886075SAndre Fischer final State aBaseState, 66062886075SAndre Fischer final State aStartState, 66162886075SAndre Fischer final State aEndState) 66262886075SAndre Fischer { 66362886075SAndre Fischer maContextStack.push(maCurrentContext); 66462886075SAndre Fischer maCurrentContext = new Context(aBaseState, aStartState, aEndState); 66562886075SAndre Fischer aNode.AcceptVisitor(this); 66662886075SAndre Fischer maCurrentContext = maContextStack.pop(); 66762886075SAndre Fischer } 66862886075SAndre Fischer 66962886075SAndre Fischer 67062886075SAndre Fischer 67162886075SAndre Fischer AddEpsilonTransition( final State aStartState, final State aEndState)67262886075SAndre Fischer private void AddEpsilonTransition ( 67362886075SAndre Fischer final State aStartState, 67462886075SAndre Fischer final State aEndState) 67562886075SAndre Fischer { 67662886075SAndre Fischer // Silently ignore epsilon transitions from a state to itself. 67762886075SAndre Fischer // They may indicate a problem but usually are just artifacts 67862886075SAndre Fischer // that can be safely ignored. 67962886075SAndre Fischer if (aStartState == aEndState) 68062886075SAndre Fischer return; 68162886075SAndre Fischer else 68262886075SAndre Fischer { 68362886075SAndre Fischer final EpsilonTransition aTransition = new EpsilonTransition( 68462886075SAndre Fischer aStartState, 68562886075SAndre Fischer aEndState); 68662886075SAndre Fischer aStartState.AddEpsilonTransition(aTransition); 68762886075SAndre Fischer 68862886075SAndre Fischer if (maLog != null) 68962886075SAndre Fischer { 69062886075SAndre Fischer maLog.printf("%sepsilon transition from %s to %s\n", 69162886075SAndre Fischer msLogIndentation, 69262886075SAndre Fischer aStartState.GetFullname(), 69362886075SAndre Fischer aEndState.GetFullname()); 69462886075SAndre Fischer } 69562886075SAndre Fischer } 69662886075SAndre Fischer } 69762886075SAndre Fischer 69862886075SAndre Fischer 69962886075SAndre Fischer 70062886075SAndre Fischer GetElementCount(final INode aNode)70162886075SAndre Fischer private int GetElementCount (final INode aNode) 70262886075SAndre Fischer { 70362886075SAndre Fischer 70462886075SAndre Fischer class Visitor extends NodeVisitorAdapter 70562886075SAndre Fischer { 70662886075SAndre Fischer int nElementCount = 0; 70762886075SAndre Fischer @Override public void Visit (final Element aElement) 70862886075SAndre Fischer { 70962886075SAndre Fischer ++nElementCount; 71062886075SAndre Fischer } 71162886075SAndre Fischer int GetElementCount () 71262886075SAndre Fischer { 71362886075SAndre Fischer return nElementCount; 71462886075SAndre Fischer } 71562886075SAndre Fischer }; 71662886075SAndre Fischer final Visitor aVisitor = new Visitor(); 71762886075SAndre Fischer for (final INode aChildNode : new DereferencingNodeIterator(aNode, maSchemaBase, false)) 71862886075SAndre Fischer { 71962886075SAndre Fischer aChildNode.AcceptVisitor(aVisitor); 72062886075SAndre Fischer } 72162886075SAndre Fischer return aVisitor.GetElementCount(); 72262886075SAndre Fischer } 72362886075SAndre Fischer 72462886075SAndre Fischer 72562886075SAndre Fischer 72662886075SAndre Fischer GetAllReplacement(final All aAll)72762886075SAndre Fischer private INode GetAllReplacement (final All aAll) 72862886075SAndre Fischer { 729*7d97ce35SAndre Fischer final long nStartTime = System.currentTimeMillis(); 730*7d97ce35SAndre Fischer 73162886075SAndre Fischer // By default each child of this node can appear exactly once, however 73262886075SAndre Fischer // the order is undefined. This corresponds to an enumeration of all 73362886075SAndre Fischer // permutations of the children. 73462886075SAndre Fischer 73562886075SAndre Fischer // Set up an array of all children. This array will be modified to contain 73662886075SAndre Fischer // all permutations. 73762886075SAndre Fischer final INode[] aNodes = new INode[aAll.GetChildCount()]; 73862886075SAndre Fischer final Iterator<INode> aChildren = aAll.GetChildren().iterator(); 73962886075SAndre Fischer for (int nIndex=0; aChildren.hasNext(); ++nIndex) 74062886075SAndre Fischer aNodes[nIndex] = aChildren.next(); 74162886075SAndre Fischer 74262886075SAndre Fischer final Location aLocation = aAll.GetLocation(); 74362886075SAndre Fischer final Choice aChoice = new Choice(aAll, aLocation); 74462886075SAndre Fischer 74562886075SAndre Fischer // Treat every permutation as sequence so that the whole set of permutations 74662886075SAndre Fischer // is equivalent to a choice of sequences. 74762886075SAndre Fischer int nCount = 0; 74862886075SAndre Fischer for (final PermutationIterator<INode> aIterator = new PermutationIterator<>(aNodes); aIterator.HasMore(); aIterator.Next()) 74962886075SAndre Fischer { 75062886075SAndre Fischer // Create a Sequence node for the current permutation and add it as 75162886075SAndre Fischer // choice to the Choice node. 75262886075SAndre Fischer final Sequence aSequence = new Sequence(aChoice, null, aLocation); 75362886075SAndre Fischer aChoice.AddChild(aSequence); 75462886075SAndre Fischer 75562886075SAndre Fischer for (final INode aNode : aNodes) 75662886075SAndre Fischer aSequence.AddChild(aNode); 75762886075SAndre Fischer 75862886075SAndre Fischer ++nCount; 75962886075SAndre Fischer } 760*7d97ce35SAndre Fischer final long nEndTime = System.currentTimeMillis(); 761*7d97ce35SAndre Fischer System.out.printf("created %d permutations in %fs\n", 762*7d97ce35SAndre Fischer nCount, 763*7d97ce35SAndre Fischer (nEndTime-nStartTime)/1000.0); 76462886075SAndre Fischer 76562886075SAndre Fischer return aChoice; 76662886075SAndre Fischer } 76762886075SAndre Fischer 76862886075SAndre Fischer 76962886075SAndre Fischer 77062886075SAndre Fischer 77162886075SAndre Fischer class Context 77262886075SAndre Fischer { Context( final State aBaseState, final State aStartState, final State aEndState)77362886075SAndre Fischer Context ( 77462886075SAndre Fischer final State aBaseState, 77562886075SAndre Fischer final State aStartState, 77662886075SAndre Fischer final State aEndState) 77762886075SAndre Fischer { 77862886075SAndre Fischer BaseState = aBaseState; 77962886075SAndre Fischer StartState = aStartState; 78062886075SAndre Fischer EndState = aEndState; 78162886075SAndre Fischer } 78262886075SAndre Fischer final State BaseState; 78362886075SAndre Fischer final State StartState; 78462886075SAndre Fischer final State EndState; 7856cde7e4aSAndre Fischer } 7866cde7e4aSAndre Fischer 7876cde7e4aSAndre Fischer 7886cde7e4aSAndre Fischer 7896cde7e4aSAndre Fischer 79062886075SAndre Fischer private StateContext maStateContext; 79162886075SAndre Fischer private final Stack<Context> maContextStack; 79262886075SAndre Fischer private Context maCurrentContext; 7936cde7e4aSAndre Fischer } 794