| package net.sf.saxon.om; |
| |
| public final class Navigator { |
| |
| /** |
| * Determine if a string is all-whitespace |
| * |
| * @param content the string to be tested |
| * @return true if the supplied string contains no non-whitespace |
| * characters |
| */ |
| |
| public final static boolean isWhite(CharSequence content) { |
| for (int i=0; i<content.length();) { |
| // all valid XML whitespace characters, and only whitespace characters, are <= 0x20 |
| if (content.charAt(i++) > 32) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| /** |
| * Get the string value of an attribute of a given element, given the URI and |
| * local part of the attribute name. |
| * @return the attribute value, or null if the attribute is not present |
| */ |
| |
| public static String getAttributeValue(NodeInfo element, String uri, String localName) { |
| int fingerprint = element.getNamePool().allocate("", uri, localName); |
| return element.getAttributeValue(fingerprint); |
| } |
| |
| /** |
| * Get an absolute XPath expression that identifies a given node within its document |
| * |
| * @param node the node whose path is required |
| * @return a path expression that can be used to retrieve the node |
| */ |
| |
| public static String getPath(NodeInfo node) { |
| String pre; |
| NodeInfo parent = node.getParent(); |
| // System.err.println("node = " + node + " parent = " + parent); |
| // Handle parentless nodes of any kind |
| if (parent==null) return "/"; |
| switch (node.getNodeKind()) { |
| case Type.DOCUMENT: |
| return "/"; |
| case Type.ELEMENT: |
| pre = getPath(parent); |
| return (pre.equals("/") ? "" : pre) + |
| "/" + node.getDisplayName() + "[" + getNumberSimple(node) + "]"; |
| case Type.ATTRIBUTE: |
| return getPath(parent) + "/@" + node.getDisplayName(); |
| case Type.TEXT: |
| pre = getPath(parent); |
| return (pre.equals("/") ? "" : pre) + |
| "/text()[" + getNumberSimple(node) + "]"; |
| case Type.COMMENT: |
| pre = getPath(parent); |
| return (pre.equals("/") ? "" : pre) + |
| "/comment()[" + getNumberSimple(node) + "]"; |
| case Type.PROCESSING_INSTRUCTION: |
| pre = getPath(parent); |
| return (pre.equals("/") ? "" : pre) + |
| "/processing-instruction()[" + getNumberSimple(node) + "]"; |
| default: |
| return ""; |
| } |
| } |
| |
| /** |
| * Get simple node number. This is defined as one plus the number of previous siblings of the |
| * same node type and name. It is not accessible directly in XSL. |
| * |
| * @param node The node whose number is required |
| * @param controller Used for remembering previous result, for |
| * performance |
| * @exception XPathException if any error occurs |
| * @return the node number, as defined above |
| */ |
| |
| public static int getNumberSimple(NodeInfo node, Controller controller) throws XPathException { |
| |
| //checkNumberable(node); |
| |
| int fingerprint = node.getFingerprint(); |
| NodeTest same; |
| |
| if (fingerprint==-1) { |
| same = NodeKindTest.makeNodeKindTest(node.getNodeKind()); |
| } else { |
| same = new NameTest(node); |
| } |
| |
| SequenceIterator preceding = node.iterateAxis(Axis.PRECEDING_SIBLING, same); |
| |
| int i=1; |
| while (true) { |
| NodeInfo prev = (NodeInfo)preceding.next(); |
| if (prev == null) { |
| break; |
| } |
| |
| int memo = controller.getRememberedNumber(prev); |
| if (memo>0) { |
| memo += i; |
| controller.setRememberedNumber(node, memo); |
| return memo; |
| } |
| |
| i++; |
| } |
| |
| controller.setRememberedNumber(node, i); |
| return i; |
| } |
| |
| /** |
| * Get simple node number. This is defined as one plus the number of previous siblings of the |
| * same node type and name. It is not accessible directly in XSL. This version doesn't require |
| * the controller, and therefore doesn't remember previous results. It is used only by getPath(). |
| * |
| * @param node the node whose number is required |
| * @return the node number, as defined above |
| */ |
| |
| private static int getNumberSimple(NodeInfo node) { |
| |
| int fingerprint = node.getFingerprint(); |
| NodeTest same; |
| |
| if (fingerprint==-1) { |
| same = NodeKindTest.makeNodeKindTest(node.getNodeKind()); |
| } else { |
| same = new NameTest(node); |
| } |
| |
| AxisIterator preceding = node.iterateAxis(Axis.PRECEDING_SIBLING, same); |
| |
| int i=1; |
| while (preceding.next() != null) { |
| i++; |
| } |
| |
| return i; |
| } |
| |
| /** |
| * Get node number (level="single"). If the current node matches the supplied pattern, the returned |
| * number is one plus the number of previous siblings that match the pattern. Otherwise, |
| * return the element number of the nearest ancestor that matches the supplied pattern. |
| * |
| * @param node the current node, the one whose node number is required |
| * @param count Pattern that identifies which nodes should be |
| * counted. Default (null) is the element name if the current node is |
| * an element, or "node()" otherwise. |
| * @param from Pattern that specifies where counting starts from. |
| * Default (null) is the root node. (This parameter does not seem |
| * useful but is included for the sake of XSLT conformance.) |
| * @param controller the controller of the transformation, used if |
| * the patterns reference context values (e.g. variables) |
| * @exception XPathException when any error occurs in processing |
| * @return the node number established as follows: go to the nearest |
| * ancestor-or-self that matches the 'count' pattern and that is a |
| * descendant of the nearest ancestor that matches the 'from' pattern. |
| * Return one plus the nunber of preceding siblings of that ancestor |
| * that match the 'count' pattern. If there is no such ancestor, |
| * return 0. |
| */ |
| |
| public static int getNumberSingle(NodeInfo node, Pattern count, |
| Pattern from, Controller controller) throws XPathException { |
| |
| // checkNumberable(node); |
| |
| if (count==null && from==null) { |
| return getNumberSimple(node, controller); |
| } |
| |
| boolean knownToMatch = false; |
| if (count==null) { |
| if (node.getFingerprint()==-1) { // unnamed node |
| count = NodeKindTest.makeNodeKindTest(node.getNodeKind()); |
| } else { |
| count = new NameTest(node); |
| } |
| knownToMatch = true; |
| } |
| |
| NodeInfo target = node; |
| while (!(knownToMatch || count.matches(target, controller))) { |
| target = target.getParent(); |
| if (target==null) { |
| return 0; |
| } |
| if (from!=null && from.matches(target, controller)) { |
| return 0; |
| } |
| } |
| |
| // we've found the ancestor to count from |
| |
| SequenceIterator preceding = |
| target.iterateAxis(Axis.PRECEDING_SIBLING, count.getNodeTest()); |
| // pass the filter condition down to the axis enumeration where possible |
| boolean alreadyChecked = (count instanceof NodeTest); |
| int i = 1; |
| while (true) { |
| NodeInfo p = (NodeInfo)preceding.next(); |
| if (p == null) { |
| return i; |
| } |
| if (alreadyChecked || count.matches(p, controller)) { |
| i++; |
| } |
| } |
| } |
| |
| /** |
| * Get node number (level="any"). |
| * Return one plus the number of previous nodes in the |
| * document that match the supplied pattern |
| * |
| * @exception XPathException |
| * @param inst Identifies the xsl:number instruction; this is relevant |
| * when the function is memoised to support repeated use of the same |
| * instruction to number modulple nodes |
| * @param node Identifies the xsl:number instruction; this is |
| * relevant when the function is memoised to support repeated use of |
| * the same instruction to number modulple nodes |
| * @param count Pattern that identifies which nodes should be |
| * counted. Default (null) is the element name if the current node is |
| * an element, or "node()" otherwise. |
| * @param from Pattern that specifies where counting starts from. |
| * Default (null) is the root node. Only nodes after the first (most |
| * recent) node that matches the 'from' pattern are counted. |
| * @param controller The controller |
| * @param hasVariablesInPatterns if the count or from patterns |
| * contain variables, then it's not safe to get the answer by adding |
| * one to the number of the most recent node that matches |
| * @return one plus the number of nodes that precede the current node, |
| * that match the count pattern, and that follow the first node that |
| * matches the from pattern if specified. |
| */ |
| |
| public static int getNumberAny(Instruction inst, NodeInfo node, Pattern count, |
| Pattern from, Controller controller, boolean hasVariablesInPatterns) throws XPathException { |
| |
| NodeInfo memoNode = null; |
| int memoNumber = 0; |
| boolean memoise = (!hasVariablesInPatterns && count!=null); |
| if (memoise) { |
| Object[] memo = (Object[])controller.getUserData(inst, "xsl:number"); |
| if (memo != null) { |
| memoNode = (NodeInfo)memo[0]; |
| memoNumber = ((Integer)memo[1]).intValue(); |
| } |
| } |
| |
| int num = 0; |
| if (count==null) { |
| if (node.getFingerprint()==-1) { // unnamed node |
| count = NodeKindTest.makeNodeKindTest(node.getNodeKind()); |
| } else { |
| count = new NameTest(node); |
| } |
| num = 1; |
| } else if (count.matches(node, controller)) { |
| num = 1; |
| } |
| |
| // We use a special axis invented for the purpose: the union of the preceding and |
| // ancestor axes, but in reverse document order |
| |
| // Pass part of the filtering down to the axis iterator if possible |
| NodeTest filter; |
| if (from==null) { |
| filter = count.getNodeTest(); |
| } else if (from.getNodeKind()==Type.ELEMENT && count.getNodeKind()==Type.ELEMENT) { |
| filter = NodeKindTest.ELEMENT; |
| } else { |
| filter = AnyNodeTest.getInstance(); |
| } |
| |
| SequenceIterator preceding = |
| node.iterateAxis(Axis.PRECEDING_OR_ANCESTOR, filter); |
| |
| while (true) { |
| NodeInfo prev = (NodeInfo)preceding.next(); |
| if (prev == null) { |
| break; |
| } |
| if (from!=null && from.matches(prev, controller)) { |
| return num; |
| } |
| if (count.matches(prev, controller)) { |
| if (num==1 && memoNode!=null && prev.isSameNode(memoNode)) { |
| num = memoNumber + 1; |
| break; |
| } |
| num++; |
| } |
| } |
| if (memoise) { |
| Object[] memo = new Object[2]; |
| memo[0] = node; |
| memo[1] = new Integer(num); |
| controller.setUserData(inst, "xsl:number", memo); |
| } |
| return num; |
| } |
| |
| /** |
| * Get node number (level="multiple"). |
| * Return a vector giving the hierarchic position of this node. See the XSLT spec for details. |
| * |
| * @exception XPathException |
| * @param node The node to be numbered |
| * @param count Pattern that identifies which nodes (ancestors and |
| * their previous siblings) should be counted. Default (null) is the |
| * element name if the current node is an element, or "node()" |
| * otherwise. |
| * @param from Pattern that specifies where counting starts from. |
| * Default (null) is the root node. Only nodes below the first (most |
| * recent) node that matches the 'from' pattern are counted. |
| * @param controller The controller for the transformation |
| * @return a vector containing for each ancestor-or-self that matches the |
| * count pattern and that is below the nearest node that matches the |
| * from pattern, an Integer which is one greater than the number of |
| * previous siblings that match the count pattern. |
| */ |
| |
| public static List getNumberMulti(NodeInfo node, Pattern count, |
| Pattern from, Controller controller) throws XPathException { |
| |
| //checkNumberable(node); |
| |
| ArrayList v = new ArrayList(); |
| |
| if (count==null) { |
| if (node.getFingerprint()==-1) { // unnamed node |
| count = NodeKindTest.makeNodeKindTest(node.getNodeKind()); |
| } else { |
| count = new NameTest(node); |
| } |
| } |
| |
| NodeInfo curr = node; |
| |
| while(true) { |
| if (count.matches(curr, controller)) { |
| int num = getNumberSingle(curr, count, null, controller); |
| v.add(0, new Long(num)); |
| } |
| curr = curr.getParent(); |
| if (curr==null) break; |
| if (from!=null && from.matches(curr, controller)) break; |
| } |
| |
| return v; |
| } |
| |
| /** |
| * Generic (model-independent) implementation of deep copy algorithm for nodes. |
| * This is available for use by any node implementations that choose to use it. |
| * @param node The node to be copied |
| * @param out The receiver to which events will be sent |
| * @param namePool Namepool holding the name codes (used only to resolve namespace |
| * codes) |
| * @param whichNamespaces Indicates which namespace nodes for an element should |
| * be copied |
| * @param copyAnnotations Indicates whether type annotations should be copied |
| * @throws TransformerException on any failure reported by the Receiver |
| */ |
| |
| public static void copy(NodeInfo node, |
| Receiver out, |
| NamePool namePool, |
| int whichNamespaces, |
| boolean copyAnnotations) throws TransformerException { |
| |
| switch (node.getNodeKind()) { |
| case Type.DOCUMENT: |
| AxisIterator children0 = node.iterateAxis(Axis.CHILD, new AnyNodeTest()); |
| while (true) { |
| NodeInfo child = (NodeInfo)children0.next(); |
| if (child == null) { |
| return; |
| } |
| child.copy(out, whichNamespaces, copyAnnotations); |
| } |
| |
| case Type.ELEMENT: |
| out.startElement(node.getNameCode(), 0, 0); |
| |
| // output the namespaces |
| |
| if (whichNamespaces != NodeInfo.NO_NAMESPACES) { |
| node.outputNamespaceNodes(out, true); |
| } |
| |
| // output the attributes |
| |
| AxisIterator attributes = node.iterateAxis(Axis.ATTRIBUTE, new AnyNodeTest()); |
| while (true) { |
| NodeInfo att = (NodeInfo)attributes.next(); |
| if (att == null) { |
| break; |
| } |
| att.copy(out, whichNamespaces, copyAnnotations); |
| } |
| |
| // output the children |
| |
| AxisIterator children = node.iterateAxis(Axis.CHILD, new AnyNodeTest()); |
| while (true) { |
| NodeInfo child = (NodeInfo)children.next(); |
| if (child == null) { |
| break; |
| } |
| child.copy(out, whichNamespaces, copyAnnotations); |
| } |
| |
| // finally the end tag |
| |
| out.endElement(); |
| return; |
| |
| case Type.ATTRIBUTE: |
| out.attribute(node.getNameCode(), 0, node.getStringValue(), 0); |
| return; |
| |
| case Type.TEXT: |
| out.characters(node.getStringValue(), 0); |
| return; |
| |
| case Type.COMMENT: |
| out.comment(node.getStringValue(), 0); |
| return; |
| |
| case Type.PROCESSING_INSTRUCTION: |
| out.processingInstruction(node.getLocalPart(), node.getStringValue(), 0); |
| return; |
| |
| case Type.NAMESPACE: |
| out.namespace(namePool.allocateNamespaceCode(node.getLocalPart(), node.getStringValue()),0); |
| return; |
| |
| default: |
| |
| } |
| } |
| |
| /** |
| * Generic (model-independent) method to determine the relative position of two |
| * node in document order. The nodes must be in the same tree. |
| * @param first The first node |
| * @param second The second node, whose position is to be compared with the first node |
| * @return -1 if this node precedes the other node, +1 if it follows the other |
| * node, or 0 if they are the same node. (In this case, isSameNode() will always |
| * return true, and the two nodes will produce the same result for generateId()) |
| */ |
| |
| public static int compareOrder(SiblingCountingNode first, SiblingCountingNode second) { |
| NodeInfo ow = second; |
| |
| // are they the same node? |
| if (first.isSameNode(second)) { |
| return 0; |
| } |
| // are they siblings (common case) |
| if (first.getParent().isSameNode(second.getParent())) { |
| return first.getSiblingPosition() - second.getSiblingPosition(); |
| } |
| // find the depths of both nodes in the tree |
| |
| int depth1 = 0; |
| int depth2 = 0; |
| NodeInfo p1 = first; |
| NodeInfo p2 = second; |
| while (p1 != null) { |
| depth1++; |
| p1 = p1.getParent(); |
| } |
| while (p2 != null) { |
| depth2++; |
| p2 = p2.getParent(); |
| } |
| // move up one branch of the tree so we have two nodes on the same level |
| |
| p1 = first; |
| while (depth1>depth2) { |
| p1 = p1.getParent(); |
| if (p1.isSameNode(second)) { |
| return +1; |
| } |
| depth1--; |
| } |
| |
| p2 = ow; |
| while (depth2>depth1) { |
| p2 = p2.getParent(); |
| if (p2.isSameNode(first)) { |
| return -1; |
| } |
| depth2--; |
| } |
| |
| // now move up both branches in sync until we find a common parent |
| while (true) { |
| NodeInfo par1 = p1.getParent(); |
| NodeInfo par2 = p2.getParent(); |
| if (par1==null || par2==null) { |
| throw new NullPointerException("DOM tree compare - internal error"); |
| } |
| if (par1.isSameNode(par2)) { |
| return ((SiblingCountingNode)p1).getSiblingPosition() - |
| ((SiblingCountingNode)p2).getSiblingPosition(); |
| } |
| p1 = par1; |
| p2 = par2; |
| } |
| } |
| |
| /** |
| * Get a character string that uniquely identifies this node and that collates nodes |
| * into document order |
| * @return a string. The string is always interned so keys can be compared using "==". |
| */ |
| |
| public static String getSequentialKey(SiblingCountingNode node) { |
| // TODO: this was designed so it could be used for sorting nodes into document |
| // order, but is not currently used that way. |
| StringBuffer key = new StringBuffer(); |
| while(!(node instanceof DocumentInfo)) { |
| key.insert(0, alphaKey(node.getSiblingPosition())); |
| node = (SiblingCountingNode)node.getParent(); |
| } |
| key.insert(0, "w" + node.getDocumentNumber()); |
| return key.toString().intern(); |
| } |
| |
| /** |
| * Construct an alphabetic key from an positive integer; the key collates in the same sequence |
| * as the integer |
| * @param value The positive integer key value (negative values are treated as zero). |
| */ |
| |
| public static String alphaKey(int value) { |
| if (value<1) return "a"; |
| if (value<10) return "b" + value; |
| if (value<100) return "c" + value; |
| if (value<1000) return "d" + value; |
| if (value<10000) return "e" + value; |
| if (value<100000) return "f" + value; |
| if (value<1000000) return "g" + value; |
| if (value<10000000) return "h" + value; |
| if (value<100000000) return "i" + value; |
| if (value<1000000000) return "j" + value; |
| return "k" + value; |
| } |
| |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| // Helper classes to support axis iteration |
| /////////////////////////////////////////////////////////////////////////////// |
| |
| /** |
| * AxisFilter is an iterator that applies a NodeTest filter to |
| * the nodes returned by an underlying AxisIterator. |
| */ |
| |
| public static class AxisFilter extends AxisIteratorImpl { |
| private int last = -1; |
| |
| /** |
| * Construct a AxisFilter |
| * @param base the underlying iterator that returns all the nodes on |
| * a required axis. This must not be an atomizing iterator! |
| * @param test a NodeTest that is applied to each node returned by the |
| * underlying AxisIterator; only those nodes that pass the NodeTest are |
| * returned by the AxisFilter |
| */ |
| |
| public AxisFilter(AxisIterator base, NodeTest test) { |
| this.base = base; |
| this.nodeTest = test; |
| position = 0; |
| } |
| |
| public Item next() { |
| while (true) { |
| current = base.next(); |
| if (current == null) { |
| return null; |
| } |
| NodeInfo n = (NodeInfo)current; |
| if (nodeTest.matches(n.getNodeKind(), |
| n.getFingerprint(), |
| n.getTypeAnnotation())) { |
| position++; |
| return current; |
| } |
| } |
| } |
| |
| public int getLastPosition() { |
| |
| // To find out how many nodes there are in the axis, we |
| // make a copy of the original node enumeration, and run through |
| // the whole thing again, counting how many nodes match the filter. |
| |
| if (last>=0) { |
| return last; |
| } |
| last = 0; |
| AxisIterator b = (AxisIterator)base.getAnother(); |
| while (true) { |
| NodeInfo n = (NodeInfo)b.next(); |
| if (n == null) { |
| return last; |
| } |
| if (nodeTest.matches(n.getNodeKind(), |
| n.getFingerprint(), |
| n.getTypeAnnotation())) { |
| last++; |
| } |
| } |
| } |
| |
| public SequenceIterator getAnother() { |
| return new AxisFilter((AxisIterator)base.getAnother(), nodeTest); |
| } |
| } |
| } |