From commits-return-4402-apmail-ws-commits-archive=ws.apache.org@ws.apache.org Wed Sep 17 15:33:30 2014 Return-Path: X-Original-To: apmail-ws-commits-archive@minotaur.apache.org Delivered-To: apmail-ws-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 5AE3211475 for ; Wed, 17 Sep 2014 15:33:30 +0000 (UTC) Received: (qmail 18189 invoked by uid 500); 17 Sep 2014 15:33:30 -0000 Delivered-To: apmail-ws-commits-archive@ws.apache.org Received: (qmail 18154 invoked by uid 500); 17 Sep 2014 15:33:30 -0000 Mailing-List: contact commits-help@ws.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@ws.apache.org Delivered-To: mailing list commits@ws.apache.org Received: (qmail 18091 invoked by uid 99); 17 Sep 2014 15:33:30 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 17 Sep 2014 15:33:30 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 17 Sep 2014 15:32:51 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id D9C5C23889DA; Wed, 17 Sep 2014 15:32:47 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: 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... Date: Wed, 17 Sep 2014 15:32:46 -0000 To: commits@ws.apache.org From: dkulp@apache.org X-Mailer: svnmailer-1.0.9 Message-Id: <20140917153247.D9C5C23889DA@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org 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}. + *

+ * Implemented as a series of scope-based stacks, one per prefix. + *

+ */ +public final class XmlSchemaNamespaceContext implements NamespacePrefixList { + + private Map> namespacesByPrefixStack; + + /** + * Constructs a new XmlSchemaNamespaceContext with the + * following initial mappings: + *
    + *
  • + * xml -> http://www.w3.org/1999/namespace
    • + *
  • + * xmlns -> http://www.w3.org/2000/xmlns/
    • + *
+ */ + public XmlSchemaNamespaceContext() { + namespacesByPrefixStack = new HashMap>(); + + 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 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> prefixEntry : namespacesByPrefixStack.entrySet()) { + + final List 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 prefixes = new ArrayList(); + + for (Map.Entry> prefixEntry : namespacesByPrefixStack.entrySet()) { + + final List 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 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 namespaceStack = namespacesByPrefixStack.get(prefix); + if (namespaceStack == null) { + namespaceStack = new ArrayList(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 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. + *

+ * 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}. + *

+ *

+ * 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. + *

+ */ +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 traversedElements; + private ArrayList decisionPoints; + + private ArrayList elementStack; + private ArrayList 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 { + + 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) 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 DescisionPoint 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 choices; + private final int traversedElementIndex; + private final ArrayList elementStack; + private final ArrayList anyStack; + + DecisionPoint(XmlSchemaPathNode decisionPoint, List choices, int traversedElementIndex, + ArrayList elementStack, ArrayList 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(elementStack); + + if (anyStack == null) { + this.anyStack = null; + } else { + this.anyStack = new ArrayList(anyStack); + } + + java.util.Collections.sort(choices); + } + + /** + * Returns the next PathSegment to try, or + * null if all PathSegments have been + * followed. + */ + PathSegment tryNextPath() { + if (choices.isEmpty()) { + return null; + } else { + return choices.remove(0); + } + } + + XmlSchemaPathNode getDecisionPoint() { + return decisionPoint; + } + + ArrayList getElementStack() { + return new ArrayList(elementStack); + } + + ArrayList getAnyStack() { + return (anyStack == null) ? null : ((ArrayList)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 XmlToAvroPathCreator 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(); + elementStack = new ArrayList(); + currentPath = null; + decisionPoints = null; // Hopefully there won't be any! + } + + /** + * Kick-starts a new SAX walk, building new XmlSchemaPathNode + * and XmlSchemaDocumentNode 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 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(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(); + } + 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(); + } + 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(); + } + 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 + * uri and localName, 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. + *

+ * Confirms all open elements have been closed. If not, throws an + * {@link IllegalStateException}. + *

+ */ + @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. + *

+ * {@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. + *

+ */ + public XmlSchemaPathNode getXmlSchemaTraversal() { + return rootPathNode; + } + + private static Fulfillment isPositionFulfilled(XmlSchemaPathNode currentPath, List 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 nextStates = state.getPossibleNextStates(); + + Map 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 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 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 find(XmlSchemaPathNode startNode, QName elemQName, + XmlSchemaStateMachineNode doNotFollow) { + + final ArrayList childrenNodes = new ArrayList(); + final boolean isFulfilled = !isPositionFulfilled(startNode, childrenNodes).equals(Fulfillment.NOT); + + // First, try searching down the tree. + List choices = null; + List 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 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 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 choices = null; + + switch (state.getNodeType()) { + case ELEMENT: { + if (state.getElement().getQName().equals(elemQName) + && startNode.getIteration() <= state.getMaxOccurs()) { + + choices = new ArrayList(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 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 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(1); + choices.add(new PathSegment(startNode)); + break; + } + + boolean needTargetNamespace = false; + boolean matches = false; + boolean matchOnNotTargetNamespace = false; + + List 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(1); + + } else { + final String[] namespaces = any.getNamespace().trim().split(" "); + validNamespaces = new ArrayList(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(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