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); | |
} | |
} | |
} |