This is an automated email from the ASF dual-hosted git repository.
coheigea pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/ws-xmlschema.git
The following commit(s) were added to refs/heads/master by this push:
new 4d5e2049 Fix state machine generation for shared schema types (#126)
4d5e2049 is described below
commit 4d5e20490c71c4d5d3b3ec84dab51ca1ee01a2b9
Author: Colm O hEigeartaigh <[email protected]>
AuthorDate: Mon Aug 24 11:21:20 2026 +0100
Fix state machine generation for shared schema types (#126)
---
.../docpath/XmlSchemaStateMachineGenerator.java | 186 ++++++++++++--
.../schema/docpath/TestStateMachineSharedType.java | 280 +++++++++++++++++++++
2 files changed, 451 insertions(+), 15 deletions(-)
diff --git
a/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaStateMachineGenerator.java
b/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaStateMachineGenerator.java
index c8db32bc..6ab63dfb 100644
---
a/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaStateMachineGenerator.java
+++
b/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaStateMachineGenerator.java
@@ -21,6 +21,7 @@ package org.apache.ws.commons.schema.docpath;
import java.util.ArrayList;
import java.util.HashMap;
+import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
@@ -46,6 +47,27 @@ public final class XmlSchemaStateMachineGenerator implements
XmlSchemaVisitor {
private XmlSchemaStateMachineNode startNode;
private Map<QName, ElementInfo> elementInfoByQName;
+ /*
+ * The walker signals "previously visited" by type identity
+ * (XmlSchemaWalker.visitedTypes is reference-keyed), so keep a
+ * type-identity index alongside the QName index: two differently-named
+ * elements may legally share one named complex type, and two same-named
+ * local declarations may have different types. XmlSchemaTypeInfo
+ * identity is stable for named types because the walker caches one
+ * XmlSchemaScope per named type and XmlSchemaScope.getTypeInfo() returns
+ * a stored field.
+ */
+ private Map<XmlSchemaTypeInfo, ElementInfo> elementInfoByType;
+
+ /*
+ * Nodes whose possibleNextStates must be copied from a source node whose
+ * element is still on the stack -- i.e. whose children are still being
+ * walked because the type is recursive. The copy is deferred until the
+ * source node's element finally exits, at which point its content model
+ * is complete.
+ */
+ private Map<XmlSchemaStateMachineNode, List<XmlSchemaStateMachineNode>>
pendingNextStateCopies;
+
private static class ElementInfo {
final List<XmlSchemaAttrInfo> attributes;
final XmlSchemaTypeInfo typeInfo;
@@ -73,6 +95,9 @@ public final class XmlSchemaStateMachineGenerator implements
XmlSchemaVisitor {
public XmlSchemaStateMachineGenerator() {
stack = new ArrayList<XmlSchemaStateMachineNode>();
elementInfoByQName = new HashMap<QName, ElementInfo>();
+ elementInfoByType = new IdentityHashMap<XmlSchemaTypeInfo,
ElementInfo>();
+ pendingNextStateCopies =
+ new IdentityHashMap<XmlSchemaStateMachineNode,
List<XmlSchemaStateMachineNode>>();
startNode = null;
}
@@ -120,17 +145,57 @@ public final class XmlSchemaStateMachineGenerator
implements XmlSchemaVisitor {
* onEndAttributes() is called, so we can create an ElementInfo
* entry for it, and wait until later to create the state machine
* and add it to the stack.
+ *
+ * The QName entry is deliberately an overwrite: the in-flight
+ * element must stay reachable by QName from onVisitAttribute()
+ * and onEndAttributes(), even if a different declaration with
+ * the same QName was walked earlier. The previously-visited
+ * branch below therefore never trusts a QName hit alone -- it
+ * resolves by type identity first and validates any QName hit
+ * against the element's schema type.
*/
final ElementInfo info = new ElementInfo(element, typeInfo);
elementInfoByQName.put(element.getQName(), info);
+ if (!elementInfoByType.containsKey(typeInfo)) {
+ elementInfoByType.put(typeInfo, info);
+ }
} else {
/*
- * We have previously encountered this element, which means we have
- * already collected all of the information we needed to build an
- * XmlSchemaStateMachineNode. Likewise, we can just reference it.
+ * We have previously encountered this element's type (the walker
+ * tracks visits by type identity, not element QName), which
+ * means we have already collected all of the information we
+ * needed to build an XmlSchemaStateMachineNode for that type.
+ *
+ * Resolve the prior bookkeeping by type identity first. The
+ * QName index alone is unreliable here: a differently-named
+ * element may share a previously-visited named type (and have no
+ * QName entry of its own), and two distinct same-QName
+ * declarations overwrite each other's QName entries.
*/
- final ElementInfo elemInfo =
elementInfoByQName.get(element.getQName());
+ ElementInfo elemInfo = elementInfoByType.get(typeInfo);
+
+ boolean sharedFromSibling = false;
+ if ((elemInfo != null) && (elemInfo.stateMachineNode != null)) {
+ sharedFromSibling =
!element.getQName().equals(elemInfo.element.getQName());
+ } else {
+ /*
+ * No type-identity entry: for anonymous types the walker
+ * builds a fresh XmlSchemaTypeInfo on every encounter (only
+ * named types' scopes are cached), so the identity lookup
+ * cannot match. Fall back to the QName index, but validate
+ * the hit against the element's schema type -- reference
+ * equality on the XmlSchemaType is exactly how the walker
+ * decided previouslyVisited -- so two distinct same-QName
+ * declarations can never cross-bind.
+ */
+ final ElementInfo byQName =
elementInfoByQName.get(element.getQName());
+ if ((byQName != null) && (byQName.stateMachineNode != null)
+ && isSameSchemaType(byQName.element, element)) {
+ elemInfo = byQName;
+ }
+ }
+
if ((elemInfo == null) || (elemInfo.stateMachineNode == null)) {
throw new IllegalStateException("Element " + element.getQName()
+ " was already visited, but
we do not"
@@ -142,17 +207,47 @@ public final class XmlSchemaStateMachineGenerator
implements XmlSchemaVisitor {
+ " parent state machine node
to attach it to!");
}
- XmlSchemaStateMachineNode stateMachineNode =
elemInfo.stateMachineNode;
-
- /*
- * If this element is identical in every way except for the minimum
- * and maximum number of occurrences, we want to create a new state
- * machine node to represent this element.
- */
- if ((stateMachineNode.getMinOccurs() != element.getMinOccurs())
- || (stateMachineNode.getMaxOccurs() !=
element.getMaxOccurs())) {
- stateMachineNode = new XmlSchemaStateMachineNode(element,
elemInfo.attributes,
-
elemInfo.typeInfo);
+ XmlSchemaStateMachineNode stateMachineNode;
+
+ if (sharedFromSibling) {
+ /*
+ * A differently-named element sharing a previously-visited
+ * named type: build this element its own state machine node
+ * from the type-sharing sibling instead of failing on a
+ * legal schema shape. The walker will not re-walk this
+ * element's children (they were walked on the type's first
+ * visit), so the sibling node's possibleNextStates must be
+ * copied over as well -- otherwise this node would carry an
+ * empty content model and legal documents would fail
+ * downstream in XmlSchemaPathFinder.
+ */
+ final ElementInfo newInfo = new ElementInfo(element, typeInfo);
+ newInfo.attributes.addAll(elemInfo.attributes);
+ newInfo.stateMachineNode =
+ new XmlSchemaStateMachineNode(element, newInfo.attributes,
typeInfo);
+ copyPossibleNextStates(elemInfo.stateMachineNode,
newInfo.stateMachineNode);
+ if (!elementInfoByQName.containsKey(element.getQName())) {
+ elementInfoByQName.put(element.getQName(), newInfo);
+ }
+ stateMachineNode = newInfo.stateMachineNode;
+
+ } else {
+ stateMachineNode = elemInfo.stateMachineNode;
+
+ /*
+ * If this element is identical in every way except for the
+ * minimum and maximum number of occurrences, we want to
+ * create a new state machine node to represent this element.
+ * The new node needs the original's possibleNextStates as
+ * well, for the same reason as above: the walker skips the
+ * children of a previously-visited type.
+ */
+ if ((stateMachineNode.getMinOccurs() != element.getMinOccurs())
+ || (stateMachineNode.getMaxOccurs() !=
element.getMaxOccurs())) {
+ stateMachineNode = new XmlSchemaStateMachineNode(element,
elemInfo.attributes,
+
elemInfo.typeInfo);
+ copyPossibleNextStates(elemInfo.stateMachineNode,
stateMachineNode);
+ }
}
stack.get(stack.size() - 1).addPossibleNextState(stateMachineNode);
@@ -182,6 +277,21 @@ public final class XmlSchemaStateMachineGenerator
implements XmlSchemaVisitor {
+ " is not the same in-memory copy
we received on creation. Our"
+ " copy is of a " +
node.getElement().getQName());
}
+
+ /*
+ * If any nodes are waiting on this node's possibleNextStates (a
+ * recursive type was re-entered while this node's children were
+ * still being walked), and this node no longer appears anywhere on
+ * the stack, its content model is complete: perform the deferred
+ * copies now.
+ */
+ final List<XmlSchemaStateMachineNode> waiting =
pendingNextStateCopies.get(node);
+ if ((waiting != null) && !isOnStack(node)) {
+ pendingNextStateCopies.remove(node);
+ for (XmlSchemaStateMachineNode waiter : waiting) {
+ waiter.addPossibleNextStates(node.getPossibleNextStates());
+ }
+ }
}
/**
@@ -328,6 +438,52 @@ public final class XmlSchemaStateMachineGenerator
implements XmlSchemaVisitor {
// Ignored.
}
+ /*
+ * XmlSchemaStateMachineNode.addPossibleNextStates() copies the elements
+ * of the collection (Collection.addAll), not the list reference, so a
+ * copy taken while the source's children are still being walked (a
+ * recursive type) could be an incomplete snapshot. Copy immediately when
+ * the source's element is no longer being walked; otherwise defer the
+ * copy until the source's element exits (see onExitElement()).
+ */
+ private void copyPossibleNextStates(XmlSchemaStateMachineNode source,
+ XmlSchemaStateMachineNode target) {
+ if (isOnStack(source)) {
+ List<XmlSchemaStateMachineNode> waiting =
pendingNextStateCopies.get(source);
+ if (waiting == null) {
+ waiting = new ArrayList<XmlSchemaStateMachineNode>();
+ pendingNextStateCopies.put(source, waiting);
+ }
+ waiting.add(target);
+ } else {
+ target.addPossibleNextStates(source.getPossibleNextStates());
+ }
+ }
+
+ private boolean isOnStack(XmlSchemaStateMachineNode node) {
+ for (int index = stack.size() - 1; index >= 0; --index) {
+ if (stack.get(index) == node) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /*
+ * Reference equality on the schema type mirrors the walker's own
+ * previously-visited bookkeeping (XmlSchemaWalker.visitedTypes is
+ * keyed on the XmlSchemaType instance). When neither element carries a
+ * resolved schema type, fall back to the type's QName, which is unique
+ * per namespace for named types.
+ */
+ private static boolean isSameSchemaType(XmlSchemaElement known,
XmlSchemaElement current) {
+ if ((known.getSchemaType() != null) || (current.getSchemaType() !=
null)) {
+ return known.getSchemaType() == current.getSchemaType();
+ }
+ return (known.getSchemaTypeName() != null)
+ &&
known.getSchemaTypeName().equals(current.getSchemaTypeName());
+ }
+
private void pushGroup(XmlSchemaStateMachineNode.Type groupType, long
minOccurs, long maxOccurs) {
if (stack.isEmpty()) {
diff --git
a/xmlschema-walker/src/test/java/org/apache/ws/commons/schema/docpath/TestStateMachineSharedType.java
b/xmlschema-walker/src/test/java/org/apache/ws/commons/schema/docpath/TestStateMachineSharedType.java
new file mode 100644
index 00000000..df80fec5
--- /dev/null
+++
b/xmlschema-walker/src/test/java/org/apache/ws/commons/schema/docpath/TestStateMachineSharedType.java
@@ -0,0 +1,280 @@
+/**
+ * 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.ws.commons.schema.docpath;
+
+import java.io.StringReader;
+import java.util.IdentityHashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+
+import javax.xml.namespace.QName;
+
+import org.apache.ws.commons.schema.XmlSchemaCollection;
+import org.apache.ws.commons.schema.XmlSchemaElement;
+import org.apache.ws.commons.schema.walker.XmlSchemaWalker;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * The walker reports "previously visited" by type identity while the state
+ * machine generator historically kept its books by element QName. These
+ * tests cover the legal schema shapes where the two disagree.
+ */
+public class TestStateMachineSharedType extends Assert {
+
+ private static final String SHARED_TYPE_SCHEMA =
+ "<xs:schema xmlns:xs=\"http://www.w3.org/2001/XMLSchema\"";
+ + " xmlns:tns=\"urn:shared\" targetNamespace=\"urn:shared\">"
+ + "<xs:complexType name=\"T\"><xs:sequence>"
+ + "<xs:element name=\"leaf\" type=\"xs:string\"/>"
+ + "</xs:sequence></xs:complexType>"
+ + "<xs:element name=\"root\"><xs:complexType><xs:sequence>"
+ + "<xs:element name=\"a\" type=\"tns:T\"/>"
+ + "<xs:element name=\"b\" type=\"tns:T\"/>"
+ + "</xs:sequence></xs:complexType></xs:element>"
+ + "</xs:schema>";
+
+ /*
+ * Two same-QName local declarations (dup) with different named types,
+ * in different scopes (legal: the Element Declarations Consistent
+ * constraint applies per content model). The third wrapper revisits
+ * type A *after* the second declaration overwrote dup's QName entry.
+ */
+ private static final String SAME_QNAME_SCHEMA =
+ "<xs:schema xmlns:xs=\"http://www.w3.org/2001/XMLSchema\"";
+ + " xmlns:tns=\"urn:dup\" targetNamespace=\"urn:dup\">"
+ + "<xs:complexType name=\"A\"><xs:sequence>"
+ + "<xs:element name=\"x\" type=\"xs:string\"/>"
+ + "</xs:sequence></xs:complexType>"
+ + "<xs:complexType name=\"B\"><xs:sequence>"
+ + "<xs:element name=\"y\" type=\"xs:string\"/>"
+ + "</xs:sequence></xs:complexType>"
+ + "<xs:element name=\"root\"><xs:complexType><xs:sequence>"
+ + "<xs:element name=\"w1\"><xs:complexType><xs:sequence>"
+ + "<xs:element name=\"dup\" type=\"tns:A\"/>"
+ + "</xs:sequence></xs:complexType></xs:element>"
+ + "<xs:element name=\"w2\"><xs:complexType><xs:sequence>"
+ + "<xs:element name=\"dup\" type=\"tns:B\"/>"
+ + "</xs:sequence></xs:complexType></xs:element>"
+ + "<xs:element name=\"w3\"><xs:complexType><xs:sequence>"
+ + "<xs:element name=\"dup\" type=\"tns:A\"/>"
+ + "</xs:sequence></xs:complexType></xs:element>"
+ + "</xs:sequence></xs:complexType></xs:element>"
+ + "</xs:schema>";
+
+ /*
+ * A global element with an anonymous type, referenced twice. The walker
+ * hands the generator a fresh element copy and a fresh XmlSchemaTypeInfo
+ * on the second reference, so this shape exercises the validated-QName
+ * fast path (schema-type reference equality).
+ */
+ private static final String REFERENCED_ANONYMOUS_SCHEMA =
+ "<xs:schema xmlns:xs=\"http://www.w3.org/2001/XMLSchema\"";
+ + " xmlns:tns=\"urn:refanon\" targetNamespace=\"urn:refanon\">"
+ + "<xs:element name=\"e\"><xs:complexType><xs:sequence>"
+ + "<xs:element name=\"inner\" type=\"xs:string\"/>"
+ + "</xs:sequence></xs:complexType></xs:element>"
+ + "<xs:element name=\"root\"><xs:complexType><xs:sequence>"
+ + "<xs:element ref=\"tns:e\"/>"
+ + "<xs:element ref=\"tns:e\"/>"
+ + "</xs:sequence></xs:complexType></xs:element>"
+ + "</xs:schema>";
+
+ /*
+ * A recursive named type re-entered under a different element QName
+ * while its own children are still being walked: the transition copy
+ * must be deferred until the first-visit node's content model is
+ * complete.
+ */
+ private static final String RECURSIVE_SHARED_SCHEMA =
+ "<xs:schema xmlns:xs=\"http://www.w3.org/2001/XMLSchema\"";
+ + " xmlns:tns=\"urn:recur\" targetNamespace=\"urn:recur\">"
+ + "<xs:complexType name=\"R\"><xs:sequence>"
+ + "<xs:element name=\"mid\" type=\"xs:string\"/>"
+ + "<xs:element name=\"next\" type=\"tns:R\" minOccurs=\"0\"/>"
+ + "</xs:sequence></xs:complexType>"
+ + "<xs:element name=\"root\"><xs:complexType><xs:sequence>"
+ + "<xs:element name=\"first\" type=\"tns:R\"/>"
+ + "</xs:sequence></xs:complexType></xs:element>"
+ + "</xs:schema>";
+
+ @Test
+ public void testTwoElementsSharingOneNamedComplexType() {
+ final XmlSchemaStateMachineGenerator generator =
+ walk(SHARED_TYPE_SCHEMA, new QName("urn:shared", "root"));
+
+ assertNotNull(generator.getStartNode());
+
+ final Map<QName, XmlSchemaStateMachineNode> nodes =
generator.getStateMachineNodesByQName();
+ final XmlSchemaStateMachineNode nodeA = nodes.get(new
QName("urn:shared", "a"));
+ final XmlSchemaStateMachineNode nodeB = nodes.get(new
QName("urn:shared", "b"));
+ assertNotNull(nodeA);
+ assertNotNull(nodeB);
+
+ /*
+ * The legal document <root><a><leaf/></a><b><leaf/></b></root> must
+ * be navigable: the walker skips b's children as previously visited,
+ * so b's node only has a content model if the transitions were
+ * copied from a's node. Non-null alone is not enough -- b's
+ * possibleNextStates must match a's.
+ */
+ final List<XmlSchemaStateMachineNode> aNext =
nodeA.getPossibleNextStates();
+ final List<XmlSchemaStateMachineNode> bNext =
nodeB.getPossibleNextStates();
+ assertFalse("a's node should have a content model", aNext.isEmpty());
+ assertEquals("b's node must carry the shared type's content model",
aNext.size(),
+ bNext.size());
+ for (int i = 0; i < aNext.size(); ++i) {
+ assertEquals(aNext.get(i).getNodeType(),
bNext.get(i).getNodeType());
+ if
(XmlSchemaStateMachineNode.Type.ELEMENT.equals(aNext.get(i).getNodeType())) {
+ assertEquals(aNext.get(i).getElement().getQName(),
+ bNext.get(i).getElement().getQName());
+ }
+ }
+
+ final QName leaf = new QName("urn:shared", "leaf");
+ assertNotNull(findElement(nodeA, leaf));
+ assertNotNull("leaf must be reachable through b's content model",
findElement(nodeB, leaf));
+ }
+
+ @Test
+ public void testSameQNameDistinctDeclarationsDoNotCrossBind() {
+ final XmlSchemaStateMachineGenerator generator =
+ walk(SAME_QNAME_SCHEMA, new QName("urn:dup", "root"));
+
+ final XmlSchemaStateMachineNode start = generator.getStartNode();
+ assertNotNull(start);
+
+ final QName dup = new QName("urn:dup", "dup");
+ final QName x = new QName("urn:dup", "x");
+ final QName y = new QName("urn:dup", "y");
+
+ final XmlSchemaStateMachineNode w2 = findElement(start, new
QName("urn:dup", "w2"));
+ final XmlSchemaStateMachineNode w3 = findElement(start, new
QName("urn:dup", "w3"));
+ assertNotNull(w2);
+ assertNotNull(w3);
+
+ // w2/dup is declared with type B: it leads to <y/>, never <x/>.
+ final XmlSchemaStateMachineNode dupUnderW2 = findElement(w2, dup);
+ assertNotNull(dupUnderW2);
+ assertNotNull(findElement(dupUnderW2, y));
+ assertNull(findElement(dupUnderW2, x));
+
+ /*
+ * w3/dup is declared with type A. Resolving the revisit through the
+ * (overwritten) QName entry would silently bind it to type B's state
+ * machine; it must lead to <x/>, never <y/>.
+ */
+ final XmlSchemaStateMachineNode dupUnderW3 = findElement(w3, dup);
+ assertNotNull(dupUnderW3);
+ assertNotNull("w3/dup must carry type A's content model",
findElement(dupUnderW3, x));
+ assertNull("w3/dup must not cross-bind to type B",
findElement(dupUnderW3, y));
+ }
+
+ @Test
+ public void testElementWithAnonymousTypeReferencedTwice() {
+ final XmlSchemaStateMachineGenerator generator =
+ walk(REFERENCED_ANONYMOUS_SCHEMA, new QName("urn:refanon",
"root"));
+
+ final XmlSchemaStateMachineNode start = generator.getStartNode();
+ assertNotNull(start);
+
+ final XmlSchemaStateMachineNode nodeE = findElement(start, new
QName("urn:refanon", "e"));
+ assertNotNull(nodeE);
+ assertFalse(nodeE.getPossibleNextStates().isEmpty());
+ assertNotNull(findElement(nodeE, new QName("urn:refanon", "inner")));
+ }
+
+ @Test
+ public void testRecursiveTypeSharedUnderDifferentName() {
+ final XmlSchemaStateMachineGenerator generator =
+ walk(RECURSIVE_SHARED_SCHEMA, new QName("urn:recur", "root"));
+
+ assertNotNull(generator.getStartNode());
+
+ final Map<QName, XmlSchemaStateMachineNode> nodes =
generator.getStateMachineNodesByQName();
+ final XmlSchemaStateMachineNode nodeFirst = nodes.get(new
QName("urn:recur", "first"));
+ final XmlSchemaStateMachineNode nodeNext = nodes.get(new
QName("urn:recur", "next"));
+ assertNotNull(nodeFirst);
+ assertNotNull(nodeNext);
+
+ /*
+ * "next" re-entered type R while "first" was still being walked; the
+ * deferred copy must still deliver the complete content model.
+ */
+ assertFalse(nodeFirst.getPossibleNextStates().isEmpty());
+ assertEquals(nodeFirst.getPossibleNextStates().size(),
+ nodeNext.getPossibleNextStates().size());
+
+ final QName mid = new QName("urn:recur", "mid");
+ final QName next = new QName("urn:recur", "next");
+ assertNotNull(findElement(nodeNext, mid));
+ assertNotNull(findElement(nodeNext, next));
+ }
+
+ private static XmlSchemaStateMachineGenerator walk(String schema, QName
rootQName) {
+ final XmlSchemaCollection collection = new XmlSchemaCollection();
+ collection.read(new StringReader(schema));
+
+ final XmlSchemaElement root = collection.getElementByQName(rootQName);
+ assertNotNull(root);
+
+ final XmlSchemaStateMachineGenerator generator = new
XmlSchemaStateMachineGenerator();
+ final XmlSchemaWalker walker = new XmlSchemaWalker(collection,
generator);
+
+ // Throws IllegalStateException without the type-identity handling.
+ walker.walk(root);
+
+ return generator;
+ }
+
+ /**
+ * Breadth-first search of a node's content model for an element with the
+ * given QName. Does not descend through nested elements (an element
+ * boundary starts a nested content model) and is cycle-safe for
+ * recursive types.
+ */
+ private static XmlSchemaStateMachineNode
findElement(XmlSchemaStateMachineNode start,
+ QName qName) {
+ final Map<XmlSchemaStateMachineNode, Boolean> visited =
+ new IdentityHashMap<XmlSchemaStateMachineNode, Boolean>();
+ final LinkedList<XmlSchemaStateMachineNode> queue =
+ new
LinkedList<XmlSchemaStateMachineNode>(start.getPossibleNextStates());
+
+ while (!queue.isEmpty()) {
+ final XmlSchemaStateMachineNode node = queue.removeFirst();
+ if (visited.containsKey(node)) {
+ continue;
+ }
+ visited.put(node, Boolean.TRUE);
+
+ if
(XmlSchemaStateMachineNode.Type.ELEMENT.equals(node.getNodeType())) {
+ if (qName.equals(node.getElement().getQName())) {
+ return node;
+ }
+ } else {
+ queue.addAll(node.getPossibleNextStates());
+ }
+ }
+
+ return null;
+ }
+}
