You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ws.apache.org by dk...@apache.org on 2014/09/17 17:32:46 UTC
svn commit: r1625632 [2/9] - in /webservices/xmlschema/trunk: ./
xmlschema-walker/ xmlschema-walker/src/ xmlschema-walker/src/main/
xmlschema-walker/src/main/java/ xmlschema-walker/src/main/java/org/
xmlschema-walker/src/main/java/org/apache/ xmlschema...
Added: webservices/xmlschema/trunk/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaNamespaceContext.java
URL: http://svn.apache.org/viewvc/webservices/xmlschema/trunk/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaNamespaceContext.java?rev=1625632&view=auto
==============================================================================
--- webservices/xmlschema/trunk/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaNamespaceContext.java (added)
+++ webservices/xmlschema/trunk/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaNamespaceContext.java Wed Sep 17 15:32:44 2014
@@ -0,0 +1,207 @@
+/**
+ * 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.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.ws.commons.schema.constants.Constants;
+import org.apache.ws.commons.schema.utils.NamespacePrefixList;
+
+/**
+ * A {@link javax.xml.namespace.NamespaceContext}.
+ * <p>
+ * Implemented as a series of scope-based stacks, one per prefix.
+ * </p>
+ */
+public final class XmlSchemaNamespaceContext implements NamespacePrefixList {
+
+ private Map<String, List<String>> namespacesByPrefixStack;
+
+ /**
+ * Constructs a new <code>XmlSchemaNamespaceContext</code> with the
+ * following initial mappings:
+ * <ul>
+ * <li>
+ * <code>xml</code> -> <code>http://www.w3.org/1999/namespace</code></li>
+ * <li>
+ * <code>xmlns</code> -> <code>http://www.w3.org/2000/xmlns/</code></li>
+ * </ul>
+ */
+ public XmlSchemaNamespaceContext() {
+ namespacesByPrefixStack = new HashMap<String, List<String>>();
+
+ namespacesByPrefixStack.put(Constants.XML_NS_PREFIX, Collections.singletonList(Constants.XML_NS_URI));
+
+ namespacesByPrefixStack.put(Constants.XMLNS_ATTRIBUTE,
+ Collections.singletonList(Constants.XMLNS_ATTRIBUTE_NS_URI));
+ }
+
+ /**
+ * @see NamespacePrefixList#getNamespaceURI(String)
+ */
+ @Override
+ public String getNamespaceURI(String prefix) {
+ if (prefix == null) {
+ throw new IllegalArgumentException("Prefix cannot be null.");
+ }
+ final List<String> namespaces = namespacesByPrefixStack.get(prefix);
+
+ String namespace = null;
+ if ((namespaces == null) || namespaces.isEmpty()) {
+ namespace = Constants.NULL_NS_URI;
+ } else {
+ namespace = namespaces.get(namespaces.size() - 1);
+ }
+
+ return namespace;
+ }
+
+ /**
+ * @see NamespacePrefixList#getPrefix(String)
+ */
+ @Override
+ public String getPrefix(String namespaceUri) {
+ if (namespaceUri == null) {
+ throw new IllegalArgumentException("Namespace cannot be null.");
+ }
+
+ for (Map.Entry<String, List<String>> prefixEntry : namespacesByPrefixStack.entrySet()) {
+
+ final List<String> namespaceStack = prefixEntry.getValue();
+ if ((namespaceStack != null) && !namespaceStack.isEmpty()
+ && namespaceStack.get(namespaceStack.size() - 1).equals(namespaceUri)) {
+ return prefixEntry.getKey();
+ }
+ }
+
+ return null;
+ }
+
+ /**
+ * @see NamespacePrefixList#getPrefixes(String)
+ */
+ @SuppressWarnings("rawtypes")
+ @Override
+ public Iterator getPrefixes(String namespaceUri) {
+ if (namespaceUri == null) {
+ throw new IllegalArgumentException("The Namespace URI cannot be null.");
+ }
+
+ ArrayList<String> prefixes = new ArrayList<String>();
+
+ for (Map.Entry<String, List<String>> prefixEntry : namespacesByPrefixStack.entrySet()) {
+
+ final List<String> namespaceStack = prefixEntry.getValue();
+ if ((namespaceStack != null) && !namespaceStack.isEmpty()
+ && namespaceStack.get(namespaceStack.size() - 1).equals(namespaceUri)) {
+
+ prefixes.add(prefixEntry.getKey());
+ }
+ }
+
+ return prefixes.iterator();
+ }
+
+ /**
+ * @see NamespacePrefixList#getDeclaredPrefixes()
+ */
+ @Override
+ public String[] getDeclaredPrefixes() {
+ final Set<String> prefixes = namespacesByPrefixStack.keySet();
+ return prefixes.toArray(new String[prefixes.size()]);
+ }
+
+ /**
+ * Adds a new prefix mapping to the context. The prefix may be an empty
+ * string to represent the default namespace, but it cannot be null. The
+ * namespace URI can never be empty or null.
+ *
+ * @param prefix The prefix to represent the namespace URI.
+ * @param namespaceUri the namespace URI represented by the prefix.
+ * @throws IllegalArgumentException if the prefix is null, or if the
+ * namespace URI is null or empty.
+ */
+ public void addNamespace(String prefix, String namespaceUri) {
+ if ((prefix == null) || (namespaceUri == null) || (namespaceUri.length() == 0)) {
+
+ throw new IllegalArgumentException("The prefix may not be null, and the namespace URI "
+ + "may neither be null nor empty.");
+
+ } else if (isRecognizedPrefix(prefix)) {
+ // These are already mapped.
+ return;
+ }
+
+ List<String> namespaceStack = namespacesByPrefixStack.get(prefix);
+ if (namespaceStack == null) {
+ namespaceStack = new ArrayList<String>(1);
+ namespacesByPrefixStack.put(prefix, namespaceStack);
+ }
+ namespaceStack.add(namespaceUri);
+ }
+
+ /**
+ * Removes the most recent prefix-to-namespace mapping for the provided
+ * prefix. The prior prefix-to-namespace mapping before it is restored.
+ *
+ * @param prefix The prefix to remove the current prefix-to-namespace
+ * mapping of.
+ * @throws IllegalStateException If there is no current mapping for that
+ * prefix.
+ */
+ public void removeNamespace(String prefix) {
+ final List<String> namespaceStack = namespacesByPrefixStack.get(prefix);
+ if ((namespaceStack == null) || namespaceStack.isEmpty()) {
+ throw new IllegalStateException("Prefix \"" + prefix + "\" is not mapped to any namespaces.");
+
+ } else if (isRecognizedPrefix(prefix)) {
+ // These cannot be unmapped.
+ return;
+ }
+
+ namespaceStack.remove(namespaceStack.size() - 1);
+ if (namespaceStack.isEmpty()) {
+ namespacesByPrefixStack.remove(prefix);
+ }
+ }
+
+ /**
+ * Clears the given namespace stack, restoring it to the original mappings
+ * defined by the constructor.
+ */
+ public void clear() {
+ namespacesByPrefixStack.clear();
+
+ namespacesByPrefixStack.put(Constants.XML_NS_PREFIX, Collections.singletonList(Constants.XML_NS_URI));
+
+ namespacesByPrefixStack.put(Constants.XMLNS_ATTRIBUTE,
+ Collections.singletonList(Constants.XMLNS_ATTRIBUTE_NS_URI));
+ }
+
+ private static boolean isRecognizedPrefix(String prefix) {
+ return (Constants.XML_NS_PREFIX.equals(prefix) || Constants.XMLNS_ATTRIBUTE.equals(prefix));
+ }
+}
Propchange: webservices/xmlschema/trunk/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaNamespaceContext.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: webservices/xmlschema/trunk/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaPathFinder.java
URL: http://svn.apache.org/viewvc/webservices/xmlschema/trunk/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaPathFinder.java?rev=1625632&view=auto
==============================================================================
--- webservices/xmlschema/trunk/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaPathFinder.java (added)
+++ webservices/xmlschema/trunk/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaPathFinder.java Wed Sep 17 15:32:44 2014
@@ -0,0 +1,1706 @@
+/**
+ * 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.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+
+import javax.xml.bind.ValidationException;
+import javax.xml.namespace.QName;
+
+import org.apache.ws.commons.schema.XmlSchemaAny;
+import org.apache.ws.commons.schema.XmlSchemaElement;
+import org.apache.ws.commons.schema.walker.XmlSchemaTypeInfo;
+import org.xml.sax.Attributes;
+import org.xml.sax.SAXException;
+import org.xml.sax.helpers.DefaultHandler;
+
+/**
+ * Performs a SAX-based walk through the XML document, determining the
+ * interpretation ("path") that best matches the XML Schema.
+ * <p>
+ * This is a traditional {@link DefaultHandler} that can be attached to either a
+ * {@link javax.xml.parsers.SAXParser} during a parse, or to
+ * {@link SaxWalkerOverDom} to find paths through an
+ * {@link org.w3c.dom.Document}.
+ * </p>
+ * <p>
+ * Because this is a SAX-based walk, the source information need not be an XML
+ * document. It can be any data that can be interpreted via a SAX walk. This can
+ * be helpful when trying to confirm the source data can be converted back into
+ * XML.
+ * </p>
+ */
+public final class XmlSchemaPathFinder extends DefaultHandler {
+
+ /*
+ * If a group loops back on itself, we don't want to loop until the stack
+ * overflows looking for a valid match. We will stop looking once we reach
+ * MAX_DEPTH.
+ */
+ private static final int MAX_DEPTH = 256;
+
+ private final XmlSchemaNamespaceContext nsContext;
+
+ private XmlSchemaPathNode rootPathNode;
+
+ private XmlSchemaPathNode currentPath;
+
+ private ArrayList<TraversedElement> traversedElements;
+ private ArrayList<DecisionPoint> decisionPoints;
+
+ private ArrayList<QName> elementStack;
+ private ArrayList<QName> anyStack;
+
+ private XmlSchemaPathManager pathMgr;
+
+ /*
+ * We want to keep track of all of the valid path segments to a particular
+ * element, but we do not want to stomp on the very first node until we know
+ * which path we want to follow. Likewise, we want to keep the first node in
+ * the segment without a "next" node, but every node after that we wish to
+ * chain together. To accomplish this, we start with a base node at the end
+ * and "prepend" previous nodes until we work our way back to the beginning.
+ * When we prepend a node, we link the previous start node to the node
+ * directly after it, while leaving the new start node unlinked. Path
+ * segments may also be recycled when a decision point is refuted.
+ */
+ private final class PathSegment implements Comparable<PathSegment> {
+
+ private XmlSchemaPathNode start;
+ private XmlSchemaPathNode end;
+ private XmlSchemaPathNode afterStart;
+ private int length;
+ private int afterStartPathIndex;
+
+ PathSegment(XmlSchemaPathNode node) {
+ set(node);
+ }
+
+ @Override
+ public int compareTo(PathSegment o) {
+ if (this == o) {
+ return 0;
+ }
+
+ /*
+ * Paths which end in a wildcard element are of lower rank (higher
+ * order) than those that end in elements.
+ */
+ if (!end.getStateMachineNode().getNodeType()
+ .equals(o.getEnd().getStateMachineNode().getNodeType())) {
+
+ if (end.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ANY)) {
+ return 1;
+
+ } else if (o.getEnd().getStateMachineNode().getNodeType()
+ .equals(XmlSchemaStateMachineNode.Type.ANY)) {
+ return -1;
+
+ } else {
+ throw new IllegalStateException(
+ "The end nodes do not have the same machine node type, so one "
+ + "should be an ELEMENT and the other should be an ANY. "
+ + "However, this end node is a "
+ + end.getStateMachineNode().getNodeType()
+ + " while the other has an end node of type "
+ + o.getEnd().getStateMachineNode().getNodeType()
+ + ".");
+ }
+ }
+
+ final int thisLength = getLength();
+ final int thatLength = o.getLength();
+
+ /*
+ * Paths that walk through earlier sequence group children are
+ * preferred over paths that walk through later sequence group
+ * children. They provide more options later. Shorter paths are also
+ * preferred over longer ones.
+ */
+ if ((thisLength > 0) && (thatLength > 0)) {
+ // Both paths have more than just one element.
+ XmlSchemaPathNode thisIter = afterStart;
+ XmlSchemaPathNode thatIter = o.getAfterStart();
+
+ while ((thisIter != null) && (thatIter != null)) {
+ if (thisIter.getDirection().getRank() < thatIter.getDirection().getRank()) {
+ return -1;
+ } else if (thisIter.getDirection().getRank() > thatIter.getDirection().getRank()) {
+ return 1;
+ }
+
+ if (thisIter.getIndexOfNextNodeState() < thatIter.getIndexOfNextNodeState()) {
+
+ return -1;
+
+ } else if (thisIter.getIndexOfNextNodeState() > thatIter.getIndexOfNextNodeState()) {
+
+ return 1;
+ }
+
+ thisIter = thisIter.getNext();
+ thatIter = thatIter.getNext();
+ }
+
+ if ((thisIter == null) && (thatIter != null)) {
+ // This path is shorter.
+ return -1;
+ } else if ((thisIter != null) && (thatIter == null)) {
+ // That path is shorter.
+ return 1;
+ }
+
+ } else if ((thisLength == 0) && (thatLength > 0)) {
+ // This path is shorter.
+ return -1;
+
+ } else if ((thisLength > 0) && (thatLength == 0)) {
+ // That path is shorter.
+ return 1;
+
+ } else {
+ // Both paths have exactly one element.
+ if (end.getIndexOfNextNodeState() < o.getEnd().getIndexOfNextNodeState()) {
+
+ return -1;
+
+ } else if (end.getIndexOfNextNodeState() > o.getEnd().getIndexOfNextNodeState()) {
+
+ return 1;
+ }
+ }
+
+ /*
+ * If all of our different heuristics do not differentiate the
+ * paths, we will return equality. This is fine because
+ * Collections.sort(List<T>) is stable, and will preserve the
+ * ordering.
+ */
+ return 0;
+ }
+
+ int getLength() {
+ if ((length == 0) && (start != end)) {
+ for (XmlSchemaPathNode iter = afterStart; iter != end; iter = iter.getNext()) {
+ ++length;
+ }
+ ++length; // (afterStart -> end) + start
+ }
+ return length;
+ }
+
+ /*
+ * Prepends a new start node to this segment. We want to clone the
+ * previous start node as sibling paths may be sharing it. We also need
+ * to know the newStart's path index to reach the clonedStartNode, so we
+ * know how to properly link them later.
+ */
+ void prepend(XmlSchemaPathNode newStart, int pathIndexToNextNode) {
+ // We need to clone start and make it the afterStart.
+ final XmlSchemaPathNode clonedStartNode = pathMgr.clone(start);
+
+ if (afterStart != null) {
+ afterStart.setPreviousNode(clonedStartNode);
+ clonedStartNode.setNextNode(afterStartPathIndex, afterStart);
+ afterStart = clonedStartNode;
+
+ } else {
+ // This path segment only has one node in it; now it has two.
+ end = clonedStartNode;
+ afterStart = clonedStartNode;
+ }
+
+ start = newStart;
+ afterStartPathIndex = pathIndexToNextNode;
+ length = 0; // Force a recalculation.
+ }
+
+ XmlSchemaPathNode getStart() {
+ return start;
+ }
+
+ XmlSchemaPathNode getEnd() {
+ return end;
+ }
+
+ XmlSchemaPathNode getAfterStart() {
+ return afterStart;
+ }
+
+ int getAfterStartPathIndex() {
+ return afterStartPathIndex;
+ }
+
+ void set(XmlSchemaPathNode node) {
+ if (node == null) {
+ throw new IllegalArgumentException("DocumentPathNode cannot be null.");
+ }
+
+ this.start = node;
+ this.end = node;
+ this.afterStart = null;
+ this.afterStartPathIndex = -1;
+ this.length = 0;
+ }
+
+ @Override
+ public String toString() {
+ final StringBuilder str = new StringBuilder("Path Segment: [ ");
+
+ str.append(start.getDirection()).append(" | ");
+ str.append(start.getStateMachineNode()).append(" ]");
+
+ if (afterStart != null) {
+ XmlSchemaPathNode path = afterStart;
+
+ do {
+ str.append(" [").append(path.getDirection()).append(" | ");
+ str.append(path.getStateMachineNode()).append(" ]");
+
+ path = path.getNext();
+ } while (path != null);
+
+ } else {
+ str.append(" [").append(end.getDirection()).append(" | ");
+ str.append(end.getStateMachineNode()).append(" ]");
+ }
+
+ return str.toString();
+ }
+ }
+
+ /*
+ * A <code>DescisionPoint</code> is a location in a document path where an
+ * element in the document can be reached by following two or more different
+ * traversals through the XML Schema. When we reach such a decision point,
+ * we will keep track of the different paths through the XML Schema that
+ * reach the element. We will then follow each path, one-by-one from the
+ * shortest through the longest, until we find a path that successfully
+ * navigates both the document and the schema.
+ */
+ private static class DecisionPoint {
+
+ private final XmlSchemaPathNode decisionPoint;
+ private final List<PathSegment> choices;
+ private final int traversedElementIndex;
+ private final ArrayList<QName> elementStack;
+ private final ArrayList<QName> anyStack;
+
+ DecisionPoint(XmlSchemaPathNode decisionPoint, List<PathSegment> choices, int traversedElementIndex,
+ ArrayList<QName> elementStack, ArrayList<QName> anyStack) {
+
+ if (decisionPoint == null) {
+ throw new IllegalArgumentException("The decision point path node cannot be null.");
+ } else if (choices == null) {
+ throw new IllegalArgumentException("The set of choice paths to follow cannot be null.");
+ } else if (choices.size() < 2) {
+ throw new IllegalArgumentException(
+ "There must be at least two choices to constitute a decision point"
+ + ", not " + choices.size());
+ }
+
+ this.decisionPoint = decisionPoint;
+ this.choices = choices;
+ this.traversedElementIndex = traversedElementIndex;
+ this.elementStack = new ArrayList<QName>(elementStack);
+
+ if (anyStack == null) {
+ this.anyStack = null;
+ } else {
+ this.anyStack = new ArrayList<QName>(anyStack);
+ }
+
+ java.util.Collections.sort(choices);
+ }
+
+ /**
+ * Returns the next <code>PathSegment</code> to try, or
+ * <code>null</code> if all <code>PathSegment</code>s have been
+ * followed.
+ */
+ PathSegment tryNextPath() {
+ if (choices.isEmpty()) {
+ return null;
+ } else {
+ return choices.remove(0);
+ }
+ }
+
+ XmlSchemaPathNode getDecisionPoint() {
+ return decisionPoint;
+ }
+
+ ArrayList<QName> getElementStack() {
+ return new ArrayList<QName>(elementStack);
+ }
+
+ ArrayList<QName> getAnyStack() {
+ return (anyStack == null) ? null : ((ArrayList<QName>)anyStack.clone());
+ }
+
+ @Override
+ public String toString() {
+ final String nl = System.getProperty("line.separator");
+
+ final StringBuilder str = new StringBuilder("Decision Point: ");
+
+ str.append(decisionPoint.getDirection()).append(" | ");
+ str.append(decisionPoint.getStateMachineNode());
+ str.append(" ]").append(nl);
+
+ for (PathSegment choice : choices) {
+ str.append('\t').append(choice).append(nl);
+ }
+
+ return str.toString();
+ }
+ }
+
+ /*
+ * Represents an element-start, element-end, or content we have seen before.
+ * When walking our way through the XML Schema, we need this information in
+ * order to properly backtrack if we took a wrong path.
+ */
+ private static class TraversedElement {
+
+ QName elemName;
+ Traversal traversal;
+
+ enum Traversal {
+ START, CONTENT, END
+ }
+
+ TraversedElement(QName elemName, Traversal traversal) {
+ this.elemName = elemName;
+ this.traversal = traversal;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder str = new StringBuilder(elemName.toString());
+ str.append(" : ").append(traversal);
+ return str.toString();
+ }
+ }
+
+ /*
+ * Represents a group's fulfillment state. It is either not fulfilled,
+ * meaning more children are required, partially fulfilled, meaning at least
+ * the minimum number of children have been added, or completely fulfilled,
+ * meaning no more children can be introduced.
+ */
+ private enum Fulfillment {
+ NOT, PARTIAL, COMPLETE
+ }
+
+ /**
+ * Creates a new <code>XmlToAvroPathCreator</code> with the root
+ * {@link XmlSchemaStateMachineNode} to start from when evaluating
+ * documents.
+ */
+ public XmlSchemaPathFinder(XmlSchemaStateMachineNode root) {
+ pathMgr = new XmlSchemaPathManager();
+ nsContext = new XmlSchemaNamespaceContext();
+
+ rootPathNode = pathMgr.createStartPathNode(XmlSchemaPathNode.Direction.CHILD, root);
+ rootPathNode.setIteration(1);
+
+ traversedElements = new ArrayList<TraversedElement>();
+ elementStack = new ArrayList<QName>();
+ currentPath = null;
+ decisionPoints = null; // Hopefully there won't be any!
+ }
+
+ /**
+ * Kick-starts a new SAX walk, building new <code>XmlSchemaPathNode</code>
+ * and <code>XmlSchemaDocumentNode</code> traversals in the process.
+ *
+ * @see DefaultHandler#startDocument()
+ */
+ @Override
+ public void startDocument() throws SAXException {
+ currentPath = null;
+
+ traversedElements.clear();
+ elementStack.clear();
+
+ if (decisionPoints != null) {
+ decisionPoints.clear();
+ }
+ }
+
+ /**
+ * Handles a new prefix mapping in the SAX walk.
+ *
+ * @see DefaultHandler#startPrefixMapping(String, String)
+ */
+ @Override
+ public void startPrefixMapping(String prefix, String uri) throws SAXException {
+
+ nsContext.addNamespace(prefix, uri);
+ }
+
+ /**
+ * Handles the end of a prefix mapping in the SAX walk.
+ *
+ * @see DefaultHandler#endPrefixMapping(String)
+ */
+ @Override
+ public void endPrefixMapping(String prefix) throws SAXException {
+ nsContext.removeNamespace(prefix);
+ }
+
+ /**
+ * Find the path through the XML Schema that best matches this element,
+ * traversing any relevant groups, and backtracking if necessary.
+ *
+ * @see DefaultHandler#startElement(String, String, String, Attributes)
+ */
+ @Override
+ public void startElement(String uri, String localName, String qName, Attributes atts) throws SAXException {
+
+ final QName elemQName = new QName(uri, localName);
+
+ try {
+ if (currentPath == null) {
+ /*
+ * We just started a new document. Likewise we need to move into
+ * a position to process the root element.
+ */
+ currentPath = rootPathNode;
+
+ } else if (currentPath.getStateMachineNode().getNodeType()
+ .equals(XmlSchemaStateMachineNode.Type.ANY)
+ && (anyStack != null) && !anyStack.isEmpty()) {
+ /*
+ * If we are currently following a wildcard element node, we
+ * don't know anything about the element or its children. So it
+ * does not make sense to follow the children or grandchildren
+ * of this element.
+ */
+ elementStack.add(elemQName);
+ anyStack.add(elemQName);
+ return;
+ }
+
+ // 1. Find possible paths.
+ List<PathSegment> possiblePaths = find(currentPath, elemQName);
+
+ PathSegment nextPath = null;
+
+ if ((possiblePaths != null) && !possiblePaths.isEmpty()) {
+ /*
+ * 2. If multiple paths were returned, add a DecisionPoint. Sort
+ * the paths where paths ending in elements are favored over
+ * element wild cards, and shorter paths are favored over longer
+ * paths.
+ */
+ if (possiblePaths.size() > 1) {
+ final DecisionPoint decisionPoint = new DecisionPoint(currentPath, possiblePaths,
+ traversedElements.size(),
+ elementStack, anyStack);
+
+ if (decisionPoints == null) {
+ decisionPoints = new ArrayList<DecisionPoint>(4);
+ }
+ decisionPoints.add(decisionPoint);
+
+ nextPath = decisionPoint.tryNextPath();
+ } else {
+ nextPath = possiblePaths.get(0);
+ }
+
+ if (nextPath == null) {
+ throw new IllegalStateException("When searching for " + elemQName
+ + ", received a set of path choices of size "
+ + possiblePaths.size() + ", but the next path is null.");
+ }
+
+ followPath(nextPath);
+
+ } else {
+ // OR: If no paths are returned:
+ while ((decisionPoints != null) && !decisionPoints.isEmpty()) {
+ /*
+ * 2a. Backtrack to the most recent decision point. Remove
+ * the top path (the one we just tried), and select the next
+ * one.
+ */
+ final DecisionPoint priorPoint = decisionPoints.get(decisionPoints.size() - 1);
+
+ nextPath = priorPoint.tryNextPath();
+
+ if (nextPath == null) {
+ /*
+ * We have tried all paths at this decision point.
+ * Remove it and try the next prior decision point.
+ */
+ decisionPoints.remove(decisionPoints.size() - 1);
+ continue;
+ }
+
+ pathMgr.unfollowPath(priorPoint.getDecisionPoint());
+
+ elementStack = priorPoint.getElementStack();
+ anyStack = priorPoint.getAnyStack();
+
+ /*
+ * Walk through the traversedElements list again from that
+ * index and see if we traverse through all of the elements
+ * in the list, including this one. If not, repeat step 2a,
+ * removing decision points from the stack as we refute
+ * them.
+ */
+ followPath(nextPath);
+
+ final QName traversedQName = traversedElements.get(priorPoint.traversedElementIndex).elemName;
+
+ elementStack.add(traversedQName);
+
+ if (currentPath.getStateMachineNode().getNodeType()
+ .equals(XmlSchemaStateMachineNode.Type.ANY)) {
+ if (anyStack == null) {
+ anyStack = new ArrayList<QName>();
+ }
+ anyStack.add(traversedQName);
+ }
+
+ int index = priorPoint.traversedElementIndex + 1;
+ for (; index < traversedElements.size(); ++index) {
+ nextPath = null;
+
+ final TraversedElement te = traversedElements.get(index);
+
+ if (te.traversal.equals(TraversedElement.Traversal.START)) {
+ possiblePaths = find(currentPath, te.elemName);
+
+ if ((possiblePaths == null) || possiblePaths.isEmpty()) {
+ break;
+
+ } else if (possiblePaths.size() > 1) {
+ final DecisionPoint decisionPoint = new DecisionPoint(currentPath,
+ possiblePaths, index,
+ elementStack, anyStack);
+ decisionPoints.add(decisionPoint);
+ nextPath = decisionPoint.tryNextPath();
+
+ } else {
+ nextPath = possiblePaths.get(0);
+ }
+
+ if (nextPath == null) {
+ throw new IllegalStateException("Somehow after finding a new path to follow,"
+ + " that path is null.");
+ }
+
+ // If we find (a) path(s) that match(es), success!
+ // Follow it.
+ followPath(nextPath);
+
+ if (currentPath.getStateMachineNode().getNodeType()
+ .equals(XmlSchemaStateMachineNode.Type.ANY)) {
+ if (anyStack == null) {
+ anyStack = new ArrayList<QName>();
+ }
+ anyStack.add(te.elemName);
+ }
+
+ elementStack.add(te.elemName);
+
+ } else if (te.traversal.equals(TraversedElement.Traversal.END)) {
+ final boolean isAny = (currentPath.getStateMachineNode().getNodeType()
+ .equals(XmlSchemaStateMachineNode.Type.ANY)
+ && (anyStack != null) && !anyStack.isEmpty());
+
+ if (!isAny) {
+ walkUpToElement(te.elemName);
+ }
+
+ walkUpTree(te.elemName);
+
+ final QName endingElemName = elementStack.remove(elementStack.size() - 1);
+
+ if (!te.elemName.equals(endingElemName)) {
+ throw new IllegalStateException("Attempted to end element " + te.elemName
+ + " but found " + endingElemName
+ + " on the stack instead!");
+ }
+
+ if (isAny) {
+ anyStack.remove(anyStack.size() - 1);
+ }
+
+ } else if (te.traversal.equals(TraversedElement.Traversal.CONTENT)) {
+
+ final XmlSchemaPathNode contentPath = pathMgr
+ .addParentSiblingOrContentNodeToPath(currentPath,
+ XmlSchemaPathNode.Direction.CONTENT);
+
+ currentPath.setNextNode(-1, contentPath);
+ currentPath = contentPath;
+
+ } else {
+ throw new IllegalStateException("Unrecognized element traversal direction for "
+ + te.elemName + " of " + te.traversal + '.');
+ }
+ }
+
+ if (index < traversedElements.size()) {
+ /*
+ * This attempt is also incorrect. However, we may have
+ * introduced new decision points along the way, and we
+ * want to follow them first. So let's go back around
+ * for another try.
+ */
+ continue;
+ }
+
+ /*
+ * We made it to the end of the element list! Now try the
+ * current one again.
+ */
+ possiblePaths = find(currentPath, elemQName);
+
+ if (possiblePaths == null) {
+ // Still incorrect!
+ continue;
+
+ } else if (possiblePaths.size() > 1) {
+ final DecisionPoint decisionPoint = new DecisionPoint(currentPath, possiblePaths,
+ traversedElements.size(),
+ elementStack, anyStack);
+ decisionPoints.add(decisionPoint);
+ nextPath = decisionPoint.tryNextPath();
+ } else {
+ nextPath = possiblePaths.get(0);
+ }
+
+ if (nextPath != null) {
+ followPath(nextPath);
+ break;
+ }
+ }
+ }
+
+ if (nextPath == null) {
+ /*
+ * If we go through all prior decision points and are unable to
+ * find one or more paths through the XML Schema that match the
+ * document, throw an error. There is nothing more we can do
+ * here.
+ */
+ throw new IllegalStateException(
+ "Walked through XML Schema and could not find a traversal that "
+ + "represented this XML Document.");
+ }
+
+ /*
+ * Current path now points to the element we just started. Validate
+ * its attributes.
+ */
+ validateAttributes(atts);
+
+ traversedElements.add(new TraversedElement(elemQName, TraversedElement.Traversal.START));
+ elementStack.add(elemQName);
+
+ /*
+ * If this is element is of type xsd:any, we do not track it or its
+ * children. So, we keep a stack of the element and its children,
+ * allowing us to know when we leave and can start tracking elements
+ * again.
+ */
+ if (currentPath.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ANY)) {
+ if (anyStack == null) {
+ anyStack = new ArrayList<QName>();
+ }
+ anyStack.add(elemQName);
+ }
+
+ } catch (Exception e) {
+ /*
+ * A SAX Exception cannot be thrown because it is caught, and its
+ * internal exception is thrown instead. Likewise, any useful info
+ * about the error reported in the wrapper SAXException is lost.
+ */
+ throw new RuntimeException("Error occurred while starting element " + elemQName
+ + "; traversed path is " + getElementsTraversedAsString(), e);
+ }
+ }
+
+ /**
+ * Adds a new {@link XmlSchemaPathNode.Direction#CONTENT}
+ * {@link XmlSchemaPathNode} to the path. Throws an
+ * {@link IllegalStateException} if the owning element should not receive
+ * content, or the content is empty when it should not be.
+ *
+ * @see org.xml.sax.helpers.DefaultHandler#characters(char[], int, int)
+ */
+ @Override
+ public void characters(char[] ch, int start, int length) throws SAXException {
+
+ /*
+ * If the most recent path node is an element with simple content,
+ * confirm these characters match the data type expected. If we are not
+ * expecting an element with simple content, and the characters don't
+ * represent all whitespace, throw an exception.
+ */
+
+ try {
+ if (currentPath.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ANY)
+ && (anyStack != null) && !anyStack.isEmpty()) {
+ /*
+ * If this represents a wildcard element, we don't care - we
+ * won't be processing the content.
+ */
+ return;
+ }
+
+ final XmlSchemaStateMachineNode state = getStateMachineOfOwningElement();
+
+ final XmlSchemaElement element = state.getElement();
+ final XmlSchemaTypeInfo elemTypeInfo = state.getElementType();
+
+ final String text = new String(ch, start, length).trim();
+
+ final boolean elemExpectsContent = ((elemTypeInfo != null) && (!elemTypeInfo.getType()
+ .equals(XmlSchemaTypeInfo.Type.COMPLEX) || elemTypeInfo.isMixed()));
+
+ if (!elemExpectsContent && (text.length() == 0)) {
+ // Nothing to see here.
+ return;
+
+ } else if (!elemExpectsContent && (text.length() > 0)) {
+ throw new IllegalStateException("Element " + state.getElement().getQName()
+ + " has no content, but we received \"" + text + "\" for it.");
+
+ } else if (elemExpectsContent && (text.length() == 0) && !state.getElement().isNillable()
+ && !elemTypeInfo.isMixed() && (element.getDefaultValue() == null)
+ && (element.getFixedValue() == null)) {
+ throw new IllegalStateException("Received empty text for element "
+ + state.getElement().getQName()
+ + " when content was expected.");
+ }
+
+ XmlSchemaElementValidator.validateContent(state, text, nsContext);
+
+ currentPath.getDocumentNode().setReceivedContent(true);
+
+ final XmlSchemaPathNode contentPath = pathMgr
+ .addParentSiblingOrContentNodeToPath(currentPath, XmlSchemaPathNode.Direction.CONTENT);
+
+ currentPath.setNextNode(-1, contentPath);
+ currentPath = contentPath;
+
+ traversedElements
+ .add(new TraversedElement(element.getQName(), TraversedElement.Traversal.CONTENT));
+
+ } catch (Exception e) {
+ throw new RuntimeException("Error occurred while processing characters; traversed path was "
+ + getElementsTraversedAsString(), e);
+ }
+ }
+
+ /**
+ * Ends the current element. If the current element is not of the provided
+ * <code>uri</code> and <code>localName</code>, throws an
+ * {@link IllegalStateException}.
+ *
+ * @see DefaultHandler#endElement(String, String, String)
+ */
+ @Override
+ public void endElement(String uri, String localName, String qName) throws SAXException {
+ final QName elemQName = new QName(uri, localName);
+
+ try {
+ final boolean isAny = (currentPath.getStateMachineNode().getNodeType()
+ .equals(XmlSchemaStateMachineNode.Type.ANY)
+ && (anyStack != null) && !anyStack.isEmpty());
+
+ if (!isAny && !elementStack.get(elementStack.size() - 1).equals(elemQName)) {
+ throw new IllegalStateException("Attempting to end element " + elemQName
+ + " but the stack is expecting "
+ + elementStack.get(elementStack.size() - 1));
+ }
+
+ if (!isAny) {
+ walkUpToElement(elemQName);
+ }
+
+ final XmlSchemaStateMachineNode state = currentPath.getStateMachineNode();
+
+ if (state.getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT)) {
+
+ // 1. Is this the element we are looking for?
+ if (!state.getElement().getQName().equals(elemQName)) {
+ throw new IllegalStateException("We are ending element " + elemQName
+ + " but our current position is for element "
+ + state.getElement().getQName() + '.');
+ }
+
+ // 2. Check the element received the expected content, if any.
+ final XmlSchemaTypeInfo elemTypeInfo = state.getElementType();
+
+ final boolean elemExpectsContent = (elemTypeInfo != null)
+ && (!elemTypeInfo.getType()
+ .equals(XmlSchemaTypeInfo.Type.COMPLEX));
+
+ if (elemExpectsContent && !state.getElement().isNillable()
+ && (state.getElement().getDefaultValue() == null)
+ && (state.getElement().getFixedValue() == null)
+ && !currentPath.getDocumentNode().getReceivedContent()) {
+ throw new IllegalStateException("We are ending element " + elemQName
+ + "; it expected to receive content but did not.");
+ }
+ }
+
+ traversedElements.add(new TraversedElement(elemQName, TraversedElement.Traversal.END));
+
+ elementStack.remove(elementStack.size() - 1);
+ if (isAny) {
+ anyStack.remove(anyStack.size() - 1);
+ }
+
+ if ((anyStack == null) || anyStack.isEmpty()) {
+ walkUpTree(elemQName);
+ }
+
+ } catch (Exception e) {
+ throw new RuntimeException("Error occurred while ending element " + elemQName
+ + "; traversed path was " + getElementsTraversedAsString(), e);
+ }
+ }
+
+ /**
+ * Called when the XML Document traversal is complete.
+ * <p>
+ * Confirms all open elements have been closed. If not, throws an
+ * {@link IllegalStateException}.
+ * </p>
+ */
+ @Override
+ public void endDocument() throws SAXException {
+ if (!elementStack.isEmpty()) {
+ throw new IllegalStateException("Ended the document but " + elementStack.size()
+ + " elements have not been closed.");
+ }
+
+ pathMgr.clear();
+
+ if (decisionPoints != null) {
+ decisionPoints.clear();
+ }
+ }
+
+ /**
+ * Once a traversal completes successfully, this method may be called to
+ * retrieve the relevant interpretation of the path through the
+ * {@link XmlSchemaStateMachineNode}s.
+ * <p>
+ * {@link XmlSchemaPathNode#getDocumentNode()} can be called to retrieve the
+ * interpretation of the XML Schema as applied to the document; meanwhile
+ * the walk through {@link XmlSchemaPathNode}s will show how that schema was
+ * traversed.
+ * </p>
+ */
+ public XmlSchemaPathNode getXmlSchemaTraversal() {
+ return rootPathNode;
+ }
+
+ private static Fulfillment isPositionFulfilled(XmlSchemaPathNode currentPath, List<Integer> possiblePaths) {
+
+ boolean completelyFulfilled = true;
+ boolean partiallyFulfilled = true;
+
+ final XmlSchemaStateMachineNode state = currentPath.getStateMachineNode();
+
+ if (currentPath.getDocumentNode() == null) {
+ // This is the root node. It is not fulfilled.
+ partiallyFulfilled = false;
+ } else if (currentPath.getDocIteration() >= state.getMinOccurs()) {
+ partiallyFulfilled = true;
+ } else {
+ partiallyFulfilled = false;
+ }
+
+ if (currentPath.getDocumentNode() == null) {
+ completelyFulfilled = false;
+ } else if (currentPath.getDocIteration() == state.getMaxOccurs()) {
+ completelyFulfilled = true;
+ } else if (currentPath.getDocIteration() > state.getMaxOccurs()) {
+ throw new IllegalStateException("Current path's document iteration of "
+ + currentPath.getDocIteration()
+ + " is greater than the maximum number of occurrences ("
+ + state.getMaxOccurs() + ").");
+
+ } else {
+ completelyFulfilled = false;
+ }
+
+ final List<XmlSchemaStateMachineNode> nextStates = state.getPossibleNextStates();
+
+ Map<Integer, XmlSchemaDocumentNode> children = null;
+ if (currentPath.getDocumentNode() != null) {
+ children = currentPath.getDocumentNode().getChildren();
+ }
+
+ switch (state.getNodeType()) {
+ case ELEMENT:
+ case ANY:
+ // We only needed to perform the occurrence check.
+ break;
+ case CHOICE:
+ case SUBSTITUTION_GROUP: {
+ /*
+ * If any child meets the minimum number, we are partially
+ * fulfilled. If all elements meet the maximum, we are completely
+ * fulfilled.
+ */
+ boolean groupPartiallyFulfilled = false;
+ boolean groupCompletelyFulfilled = false;
+ for (int stateIndex = 0; stateIndex < nextStates.size(); ++stateIndex) {
+
+ XmlSchemaStateMachineNode nextState = nextStates.get(stateIndex);
+
+ if ((children != null) && children.containsKey(stateIndex)) {
+ final XmlSchemaDocumentNode child = children.get(stateIndex);
+ final int iteration = child.getIteration();
+ if (iteration >= nextState.getMinOccurs()) {
+ groupPartiallyFulfilled = true;
+ if (possiblePaths != null) {
+ possiblePaths.clear();
+ if (iteration < nextState.getMaxOccurs()) {
+ possiblePaths.add(stateIndex);
+ } else {
+ groupCompletelyFulfilled = true;
+ }
+ }
+ break;
+ } else if (possiblePaths != null) {
+ possiblePaths.add(stateIndex);
+ }
+ } else {
+ if (nextState.getMinOccurs() == 0) {
+ groupPartiallyFulfilled = true;
+ }
+ if (nextState.getMaxOccurs() == 0) {
+ groupCompletelyFulfilled = true;
+ } else if (possiblePaths != null) {
+ possiblePaths.add(stateIndex);
+ }
+ }
+ }
+ partiallyFulfilled &= groupPartiallyFulfilled;
+ completelyFulfilled &= groupCompletelyFulfilled;
+ break;
+ }
+ case ALL: {
+ // If all children meet the minimum number, we succeeded.
+ for (int stateIndex = 0; stateIndex < nextStates.size(); ++stateIndex) {
+
+ final XmlSchemaStateMachineNode nextState = nextStates.get(stateIndex);
+
+ if ((children != null) && children.containsKey(stateIndex)) {
+ final XmlSchemaDocumentNode child = children.get(stateIndex);
+ final int iteration = child.getIteration();
+ if (iteration < nextState.getMinOccurs()) {
+ partiallyFulfilled = false;
+ }
+ if (iteration < nextState.getMaxOccurs()) {
+ completelyFulfilled = false;
+ if (possiblePaths != null) {
+ possiblePaths.add(stateIndex);
+ }
+ }
+ } else {
+ if (nextState.getMinOccurs() > 0) {
+ partiallyFulfilled = false;
+ }
+ if (nextState.getMaxOccurs() > 0) {
+ completelyFulfilled = false;
+ if (possiblePaths != null) {
+ possiblePaths.add(stateIndex);
+ }
+ }
+ }
+ }
+
+ break;
+ }
+ case SEQUENCE: {
+ // If the sequence is complete, we succeeded.
+ int stateIndex = currentPath.getDocSequencePosition();
+ if (stateIndex < 0) {
+ stateIndex = 0;
+ }
+ for (; stateIndex < nextStates.size(); ++stateIndex) {
+ final XmlSchemaStateMachineNode nextState = nextStates.get(stateIndex);
+
+ if ((children != null) && children.containsKey(stateIndex)) {
+ final XmlSchemaDocumentNode child = children.get(stateIndex);
+ if (child.getIteration() < nextState.getMinOccurs()) {
+ partiallyFulfilled = false;
+ }
+ if (child.getIteration() < nextState.getMaxOccurs()) {
+ completelyFulfilled = false;
+ if (possiblePaths != null) {
+ possiblePaths.add(stateIndex);
+ }
+ }
+ } else {
+ if (nextState.getMinOccurs() > 0) {
+ partiallyFulfilled = false;
+ }
+ if (nextState.getMaxOccurs() > 0) {
+ completelyFulfilled = false;
+ if (possiblePaths != null) {
+ possiblePaths.add(stateIndex);
+ }
+ }
+ }
+ }
+ break;
+ }
+ default:
+ throw new IllegalStateException("Current position has a node of unrecognized type \""
+ + currentPath.getStateMachineNode().getNodeType() + '\"');
+ }
+
+ Fulfillment fulfillment = Fulfillment.NOT;
+ if (completelyFulfilled) {
+ fulfillment = Fulfillment.COMPLETE;
+ } else if (partiallyFulfilled) {
+ fulfillment = Fulfillment.PARTIAL;
+ }
+ return fulfillment;
+ }
+
+ private List<PathSegment> find(XmlSchemaPathNode startNode, QName elemQName) {
+
+ final XmlSchemaPathNode startOfPath = startNode;
+
+ if (startNode.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT)
+ && !elementStack.isEmpty()
+ && startNode.getStateMachineNode().getElement().getQName()
+ .equals(elementStack.get(elementStack.size() - 1))) {
+
+ /*
+ * We are at an element in an existing document. This is the start
+ * node of a child. Likewise we need to move down one level to the
+ * children.
+ */
+ verifyCurrentPositionIsAtElement("Started element " + elemQName);
+
+ if (startNode.getStateMachineNode().getPossibleNextStates() == null) {
+
+ final String elemName = getLeafNodeName(startNode.getStateMachineNode());
+
+ throw new IllegalStateException("Element " + elemName
+ + " has null children! Exactly one is expected.");
+
+ } else if (startNode.getStateMachineNode().getPossibleNextStates().isEmpty()) {
+
+ final String elemName = getLeafNodeName(startNode.getStateMachineNode());
+
+ throw new IllegalStateException("Element " + elemName
+ + " has zero children! Exactly one is expected.");
+
+ } else if (currentPath.getStateMachineNode().getPossibleNextStates().size() > 1) {
+
+ final String elemName = getLeafNodeName(currentPath.getStateMachineNode());
+
+ throw new IllegalStateException("Element "
+ + elemName
+ + " has "
+ + currentPath.getStateMachineNode().getPossibleNextStates()
+ .size() + " children! Only one was expected.");
+ }
+
+ if ((startNode.getDocumentNode() != null) && (startNode.getDocumentNode().getChildren() != null)
+ && !startNode.getDocumentNode().getChildren().isEmpty()
+ && (startNode.getDocumentNode().getChildren().size() > 1)) {
+ throw new IllegalStateException(
+ "There are multiple children in the document node for element "
+ + currentPath.getStateMachineNode().getElement()
+ .getQName());
+ }
+
+ final XmlSchemaPathNode childPath = pathMgr.addChildNodeToPath(startNode, 0);
+
+ startNode.setNextNode(0, childPath);
+ startNode = childPath;
+ }
+
+ final List<PathSegment> choices = find(startNode, elemQName, null);
+
+ if ((choices != null) && (startOfPath != startNode)) {
+ /*
+ * If we moved down to the children, we need to prepend the path
+ * with the original start node.
+ */
+ for (PathSegment choice : choices) {
+ choice.prepend(startOfPath, 0);
+ }
+ }
+
+ return choices;
+ }
+
+ private List<PathSegment> find(XmlSchemaPathNode startNode, QName elemQName,
+ XmlSchemaStateMachineNode doNotFollow) {
+
+ final ArrayList<Integer> childrenNodes = new ArrayList<Integer>();
+ final boolean isFulfilled = !isPositionFulfilled(startNode, childrenNodes).equals(Fulfillment.NOT);
+
+ // First, try searching down the tree.
+ List<PathSegment> choices = null;
+ List<PathSegment> currChoices = null;
+
+ if (startNode.getIteration() > startNode.getDocIteration()) {
+ choices = find(startNode, elemQName, 0);
+ } else {
+ for (Integer childPath : childrenNodes) {
+ if (doNotFollow == startNode.getStateMachineNode().getPossibleNextStates().get(childPath)) {
+ /*
+ * We are coming up from a child node; do not traverse back
+ * down to that child.
+ */
+ continue;
+ }
+ final XmlSchemaPathNode currPath = pathMgr.addChildNodeToPath(startNode, childPath);
+
+ currChoices = find(currPath, elemQName, 0);
+ if (currChoices != null) {
+ for (PathSegment choice : currChoices) {
+ choice.prepend(startNode, childPath);
+ }
+
+ if (choices == null) {
+ choices = currChoices;
+ } else {
+ choices.addAll(currChoices);
+ }
+ }
+ }
+ }
+
+ // Second, if the node is currently fulfilled, try siblings and parents.
+ if (isFulfilled) {
+
+ // Try siblings.
+ if (startNode.getIteration() < startNode.getMaxOccurs()) {
+ final XmlSchemaPathNode siblingPath = pathMgr
+ .addParentSiblingOrContentNodeToPath(startNode, XmlSchemaPathNode.Direction.SIBLING);
+ siblingPath.setIteration(startNode.getIteration() + 1);
+
+ currChoices = find(siblingPath, elemQName, 0);
+ if (currChoices != null) {
+ for (PathSegment choice : currChoices) {
+ choice.prepend(startNode, -1);
+ }
+
+ if (choices == null) {
+ choices = currChoices;
+ } else {
+ choices.addAll(currChoices);
+ }
+ }
+ }
+
+ // Try parent.
+ if (startNode.getDocumentNode().getParent() == null) {
+ // This is the root element; there is no parent.
+ return choices;
+ }
+
+ final XmlSchemaPathNode path = pathMgr
+ .addParentSiblingOrContentNodeToPath(startNode, XmlSchemaPathNode.Direction.PARENT);
+
+ if (path.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT)
+ && path.getStateMachineNode().getElement().getQName()
+ .equals(elementStack.get(elementStack.size() - 1))) {
+ return choices;
+ }
+
+ final List<PathSegment> pathsOfParent = find(path, elemQName, startNode.getStateMachineNode());
+
+ if (pathsOfParent != null) {
+ for (PathSegment choice : pathsOfParent) {
+ choice.prepend(startNode, -1);
+ }
+
+ if (choices == null) {
+ choices = pathsOfParent;
+ } else {
+ choices.addAll(pathsOfParent);
+ }
+ } else {
+ // path would not have been recycled at a lower level.
+ pathMgr.recyclePathNode(path);
+ }
+ }
+
+ return choices;
+ }
+
+ private List<PathSegment> find(XmlSchemaPathNode startNode, QName elemQName, int currDepth) {
+
+ final XmlSchemaStateMachineNode state = startNode.getStateMachineNode();
+
+ if (currDepth > MAX_DEPTH) {
+ /*
+ * We are likely in an infinite recursive loop looking for an
+ * element in a group whose definition includes itself. Likewise,
+ * we'll stop here and say we were unable to find the element we
+ * were looking for.
+ */
+ return null;
+
+ } else if (startNode.getStateMachineNode() != state) {
+
+ throw new IllegalStateException("While searching for " + elemQName
+ + ", the DocumentPathNode state machine ("
+ + startNode.getStateMachineNode().getNodeType()
+ + ") does not match the tree node (" + state.getNodeType() + ").");
+
+ } else if (startNode.getIteration() <= startNode.getDocIteration()) {
+ throw new IllegalStateException("While searching for " + elemQName
+ + ", the DocumentPathNode iteration (" + startNode.getIteration()
+ + ") should be greater than the tree node's iteration ("
+ + startNode.getDocIteration()
+ + "). Current state machine position is " + state.getNodeType());
+
+ } else if (state.getMaxOccurs() < startNode.getIteration()) {
+ return null;
+ }
+
+ // If this is a group, confirm it has children.
+ if (!state.getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT)
+ && !state.getNodeType().equals(XmlSchemaStateMachineNode.Type.ANY)
+ && ((state.getPossibleNextStates() == null) || state.getPossibleNextStates().isEmpty())) {
+
+ throw new IllegalStateException("Group " + state.getNodeType()
+ + " has no children. Found when processing " + elemQName);
+ }
+
+ List<PathSegment> choices = null;
+
+ switch (state.getNodeType()) {
+ case ELEMENT: {
+ if (state.getElement().getQName().equals(elemQName)
+ && startNode.getIteration() <= state.getMaxOccurs()) {
+
+ choices = new ArrayList<PathSegment>(1);
+ choices.add(new PathSegment(startNode));
+ }
+ }
+ break;
+
+ case SEQUENCE: {
+ // Find the next one in the sequence that matches.
+ int position = startNode.getDocSequencePosition();
+
+ if (startNode.getDocIteration() > startNode.getMaxOccurs()) {
+ throw new IllegalStateException("Somehow the document iteration for "
+ + startNode.getStateMachineNode() + " of "
+ + startNode.getDocIteration()
+ + " exceeds the maximum number of occurrences of "
+ + startNode.getMaxOccurs());
+
+ } else if (startNode.getDocIteration() == startNode.getMaxOccurs()) {
+ ++position;
+ }
+
+ for (int stateIndex = position; stateIndex < startNode.getStateMachineNode()
+ .getPossibleNextStates().size(); ++stateIndex) {
+
+ // Process child.
+ final XmlSchemaPathNode nextPath = pathMgr.addChildNodeToPath(startNode, stateIndex);
+
+ /*
+ * Both the tree node's and the document path node's state
+ * machine nodes should point to the same state machine node in
+ * memory.
+ */
+ if (nextPath.getIteration() > nextPath.getMaxOccurs()) {
+ throw new IllegalStateException("Reached a sequence group when searching for "
+ + elemQName
+ + " whose iteration at the current position ("
+ + nextPath.getIteration() + ") was already maxed out ("
+ + nextPath.getMaxOccurs() + "). Was at position "
+ + stateIndex + "; tree node's starting position was "
+ + startNode.getDocSequencePosition());
+ }
+
+ final boolean reachedMinOccurs = (nextPath.getDocIteration() >= nextPath.getMinOccurs());
+
+ final List<PathSegment> seqPaths = find(nextPath, elemQName, currDepth + 1);
+
+ if (seqPaths != null) {
+ for (PathSegment seqPath : seqPaths) {
+ seqPath.prepend(startNode, stateIndex);
+ }
+
+ // nextPath was cloned by all path segments, so it can be
+ // recycled.
+ pathMgr.recyclePathNode(nextPath);
+
+ if (choices == null) {
+ choices = seqPaths;
+ } else {
+ choices.addAll(seqPaths);
+ }
+ }
+
+ if (!reachedMinOccurs) {
+
+ /*
+ * If we have not traversed this node in the sequence the
+ * minimum number of times, we cannot advance to the next
+ * node in the sequence.
+ */
+ break;
+ }
+ }
+
+ break;
+ }
+
+ case ALL:
+ case SUBSTITUTION_GROUP:
+ case CHOICE: {
+ /*
+ * All groups only contain elements. Find one that matches. The
+ * max-occurrence check will confirm it wasn't already selected.
+ * Choice groups may have multiple paths through its children which
+ * are valid. In addition, a wild card ("any" element) may be a
+ * child of any group, thus creating another decision point.
+ */
+ for (int stateIndex = 0; stateIndex < state.getPossibleNextStates().size(); ++stateIndex) {
+
+ final XmlSchemaStateMachineNode nextState = state.getPossibleNextStates().get(stateIndex);
+
+ if (state.getNodeType().equals(XmlSchemaStateMachineNode.Type.ALL)
+ && !nextState.getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT)
+ && !nextState.getNodeType().equals(XmlSchemaStateMachineNode.Type.SUBSTITUTION_GROUP)
+ && !nextState.getNodeType().equals(XmlSchemaStateMachineNode.Type.ANY)) {
+
+ throw new IllegalStateException(
+ "While searching for "
+ + elemQName
+ + ", encountered an All group which contained a child of type "
+ + nextState.getNodeType() + '.');
+ }
+
+ final XmlSchemaPathNode nextPath = pathMgr.addChildNodeToPath(startNode, stateIndex);
+
+ final List<PathSegment> choicePaths = find(nextPath, elemQName, currDepth + 1);
+
+ if (choicePaths != null) {
+ for (PathSegment choicePath : choicePaths) {
+ choicePath.prepend(startNode, stateIndex);
+ }
+
+ // nextPath was cloned by all path segments, so it can be
+ // recycled.
+ pathMgr.recyclePathNode(nextPath);
+
+ if (choices == null) {
+ choices = choicePaths;
+ } else {
+ choices.addAll(choicePaths);
+ }
+ }
+ }
+
+ break;
+ }
+ case ANY: {
+ /*
+ * If the XmlSchemaAny namespace and processing rules apply, this
+ * element matches. False otherwise.
+ */
+ if (traversedElements.size() < 2) {
+ throw new IllegalStateException("Reached a wildcard element while searching for " + elemQName
+ + ", but we've only seen " + traversedElements.size()
+ + " element(s)!");
+ }
+
+ final XmlSchemaAny any = state.getAny();
+
+ if (any.getNamespace() == null) {
+ choices = new ArrayList<PathSegment>(1);
+ choices.add(new PathSegment(startNode));
+ break;
+ }
+
+ boolean needTargetNamespace = false;
+ boolean matches = false;
+ boolean matchOnNotTargetNamespace = false;
+
+ List<String> validNamespaces = null;
+
+ if (any.getNamespace().equals("##any")) {
+ // Any namespace is valid. This matches.
+ matches = true;
+
+ } else if (any.getNamespace().equals("##other")) {
+ needTargetNamespace = true;
+ matchOnNotTargetNamespace = true;
+ validNamespaces = new ArrayList<String>(1);
+
+ } else {
+ final String[] namespaces = any.getNamespace().trim().split(" ");
+ validNamespaces = new ArrayList<String>(namespaces.length);
+ for (String namespace : namespaces) {
+ if ("##targetNamespace".equals(namespace)) {
+ needTargetNamespace = true;
+
+ } else if ("##local".equals(namespace) && (elemQName.getNamespaceURI() == null)) {
+
+ matches = true;
+
+ } else {
+ validNamespaces.add(namespace);
+ }
+ }
+ }
+
+ if (!matches) {
+ if (needTargetNamespace) {
+ validNamespaces.add(any.getTargetNamespace());
+ }
+
+ matches = validNamespaces.contains(elemQName.getNamespaceURI());
+
+ if (matchOnNotTargetNamespace) {
+ matches = !matches;
+ }
+ }
+
+ if (matches) {
+ choices = new ArrayList<PathSegment>(1);
+ choices.add(new PathSegment(startNode));
+ }
+ }
+ break;
+ default:
+ throw new IllegalStateException("Unrecognized node type " + state.getNodeType()
+ + " when processing element " + elemQName);
+ }
+
+ if ((choices == null) && (currDepth > 0)) {
+ pathMgr.recyclePathNode(startNode);
+ }
+ return choices;
+ }
+
+ /*
+ * Walks up the tree from the current element to the prior one. Confirms the
+ * provided QName matches the current one before traversing. If currElem is
+ * null, the current position must be a wildcard element.
+ */
+ private void walkUpTree(QName currElem) {
+ final XmlSchemaStateMachineNode state = currentPath.getStateMachineNode();
+
+ switch (state.getNodeType()) {
+ case ANY:
+ break;
+ case ELEMENT:
+ if (!state.getElement().getQName().equals(currElem)) {
+ throw new IllegalStateException("We expected to walk upwards from element " + currElem
+ + ", but our current element is "
+ + state.getElement().getQName());
+ }
+ break;
+ default:
+ throw new IllegalStateException("We expected to walk upwards from element " + currElem
+ + ", but our current position is in a node of type "
+ + state.getNodeType());
+ }
+
+ XmlSchemaDocumentNode iter = currentPath.getDocumentNode();
+ XmlSchemaPathNode path = currentPath;
+
+ do {
+ if (iter.getIteration() < iter.getStateMachineNode().getMaxOccurs()) {
+ break;
+ }
+
+ if (!isPositionFulfilled(path, null).equals(Fulfillment.COMPLETE)) {
+ break;
+ }
+
+ iter = iter.getParent();
+
+ if (iter == null) {
+ // We are exiting the root node. Nothing to see here!
+ break;
+ }
+
+ final XmlSchemaPathNode nextPath = pathMgr
+ .addParentSiblingOrContentNodeToPath(path, XmlSchemaPathNode.Direction.PARENT);
+
+ path.setNextNode(-1, nextPath);
+ path = nextPath;
+
+ } while (!iter.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT));
+
+ currentPath = path;
+ }
+
+ private void walkUpToElement(QName element) {
+ XmlSchemaDocumentNode iter = currentPath.getDocumentNode();
+
+ if (iter.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT)
+ && iter.getStateMachineNode().getElement().getQName().equals(element)) {
+ // We are already at the element!
+ return;
+ }
+
+ do {
+
+ iter = iter.getParent();
+ if (iter != null) {
+ final XmlSchemaPathNode nextPath = pathMgr
+ .addParentSiblingOrContentNodeToPath(currentPath, XmlSchemaPathNode.Direction.PARENT);
+
+ currentPath.setNextNode(-1, nextPath);
+ currentPath = nextPath;
+ }
+ } while ((iter != null)
+ && !iter.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT));
+
+ if (!currentPath.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT)
+ || !currentPath.getStateMachineNode().getElement().getQName().equals(element)) {
+ throw new IllegalStateException("Walked up tree and stopped at node "
+ + currentPath.getStateMachineNode()
+ + ", which does not represent element " + element);
+ }
+ }
+
+ private void followPath(PathSegment path) {
+ switch (path.getEnd().getStateMachineNode().getNodeType()) {
+ case ELEMENT:
+ case ANY:
+ break;
+ default:
+ throw new IllegalStateException("Path does not end in an element or a wildcard element.");
+ }
+
+ // Join the start element with the new path.
+ XmlSchemaPathNode startNode = path.getStart();
+
+ if (path.getAfterStart() != null) {
+ startNode.setNextNode(path.getAfterStartPathIndex(), path.getAfterStart());
+ }
+
+ pathMgr.followPath(startNode);
+
+ currentPath = path.getEnd();
+ }
+
+ /*
+ * Perhaps this would be better implemented as a bunch of starting and
+ * ending tags on separate lines, properly indented, to generate an XML
+ * document similar to the one being parsed? An idea to consider later.
+ */
+ private String getElementsTraversedAsString() {
+ final StringBuilder traversed = new StringBuilder("[");
+ if ((traversedElements != null) && !traversedElements.isEmpty()) {
+ for (int i = 0; i < traversedElements.size() - 1; ++i) {
+ traversed.append(traversedElements.get(i)).append(" | ");
+ }
+ traversed.append(traversedElements.get(traversedElements.size() - 1));
+ }
+ traversed.append(" ]");
+
+ return traversed.toString();
+ }
+
+ private void verifyCurrentPositionIsAtElement(String errMsgPrefix) {
+ if (!currentPath.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT)
+
+ && !currentPath.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ANY)) {
+
+ throw new IllegalStateException(errMsgPrefix + " when our current position in the tree is a "
+ + currentPath.getStateMachineNode().getNodeType() + '.');
+ }
+ }
+
+ private String getLeafNodeName(XmlSchemaStateMachineNode node) {
+ if (!node.getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT)
+ && !node.getNodeType().equals(XmlSchemaStateMachineNode.Type.ANY)) {
+
+ throw new IllegalStateException(
+ "State machine node needs to be an element or a wildcard element, "
+ + "not a " + currentPath.getStateMachineNode().getNodeType()
+ + '.');
+ }
+
+ String elemName = "a wildcard element";
+ if (node.getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT)) {
+ elemName = node.getElement().getQName().toString();
+ }
+ return elemName;
+ }
+
+ private XmlSchemaStateMachineNode getStateMachineOfOwningElement() {
+ QName element = elementStack.get(elementStack.size() - 1);
+ XmlSchemaDocumentNode iter = currentPath.getDocumentNode();
+
+ if (iter.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT)
+ && iter.getStateMachineNode().getElement().getQName().equals(element)) {
+ // We are already at the element!
+ return currentPath.getStateMachineNode();
+ }
+
+ do {
+ iter = iter.getParent();
+ } while ((iter != null)
+ && !iter.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT));
+
+ if (!iter.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ELEMENT)
+ || !iter.getStateMachineNode().getElement().getQName().equals(element)) {
+ throw new IllegalStateException("Walked up tree and stopped at node "
+ + currentPath.getStateMachineNode()
+ + ", which does not represent element " + element);
+ }
+
+ return iter.getStateMachineNode();
+ }
+
+ private void validateAttributes(Attributes attrs) {
+ if (currentPath.getStateMachineNode().getNodeType().equals(XmlSchemaStateMachineNode.Type.ANY)) {
+ // No validation is performed on ANY elements.
+ return;
+ }
+
+ try {
+ XmlSchemaElementValidator.validateAttributes(currentPath.getStateMachineNode(), attrs, nsContext);
+ } catch (ValidationException ve) {
+ throw new IllegalStateException(
+ "Cannot validate attributes of "
+ + currentPath.getStateMachineNode().getElement().getQName()
+ + '.', ve);
+ }
+ }
+}
Propchange: webservices/xmlschema/trunk/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/XmlSchemaPathFinder.java
------------------------------------------------------------------------------
svn:eol-style = native