ws-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dk...@apache.org
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 GMT
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



Mime
View raw message