You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@xerces.apache.org by mr...@apache.org on 2007/02/23 17:53:59 UTC
svn commit: r511014 - in
/xerces/java/trunk/src/org/apache/xerces/impl/xs/models: CMBuilder.java
CMNodeFactory.java XSCMRepeatingLeaf.java XSDFACM.java
Author: mrglavas
Date: Fri Feb 23 08:53:57 2007
New Revision: 511014
URL: http://svn.apache.org/viewvc?view=rev&rev=511014
Log:
Fixing JIRA Bugs #206, #380 and #773:
http://issues.apache.org/jira/browse/XERCESJ-206
http://issues.apache.org/jira/browse/XERCESJ-380
http://issues.apache.org/jira/browse/XERCESJ-773
For larger values of maxOccurs in a schema document an OutOfMemoryError may occur when Xerces builds
the DFA representation. Similarly, large values of minOccurs with maxOccurs equal to unbounded may
exhaust the available memory. If enough space has been allocated on the heap the VM may not run out
of memory but it may take several minutes before processing completes. The workaround for this limitation
has always been for the schema author to change the value of maxOccurs to unbounded (and change minOccurs
to 1 or some small number).
For a number of users the workaround is unnacceptable and they really do need to work with the large
maxOccurs values. The following fix eliminates this long standing limtiation for a number of common
cases. We now build a representation of large minOccurs/maxOccurs in constant time and memory (which
uses a counter during validation) for element and wildcard particles when each model group particle
in the content model:
* has minOccurs/maxOccurs == 1; or
* contains only one element/wildcard particle with minOccurs/maxOccurs == 1
Handling sequences, choices and nested minOccurs/maxOccurs is somewhat tricker. We might tackle those
one day with a more general solution but what I've done for now should allivate the pain for a large
number of the users who couldn't workaround the limitation.
Added:
xerces/java/trunk/src/org/apache/xerces/impl/xs/models/XSCMRepeatingLeaf.java
Modified:
xerces/java/trunk/src/org/apache/xerces/impl/xs/models/CMBuilder.java
xerces/java/trunk/src/org/apache/xerces/impl/xs/models/CMNodeFactory.java
xerces/java/trunk/src/org/apache/xerces/impl/xs/models/XSDFACM.java
Modified: xerces/java/trunk/src/org/apache/xerces/impl/xs/models/CMBuilder.java
URL: http://svn.apache.org/viewvc/xerces/java/trunk/src/org/apache/xerces/impl/xs/models/CMBuilder.java?view=diff&rev=511014&r1=511013&r2=511014
==============================================================================
--- xerces/java/trunk/src/org/apache/xerces/impl/xs/models/CMBuilder.java (original)
+++ xerces/java/trunk/src/org/apache/xerces/impl/xs/models/CMBuilder.java Fri Feb 23 08:53:57 2007
@@ -126,7 +126,7 @@
fLeafCount = 0;
fParticleCount = 0;
// convert particle tree to CM tree
- CMNode node = buildSyntaxTree(particle);
+ CMNode node = useRepeatingLeafNodes(particle) ? buildCompactSyntaxTree(particle) : buildSyntaxTree(particle);
if (node == null)
return null;
// build DFA content model from the CM tree
@@ -302,5 +302,134 @@
}
return node;
+ }
+
+ // A special version of buildSyntaxTree() which builds a compact syntax tree
+ // containing compound leaf nodes which carry occurence information. This method
+ // for building the syntax tree is chosen over buildSyntaxTree() when
+ // useRepeatingLeafNodes() returns true.
+ private CMNode buildCompactSyntaxTree(XSParticleDecl particle) {
+ int maxOccurs = particle.fMaxOccurs;
+ int minOccurs = particle.fMinOccurs;
+ short type = particle.fType;
+ CMNode nodeRet = null;
+
+ if ((type == XSParticleDecl.PARTICLE_WILDCARD) ||
+ (type == XSParticleDecl.PARTICLE_ELEMENT)) {
+ return buildCompactSyntaxTree2(particle, minOccurs, maxOccurs);
+ }
+ else if (type == XSParticleDecl.PARTICLE_MODELGROUP) {
+ XSModelGroupImpl group = (XSModelGroupImpl)particle.fValue;
+ if (group.fParticleCount == 1 && (minOccurs != 1 || maxOccurs != 1)) {
+ return buildCompactSyntaxTree2(group.fParticles[0], minOccurs, maxOccurs);
+ }
+ else {
+ CMNode temp = null;
+
+ // when the model group is a choice of more than one particles, but
+ // only one of the particle is not empty, (for example
+ // <choice>
+ // <sequence/>
+ // <element name="e"/>
+ // </choice>
+ // ) we can't not return that one particle ("e"). instead, we should
+ // treat such particle as optional ("e?").
+ // the following boolean variable is true when there are at least
+ // 2 non-empty children.
+ boolean twoChildren = false;
+ for (int i = 0; i < group.fParticleCount; i++) {
+ // first convert each child to a CM tree
+ temp = buildCompactSyntaxTree(group.fParticles[i]);
+ // then combine them using binary operation
+ if (temp != null) {
+ if (nodeRet == null) {
+ nodeRet = temp;
+ }
+ else {
+ nodeRet = fNodeFactory.getCMBinOpNode(group.fCompositor, nodeRet, temp);
+ // record the fact that there are at least 2 children
+ twoChildren = true;
+ }
+ }
+ }
+ if (nodeRet != null) {
+ // when the group is "choice", there is only one non-empty
+ // child, and the group had more than one children, we need
+ // to create a zero-or-one (optional) node for the non-empty
+ // particle.
+ if (group.fCompositor == XSModelGroupImpl.MODELGROUP_CHOICE &&
+ !twoChildren && group.fParticleCount > 1) {
+ nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_ONE, nodeRet);
+ }
+ }
+ }
+ }
+ return nodeRet;
+ }
+
+ private CMNode buildCompactSyntaxTree2(XSParticleDecl particle, int minOccurs, int maxOccurs) {
+ // Convert element and wildcard particles to leaf nodes. Wrap repeating particles in a CMUniOpNode.
+ CMNode nodeRet = null;
+ if (minOccurs == 1 && maxOccurs == 1) {
+ nodeRet = fNodeFactory.getCMLeafNode(particle.fType, particle.fValue, fParticleCount++, fLeafCount++);
+ }
+ else if (minOccurs == 0 && maxOccurs == 1) {
+ // zero or one
+ nodeRet = fNodeFactory.getCMLeafNode(particle.fType, particle.fValue, fParticleCount++, fLeafCount++);
+ nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_ONE, nodeRet);
+ }
+ else if (minOccurs == 0 && maxOccurs==SchemaSymbols.OCCURRENCE_UNBOUNDED) {
+ // zero or more
+ nodeRet = fNodeFactory.getCMLeafNode(particle.fType, particle.fValue, fParticleCount++, fLeafCount++);
+ nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_MORE, nodeRet);
+ }
+ else if (minOccurs == 1 && maxOccurs==SchemaSymbols.OCCURRENCE_UNBOUNDED) {
+ // one or more
+ nodeRet = fNodeFactory.getCMLeafNode(particle.fType, particle.fValue, fParticleCount++, fLeafCount++);
+ nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ONE_OR_MORE, nodeRet);
+ }
+ else {
+ // {n,m}: Instead of expanding this out, create a compound leaf node which carries the
+ // occurence information and wrap it in the appropriate CMUniOpNode.
+ nodeRet = fNodeFactory.getCMRepeatingLeafNode(particle.fType, particle.fValue, minOccurs, maxOccurs, fParticleCount++, fLeafCount++);
+ if (minOccurs == 0) {
+ nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ZERO_OR_MORE, nodeRet);
+ }
+ else {
+ nodeRet = fNodeFactory.getCMUniOpNode(XSParticleDecl.PARTICLE_ONE_OR_MORE, nodeRet);
+ }
+ }
+ return nodeRet;
+ }
+
+ // This method checks if this particle can be transformed into a compact syntax
+ // tree containing compound leaf nodes which carry occurence information. Currently
+ // it returns true if each model group has minOccurs/maxOccurs == 1 or
+ // contains only one element/wildcard particle with minOccurs/maxOccurs == 1.
+ private boolean useRepeatingLeafNodes(XSParticleDecl particle) {
+ int maxOccurs = particle.fMaxOccurs;
+ int minOccurs = particle.fMinOccurs;
+ short type = particle.fType;
+
+ if (type == XSParticleDecl.PARTICLE_MODELGROUP) {
+ XSModelGroupImpl group = (XSModelGroupImpl) particle.fValue;
+ if (minOccurs != 1 || maxOccurs != 1) {
+ if (group.fParticleCount == 1) {
+ XSParticleDecl particle2 = (XSParticleDecl) group.fParticles[0];
+ short type2 = particle2.fType;
+ return ((type2 == XSParticleDecl.PARTICLE_ELEMENT ||
+ type2 == XSParticleDecl.PARTICLE_WILDCARD) &&
+ particle2.fMinOccurs == 1 &&
+ particle2.fMaxOccurs == 1);
+ }
+ return (group.fParticleCount == 0);
+ }
+ for (int i = 0; i < group.fParticleCount; ++i) {
+ if (!useRepeatingLeafNodes(group.fParticles[i])) {
+ return false;
+ }
+ }
+ }
+ return true;
}
}
Modified: xerces/java/trunk/src/org/apache/xerces/impl/xs/models/CMNodeFactory.java
URL: http://svn.apache.org/viewvc/xerces/java/trunk/src/org/apache/xerces/impl/xs/models/CMNodeFactory.java?view=diff&rev=511014&r1=511013&r2=511014
==============================================================================
--- xerces/java/trunk/src/org/apache/xerces/impl/xs/models/CMNodeFactory.java (original)
+++ xerces/java/trunk/src/org/apache/xerces/impl/xs/models/CMNodeFactory.java Fri Feb 23 08:53:57 2007
@@ -87,8 +87,14 @@
}//reset()
public CMNode getCMLeafNode(int type, Object leaf, int id, int position) {
- nodeCountCheck() ;
+ nodeCountCheck();
return new XSCMLeaf(type, leaf, id, position) ;
+ }
+
+ public CMNode getCMRepeatingLeafNode(int type, Object leaf,
+ int minOccurs, int maxOccurs, int id, int position) {
+ nodeCountCheck();
+ return new XSCMRepeatingLeaf(type, leaf, minOccurs, maxOccurs, id, position);
}
public CMNode getCMUniOpNode(int type, CMNode childNode) {
Added: xerces/java/trunk/src/org/apache/xerces/impl/xs/models/XSCMRepeatingLeaf.java
URL: http://svn.apache.org/viewvc/xerces/java/trunk/src/org/apache/xerces/impl/xs/models/XSCMRepeatingLeaf.java?view=auto&rev=511014
==============================================================================
--- xerces/java/trunk/src/org/apache/xerces/impl/xs/models/XSCMRepeatingLeaf.java (added)
+++ xerces/java/trunk/src/org/apache/xerces/impl/xs/models/XSCMRepeatingLeaf.java Fri Feb 23 08:53:57 2007
@@ -0,0 +1,47 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.xerces.impl.xs.models;
+
+/**
+ * A compound content model leaf node which carries occurence information.
+ *
+ * @xerces.internal
+ *
+ * @author Michael Glavassevich, IBM
+ * @version $Id: $
+ */
+public final class XSCMRepeatingLeaf extends XSCMLeaf {
+
+ private final int fMinOccurs;
+ private final int fMaxOccurs;
+
+ public XSCMRepeatingLeaf(int type, Object leaf,
+ int minOccurs, int maxOccurs, int id, int position) {
+ super(type, leaf, id, position);
+ fMinOccurs = minOccurs;
+ fMaxOccurs = maxOccurs;
+ }
+
+ final int getMinOccurs() {
+ return fMinOccurs;
+ }
+
+ final int getMaxOccurs() {
+ return fMaxOccurs;
+ }
+}
Modified: xerces/java/trunk/src/org/apache/xerces/impl/xs/models/XSDFACM.java
URL: http://svn.apache.org/viewvc/xerces/java/trunk/src/org/apache/xerces/impl/xs/models/XSDFACM.java?view=diff&rev=511014&r1=511013&r2=511014
==============================================================================
--- xerces/java/trunk/src/org/apache/xerces/impl/xs/models/XSDFACM.java (original)
+++ xerces/java/trunk/src/org/apache/xerces/impl/xs/models/XSDFACM.java Fri Feb 23 08:53:57 2007
@@ -22,6 +22,7 @@
import org.apache.xerces.impl.dtd.models.CMNode;
import org.apache.xerces.impl.dtd.models.CMStateSet;
+import org.apache.xerces.impl.xs.SchemaSymbols;
import org.apache.xerces.impl.xs.SubstitutionGroupHandler;
import org.apache.xerces.impl.xs.XMLSchemaException;
import org.apache.xerces.impl.xs.XSConstraints;
@@ -134,6 +135,28 @@
* positions in the second dimension of the transition table.
*/
private int fTransTable[][] = null;
+
+ /**
+ * Array containing occurence information for looping states
+ * which use counters to check minOccurs/maxOccurs.
+ */
+ private Occurence [] fCountingStates = null;
+ static final class Occurence {
+ final int minOccurs;
+ final int maxOccurs;
+ final int elemIndex;
+ public Occurence (XSCMRepeatingLeaf leaf, int elemIndex) {
+ minOccurs = leaf.getMinOccurs();
+ maxOccurs = leaf.getMaxOccurs();
+ this.elemIndex = elemIndex;
+ }
+ public String toString() {
+ return "minOccurs=" + minOccurs
+ + ";maxOccurs=" +
+ ((maxOccurs != SchemaSymbols.OCCURRENCE_UNBOUNDED)
+ ? Integer.toString(maxOccurs) : "unbounded");
+ }
+ }
/**
* The number of valid entries in the transition table, and in the other
@@ -249,7 +272,7 @@
}
}
else if (type == XSParticleDecl.PARTICLE_WILDCARD) {
- if(((XSWildcardDecl)fElemMap[elemIndex]).allowNamespace(curElem.uri)) {
+ if (((XSWildcardDecl)fElemMap[elemIndex]).allowNamespace(curElem.uri)) {
matchingDecl = fElemMap[elemIndex];
break;
}
@@ -263,6 +286,66 @@
state[0] = XSCMValidator.FIRST_ERROR;
return findMatchingDecl(curElem, subGroupHandler);
}
+
+ if (fCountingStates != null) {
+ Occurence o = fCountingStates[curState];
+ if (o != null) {
+ if (curState == nextState) {
+ if (++state[2] > o.maxOccurs &&
+ o.maxOccurs != SchemaSymbols.OCCURRENCE_UNBOUNDED) {
+ // It's likely that we looped too many times on the current state
+ // however it's possible that we actually matched another particle
+ // which allows the same name.
+ //
+ // Consider:
+ //
+ // <xs:sequence>
+ // <xs:element name="foo" type="xs:string" minOccurs="3" maxOccurs="3"/>
+ // <xs:element name="foo" type="xs:string" fixed="bar"/>
+ // </xs:sequence>
+ //
+ // and
+ //
+ // <xs:sequence>
+ // <xs:element name="foo" type="xs:string" minOccurs="3" maxOccurs="3"/>
+ // <xs:any namespace="##any" processContents="skip"/>
+ // </xs:sequence>
+ //
+ // In the DFA there will be two transitions from the current state which
+ // allow "foo". Note that this is not a UPA violation. The ambiguity of which
+ // transition to take is resolved by the current value of the counter. Since
+ // we've already seen enough instances of the first "foo" perhaps there is
+ // another element declaration or wildcard deeper in the element map which
+ // matches.
+ return findMatchingDecl(curElem, state, subGroupHandler, elemIndex);
+ }
+ }
+ else if (state[2] < o.minOccurs) {
+ // not enough loops on the current state.
+ state[1] = state[0];
+ state[0] = XSCMValidator.FIRST_ERROR;
+ return findMatchingDecl(curElem, subGroupHandler);
+ }
+ else {
+ // Exiting a counting state. If we're entering a new
+ // counting state, reset the counter.
+ o = fCountingStates[nextState];
+ if (o != null) {
+ state[2] = (elemIndex == o.elemIndex) ? 1 : 0;
+ }
+ }
+ }
+ else {
+ o = fCountingStates[nextState];
+ if (o != null) {
+ // Entering a new counting state. Reset the counter.
+ // If we've already seen one instance of the looping
+ // particle set the counter to 1, otherwise set it
+ // to 0.
+ state[2] = (elemIndex == o.elemIndex) ? 1 : 0;
+ }
+ }
+ }
state[0] = nextState;
return matchingDecl;
@@ -286,18 +369,73 @@
}
return null;
- }
+ } // findMatchingDecl(QName, SubstitutionGroupHandler): Object
+
+ Object findMatchingDecl(QName curElem, int[] state, SubstitutionGroupHandler subGroupHandler, int elemIndex) {
+
+ int curState = state[0];
+ int nextState = 0;
+ Object matchingDecl = null;
+
+ while (++elemIndex < fElemMapSize) {
+ nextState = fTransTable[curState][elemIndex];
+ if (nextState == -1)
+ continue;
+ int type = fElemMapType[elemIndex] ;
+ if (type == XSParticleDecl.PARTICLE_ELEMENT) {
+ matchingDecl = subGroupHandler.getMatchingElemDecl(curElem, (XSElementDecl)fElemMap[elemIndex]);
+ if (matchingDecl != null) {
+ break;
+ }
+ }
+ else if (type == XSParticleDecl.PARTICLE_WILDCARD) {
+ if (((XSWildcardDecl)fElemMap[elemIndex]).allowNamespace(curElem.uri)) {
+ matchingDecl = fElemMap[elemIndex];
+ break;
+ }
+ }
+ }
+
+ // if we still can't find a match, set the state to FIRST_ERROR and return null
+ if (elemIndex == fElemMapSize) {
+ state[1] = state[0];
+ state[0] = XSCMValidator.FIRST_ERROR;
+ return findMatchingDecl(curElem, subGroupHandler);
+ }
+
+ // if we found a match, set the next state and reset the
+ // counter if the next state is a counting state.
+ state[0] = nextState;
+ final Occurence o = fCountingStates[nextState];
+ if (o != null) {
+ state[2] = (elemIndex == o.elemIndex) ? 1 : 0;
+ }
+ return matchingDecl;
+ } // findMatchingDecl(QName, int[], SubstitutionGroupHandler, int): Object
// This method returns the start states of the content model.
public int[] startContentModel() {
- int[] val = new int[2];
- val[0] = 0;
- return val;
+ // [0] : the current state
+ // [1] : if [0] is an error state then the
+ // last valid state before the error
+ // [2] : occurence counter for counting states
+ return new int [3];
} // startContentModel():int[]
// this method returns whether the last state was a valid final state
public boolean endContentModel(int[] state) {
- return fFinalStateFlags[state[0]];
+ final int curState = state[0];
+ if (fFinalStateFlags[curState]) {
+ if (fCountingStates != null) {
+ Occurence o = fCountingStates[curState];
+ if (o != null && state[2] < o.minOccurs) {
+ // not enough loops on the current state to be considered final.
+ return false;
+ }
+ }
+ return true;
+ }
+ return false;
} // endContentModel(int[]): boolean
// Killed off whatCanGoHere; we may need it for DOM canInsert(...) etc.,
@@ -413,6 +551,7 @@
fElemMapType = new int[fLeafCount];
fElemMapId = new int[fLeafCount];
fElemMapSize = 0;
+ Occurence [] elemOccurenceMap = null;
for (int outIndex = 0; outIndex < fLeafCount; outIndex++) {
// optimization from Henry Zongaro:
//fElemMap[outIndex] = new Object ();
@@ -427,7 +566,14 @@
// If it was not in the list, then add it, if not the EOC node
if (inIndex == fElemMapSize) {
- fElemMap[fElemMapSize] = fLeafList[outIndex].getLeaf();
+ XSCMLeaf leaf = fLeafList[outIndex];
+ fElemMap[fElemMapSize] = leaf.getLeaf();
+ if (leaf instanceof XSCMRepeatingLeaf) {
+ if (elemOccurenceMap == null) {
+ elemOccurenceMap = new Occurence[fLeafCount];
+ }
+ elemOccurenceMap[fElemMapSize] = new Occurence((XSCMRepeatingLeaf) leaf, fElemMapSize);
+ }
fElemMapType[fElemMapSize] = fLeafListType[outIndex];
fElemMapId[fElemMapSize] = id;
fElemMapSize++;
@@ -642,6 +788,23 @@
}
}
}
+
+ //
+ // Fill in the occurence information for each looping state
+ // if we're using counters.
+ //
+ if (elemOccurenceMap != null) {
+ fCountingStates = new Occurence[curState];
+ for (int i = 0; i < curState; ++i) {
+ int [] transitions = fTransTable[i];
+ for (int j = 0; j < transitions.length; ++j) {
+ if (i == transitions[j]) {
+ fCountingStates[i] = elemOccurenceMap[j];
+ break;
+ }
+ }
+ }
+ }
//
// And now we can say bye bye to the temp representation since we've
@@ -880,10 +1043,26 @@
if (fTransTable[i][j] != -1 &&
fTransTable[i][k] != -1) {
if (conflictTable[j][k] == 0) {
- conflictTable[j][k] = XSConstraints.overlapUPA
- (fElemMap[j],fElemMap[k],
- subGroupHandler) ?
- (byte)1 : (byte)-1;
+ if (XSConstraints.overlapUPA
+ (fElemMap[j], fElemMap[k],
+ subGroupHandler)) {
+ if (fCountingStates != null) {
+ Occurence o = fCountingStates[i];
+ // If "i" is a counting state and exactly one of the transitions
+ // loops back to "i" then the two particles do not overlap if
+ // minOccurs == maxOccurs.
+ if (o != null &&
+ fTransTable[i][j] == i ^ fTransTable[i][k] == i &&
+ o.minOccurs == o.maxOccurs) {
+ conflictTable[j][k] = (byte) -1;
+ continue;
+ }
+ }
+ conflictTable[j][k] = (byte) 1;
+ }
+ else {
+ conflictTable[j][k] = (byte) -1;
+ }
}
}
}
@@ -931,11 +1110,32 @@
int curState = state[0];
if (curState < 0)
curState = state[1];
+ Occurence o = (fCountingStates != null) ?
+ fCountingStates[curState] : null;
+ int count = state[2];
Vector ret = new Vector();
for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {
- if (fTransTable[curState][elemIndex] != -1)
+ int nextState = fTransTable[curState][elemIndex];
+ if (nextState != -1) {
+ if (o != null) {
+ if (curState == nextState) {
+ // Do not include transitions which loop back to the
+ // current state if we've looped the maximum number
+ // of times or greater.
+ if (count >= o.maxOccurs &&
+ o.maxOccurs != SchemaSymbols.OCCURRENCE_UNBOUNDED) {
+ continue;
+ }
+ }
+ // Do not include transitions which advance past the
+ // current state if we have not looped enough times.
+ else if (count < o.minOccurs) {
+ continue;
+ }
+ }
ret.addElement(fElemMap[elemIndex]);
+ }
}
return ret;
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@xerces.apache.org
For additional commands, e-mail: commits-help@xerces.apache.org