This is an automated email from the ASF dual-hosted git repository. coheigea pushed a commit to branch coheigea/XmlSchemaStateMachineGenerator in repository https://gitbox.apache.org/repos/asf/ws-xmlschema.git
commit 1cb1f22cdc62f3a120253e895b7ae231721d7064 Author: Colm O hEigeartaigh <[email protected]> AuthorDate: Mon Aug 24 10:35:23 2026 +0100 Fix state machine generation for shared schema types --- .../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; + } +}
