sboag 00/10/17 12:40:20
Modified: java/src/org/apache/xpath/axes AxesWalker.java
FilterExprWalker.java LocPathIterator.java
SubContextList.java
Added: java/src/org/apache/xpath/axes AttributeWalkerOneStep.java
ChildWalkerMultiStep.java ChildWalkerOneStep.java
SelfWalkerOneStep.java WalkerFactory.java
Log:
Optimize some searches based on an compile-time analysis of the pattern.
Other minor optimizations also.
Revision Changes Path
1.5 +40 -146 xml-xalan/java/src/org/apache/xpath/axes/AxesWalker.java
Index: AxesWalker.java
===================================================================
RCS file: /home/cvs/xml-xalan/java/src/org/apache/xpath/axes/AxesWalker.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- AxesWalker.java 2000/08/23 15:58:49 1.4
+++ AxesWalker.java 2000/10/17 19:40:13 1.5
@@ -105,7 +105,7 @@
{
m_lpi = locPathIterator;
}
-
+
/**
* Init an AxesWalker.
*/
@@ -143,124 +143,11 @@
clone.m_proximityPositions = new int[this.m_proximityPositions.length];
System.arraycopy(this.m_proximityPositions, 0,
clone.m_proximityPositions, 0, this.m_proximityPositions.length);
}
+ m_testedForNTF = false;
return clone;
}
/**
- * Create the proper Walker from the axes type.
- */
- public static AxesWalker createDefaultWalker(Compiler compiler,
- int opPos,
- LocPathIterator lpi)
- {
- AxesWalker ai;
- int whatToShow = compiler.getWhatToShow(opPos);
- int stepType = compiler.getOp(opPos);
- /*
- System.out.println("0: "+compiler.getOp(opPos));
- System.out.println("1: "+compiler.getOp(opPos+1));
- System.out.println("2: "+compiler.getOp(opPos+2));
- System.out.println("3: "+compiler.getOp(opPos+3));
- System.out.println("4: "+compiler.getOp(opPos+4));
- System.out.println("5: "+compiler.getOp(opPos+5));
- */
- boolean simpleInit = false;
- switch(stepType)
- {
- case OpCodes.OP_VARIABLE:
- case OpCodes.OP_EXTFUNCTION:
- case OpCodes.OP_FUNCTION:
- case OpCodes.OP_GROUP:
- ai = new FilterExprWalker(lpi);
- simpleInit = true;
- break;
- case OpCodes.FROM_ROOT:
- ai = new RootWalker(lpi);
- simpleInit = true;
- break;
- case OpCodes.FROM_ANCESTORS:
- ai = new AncestorWalker(lpi);
- break;
- case OpCodes.FROM_ANCESTORS_OR_SELF:
- ai = new AncestorOrSelfWalker(lpi);
- break;
- case OpCodes.FROM_ATTRIBUTES:
- ai = new AttributeWalker(lpi);
- break;
- case OpCodes.FROM_NAMESPACE:
- ai = new NamespaceWalker(lpi);
- break;
- case OpCodes.FROM_CHILDREN:
- ai = new ChildWalker(lpi);
- {
- if(false &&
compiler.getPatternString().startsWith("(preceding-sibling::*|following-sibling::*)"))
- {
- ai.DEBUG = true;
- ai.DEBUG_LOCATED = true;
- ai.DEBUG_TRAVERSAL = true;
- ai.DEBUG_WAITING = true;
- }
- }
- break;
- case OpCodes.FROM_DESCENDANTS:
- ai = new DescendantWalker(lpi);
- break;
- case OpCodes.FROM_DESCENDANTS_OR_SELF:
- ai = new DescendantOrSelfWalker(lpi);
- break;
- case OpCodes.FROM_FOLLOWING:
- ai = new FollowingWalker(lpi);
- break;
- case OpCodes.FROM_FOLLOWING_SIBLINGS:
- ai = new FollowingSiblingWalker(lpi);
- break;
- case OpCodes.FROM_PRECEDING:
- ai = new PrecedingWalker(lpi);
- break;
- case OpCodes.FROM_PRECEDING_SIBLINGS:
- ai = new PrecedingSiblingWalker(lpi);
- break;
- case OpCodes.FROM_PARENT:
- ai = new ParentWalker(lpi);
- break;
- case OpCodes.FROM_SELF:
- ai = new SelfWalker(lpi);
- break;
-
- case OpCodes.MATCH_ATTRIBUTE:
- ai = new AttributeWalker(lpi);
- break;
- case OpCodes.MATCH_ANY_ANCESTOR:
- ai = new ChildWalker(lpi);
- break;
- case OpCodes.MATCH_IMMEDIATE_ANCESTOR:
- ai = new ChildWalker(lpi);
- break;
- default:
- throw new RuntimeException("Programmer's assertion: unknown opcode:
"+stepType);
- }
- /*
- System.out.print("construct: ");
- NodeTest.debugWhatToShow(whatToShow);
- System.out.println("or stuff: "+(whatToShow & (NodeFilter.SHOW_ATTRIBUTE
- | NodeFilter.SHOW_ELEMENT
- | NodeFilter.SHOW_PROCESSING_INSTRUCTION)));
- */
- if((0 == (whatToShow & (NodeFilter.SHOW_ATTRIBUTE
- | NodeFilter.SHOW_ELEMENT
- | NodeFilter.SHOW_PROCESSING_INSTRUCTION))) ||
- (whatToShow == NodeFilter.SHOW_ALL))
- ai.initNodeTest(whatToShow);
- else
- {
- ai.initNodeTest(whatToShow,
- compiler.getStepNS(opPos),
- compiler.getStepLocalName(opPos));
- }
- return ai;
- }
-
- /**
* Reset the Walker.
*/
public void reset()
@@ -280,8 +167,16 @@
*/
private int m_argLen;
protected int getArgLen() { return m_argLen; }
-
+
/**
+ * The type of this walker based on the pattern analysis.
+ * @see org.apache.xpath.axes.WalkerFactory
+ */
+ protected int m_analysis = WalkerFactory.NO_OPTIMIZE;
+ int getAnalysis() { return m_analysis; }
+ void setAnalysis(int a) { m_analysis = a; }
+
+ /**
* An array of counts that correspond to the number
* of predicates the step contains.
*/
@@ -369,7 +264,7 @@
{
return m_predicateIndex;
}
-
+
/**
* Process the predicates.
*/
@@ -429,7 +324,7 @@
* Number of predicates (in effect).
*/
int m_predicateCount;
-
+
/**
* Get the number of predicates that this walker has.
*/
@@ -445,7 +340,7 @@
{
m_predicateCount = count;
}
-
+
/**
* Init predicate info.
*/
@@ -463,7 +358,7 @@
{
return m_predicates[index];
}
-
+
/**
* Tell if the given node is a parent of the
* step context, or the step context node itself.
@@ -485,7 +380,7 @@
* The root node of the TreeWalker, as specified when it was created.
*/
Node m_root;
-
+
/**
* The root node of the TreeWalker, as specified in setRoot(Node root).
* Note that this may actually be below the current node.
@@ -541,7 +436,7 @@
* NOT_SUPPORTED_ERR: Raised if the specified <code>currentNode</code>
* is<code>null</code> .
*/
- public Node getCurrentNode()
+ public final Node getCurrentNode()
{
return m_currentNode;
}
@@ -591,7 +486,7 @@
{
return true;
}
-
+
/**
* Moves to and returns the closest visible ancestor node of the current
* node. If the search for parentNode attempts to step upward from the
@@ -670,8 +565,8 @@
{
throw new RuntimeException("previousNode not supported!");
}
-
- private AxesWalker m_nextWalker;
+
+ protected AxesWalker m_nextWalker;
public void setNextWalker(AxesWalker walker)
{
@@ -750,7 +645,7 @@
: "null";
}
}
-
+
/**
* Diagnostics.
*/
@@ -972,7 +867,7 @@
return ok;
}
-
+
private boolean m_didSwitch = false;
/**
@@ -1000,7 +895,7 @@
ws.toString()+", .);");
if(checkOKToTraverse(prevStepWalker, ws,
- ws.m_currentNode,
ws.m_nextLevelAmount))
+ ws.m_currentNode, ws.m_nextLevelAmount))
{
if(null != walker)
{
@@ -1024,7 +919,7 @@
}
}
}
-
+
return walker;
}
@@ -1087,7 +982,7 @@
printDebug("Calling checkOKToTraverse("+prevWalker.toString()+", "+
walker.toString()+", .);");
if(!checkOKToTraverse(prevWalker, walker,
- walker.m_currentNode, walker.m_nextLevelAmount))
+ walker.m_currentNode, walker.m_nextLevelAmount))
{
if(DEBUG_WAITING)
printDebug("[Adding "+walker.toString()+" to WAITING list");
@@ -1114,6 +1009,9 @@
boolean m_isDone = false;
+ // See note where this is used about this variable.
+ protected boolean m_testedForNTF = false;
+
/**
* Get the next node in document order on the axes.
*/
@@ -1122,13 +1020,9 @@
if(m_isFresh)
m_isFresh = false;
- try
- {
- // I wish there was a better way to do this...
- // System.out.println("\nCalling setNodeTest on:
"+(this.getCurrentNode()));
- ((NodeTestFilter)this.getCurrentNode()).setNodeTest(this);
- }
- catch(ClassCastException cce){}
+ Node current = this.getCurrentNode();
+ if(current.supports("NodeTestFilter", "1.0"))
+ ((NodeTestFilter)current).setNodeTest(this);
Node next = this.firstChild();
@@ -1173,7 +1067,7 @@
Node nextNode = null;
AxesWalker walker = m_lpi.getLastUsedWalker();
// DOMHelper dh = m_lpi.getDOMHelper();
- walker.printEntryDebug();
+ // walker.printEntryDebug();
m_didSwitch = false;
boolean processWaiters = true;
@@ -1213,7 +1107,7 @@
if(null == nextNode)
{
- AxesWalker prev = walker;
+ // AxesWalker prev = walker; ?? -sb
walker = walker.m_prevWalker;
if(null != walker)
walker.printEntryDebug();
@@ -1259,7 +1153,7 @@
walker = walker.m_nextWalker;
/*
if((walker.getRoot() != null) &&
- prev.getLevelMax() >= walker.getLevelMax()) // bogus, but
might be ok
+ prev.getLevelMax() >= walker.getLevelMax()) // bogus, but might
be ok
*/
if(isWaiting(walker))
{
@@ -1291,12 +1185,12 @@
} // while(null != walker)
}
- // Not sure what is going on here, but we were loosing
- // the next node in the nodeset because it's coming from a
- // different document.
- while((null != nextNode) && (null != m_prevReturned)
- && nextNode.getOwnerDocument() ==
m_prevReturned.getOwnerDocument()
- && m_lpi.getDOMHelper().isNodeAfter(nextNode, m_prevReturned));
+ // Not sure what is going on here, but we were loosing
+ // the next node in the nodeset because it's coming from a
+ // different document.
+ while((null != nextNode) && (null != m_prevReturned)
+ && nextNode.getOwnerDocument() ==
m_prevReturned.getOwnerDocument()
+ && m_lpi.getDOMHelper().isNodeAfter(nextNode, m_prevReturned));
m_prevReturned = nextNode;
if(DEBUG_LOCATED)
1.4 +3 -6
xml-xalan/java/src/org/apache/xpath/axes/FilterExprWalker.java
Index: FilterExprWalker.java
===================================================================
RCS file:
/home/cvs/xml-xalan/java/src/org/apache/xpath/axes/FilterExprWalker.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- FilterExprWalker.java 2000/08/07 02:49:53 1.3
+++ FilterExprWalker.java 2000/10/17 19:40:13 1.4
@@ -210,12 +210,9 @@
{
if(null != m_nodeSet)
{
- try
- {
- // I wish there was a better way to do this...
- ((NodeTestFilter)m_nodeSet).setNodeTest(this);
- }
- catch(ClassCastException cce){}
+ Node current = this.getCurrentNode();
+ if(current instanceof NodeTestFilter)
+ ((NodeTestFilter)current).setNodeTest(this);
next = m_nodeSet.nextNode();
}
1.4 +4 -69
xml-xalan/java/src/org/apache/xpath/axes/LocPathIterator.java
Index: LocPathIterator.java
===================================================================
RCS file:
/home/cvs/xml-xalan/java/src/org/apache/xpath/axes/LocPathIterator.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- LocPathIterator.java 2000/10/04 07:50:02 1.3
+++ LocPathIterator.java 2000/10/17 19:40:14 1.4
@@ -118,8 +118,8 @@
throws org.xml.sax.SAXException
{
int firstStepPos = compiler.getFirstChildPos(opPos);
- this.loadWalkers(compiler, firstStepPos, 0);
- // allocateWalkerStacks(m_firstStepPos);
+ m_firstWalker = WalkerFactory.loadWalkers(this, compiler, firstStepPos,
0);
+ m_lastUsedWalker = m_firstWalker;
}
/**
@@ -129,9 +129,7 @@
boolean isMatchPattern)
throws org.xml.sax.SAXException
{
- loadOneWalker(compiler, opPos);
- // m_firstStepPos = xpath.getFirstChildPos(opPos);
- // allocateWalkerStacks(firstStepPos);
+ m_firstWalker = WalkerFactory.loadOneWalker(this, compiler, opPos);
}
ObjectPool m_pool = new ObjectPool();
@@ -489,71 +487,8 @@
break;
}
}
- }
-
- /**
- * List of AxesIterators.
- */
- private Stack m_savedAxesWalkers = new Stack();
-
- /**
- * <meta name="usage" content="advanced"/>
- * This method is for building an array of possible levels
- * where the target element(s) could be found for a match.
- * @param xpath The xpath that is executing.
- * @param context The current source tree context node.
- */
- protected void loadOneWalker(Compiler compiler, int stepOpCodePos)
- throws org.xml.sax.SAXException
- {
- int stepType = compiler.getOpMap()[stepOpCodePos];
- if( stepType != OpCodes.ENDOP )
- {
- // m_axesWalkers = new AxesWalker[1];
-
- // As we unwind from the recursion, create the iterators.
- AxesWalker ai = AxesWalker.createDefaultWalker(compiler, stepType,
this);
- ai.init(compiler, stepOpCodePos, stepType);
- m_firstWalker = ai;
- }
- }
-
- /**
- * <meta name="usage" content="advanced"/>
- * This method is for building an array of possible levels
- * where the target element(s) could be found for a match.
- * @param xpath The xpath that is executing.
- * @param context The current source tree context node.
- */
- protected void loadWalkers(Compiler compiler, int stepOpCodePos, int
stepIndex)
- throws org.xml.sax.SAXException
- {
- int stepType;
- AxesWalker walker, prevWalker = null;
- int ops[] = compiler.getOpMap();
- while( OpCodes.ENDOP != (stepType = ops[stepOpCodePos]) )
- {
-
- // As we unwind from the recursion, create the iterators.
- walker = AxesWalker.createDefaultWalker(compiler, stepOpCodePos, this);
- walker.init(compiler, stepOpCodePos, stepType);
- if(null == m_firstWalker)
- {
- m_firstWalker = walker;
- m_lastUsedWalker = walker;
- }
- else
- {
- prevWalker.setNextWalker(walker);
- walker.setPrevWalker(prevWalker);
- }
- prevWalker = walker;
- stepOpCodePos = compiler.getNextStepPos(stepOpCodePos);
- if(stepOpCodePos < 0)
- break;
- }
}
-
+
/**
*
*/
1.2 +1 -0
xml-xalan/java/src/org/apache/xpath/axes/SubContextList.java
Index: SubContextList.java
===================================================================
RCS file:
/home/cvs/xml-xalan/java/src/org/apache/xpath/axes/SubContextList.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- SubContextList.java 2000/07/05 14:45:15 1.1
+++ SubContextList.java 2000/10/17 19:40:15 1.2
@@ -13,3 +13,4 @@
*/
public int getProximityPosition(XPathContext xctxt);
}
+
\ No newline at end of file
1.1
xml-xalan/java/src/org/apache/xpath/axes/AttributeWalkerOneStep.java
Index: AttributeWalkerOneStep.java
===================================================================
/*
* The Apache Software License, Version 1.1
*
*
* Copyright (c) 1999 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Xalan" and "Apache Software Foundation" must
* not be used to endorse or promote products derived from this
* software without prior written permission. For written
* permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache",
* nor may "Apache" appear in their name, without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation and was
* originally based on software copyright (c) 1999, Lotus
* Development Corporation., http://www.lotus.com. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
package org.apache.xpath.axes;
import org.w3c.dom.Node;
import org.w3c.dom.NamedNodeMap;
import org.w3c.dom.traversal.NodeFilter;
import org.apache.xpath.patterns.NodeTestFilter;
public class AttributeWalkerOneStep extends AxesWalker
{
NamedNodeMap m_attributeList;
int m_attrListPos;
int m_nAttrs;
/**
* The root node of the TreeWalker.
*/
public void setRoot(Node root)
{
super.setRoot(root);
if(root.getNodeType() == Node.ELEMENT_NODE)
{
m_attrListPos = -1;
m_attributeList = m_currentNode.getAttributes();
if(null != m_attributeList)
m_nAttrs = m_attributeList.getLength();
else
m_nAttrs = -2;
}
}
/**
* Construct an AxesWalker using a LocPathIterator.
*/
public AttributeWalkerOneStep(LocPathIterator locPathIterator)
{
super(locPathIterator);
}
/**
* Set the analysis ID.
* @see org.apache.xpath.axes.WalkerFactory
*/
void setAnalysis(int a)
{
super.setAnalysis(a);
}
/**
* Get the next node in document order on the axes.
*/
public Node nextNode()
{
if(m_isFresh)
m_isFresh = false;
Node current = this.getCurrentNode();
if(current.supports("NodeTestFilter", "1.0"))
((NodeTestFilter)current).setNodeTest(this);
Node next =null;
while(null != m_attributeList)
{
m_attrListPos++;
if(m_attrListPos < m_nAttrs)
{
next = m_attributeList.item(m_attrListPos);
if(null != next)
m_currentNode = next;
if(acceptNode(next) == NodeFilter.FILTER_ACCEPT)
break;
}
else
{
next = null;
m_attributeList = null;
}
}
if(null == next)
this.m_isDone = true;
return next;
}
}
1.1
xml-xalan/java/src/org/apache/xpath/axes/ChildWalkerMultiStep.java
Index: ChildWalkerMultiStep.java
===================================================================
/*
* The Apache Software License, Version 1.1
*
*
* Copyright (c) 1999 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Xalan" and "Apache Software Foundation" must
* not be used to endorse or promote products derived from this
* software without prior written permission. For written
* permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache",
* nor may "Apache" appear in their name, without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation and was
* originally based on software copyright (c) 1999, Lotus
* Development Corporation., http://www.lotus.com. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
package org.apache.xpath.axes;
import org.w3c.dom.Node;
import org.w3c.dom.traversal.NodeFilter;
import org.apache.xpath.patterns.NodeTestFilter;
/**
* <meta name="usage" content="internal"/>
* Class ChildWalkerMultiStep
* <needs-description/>
*
* @author [EMAIL PROTECTED]
*/
public class ChildWalkerMultiStep extends AxesWalker
{
/**
* Construct an ChildWalkerMultiStep using a LocPathIterator.
*
* @param locPathIterator
*/
public ChildWalkerMultiStep(LocPathIterator locPathIterator)
{
super(locPathIterator);
}
/**
* Get the next node in document order on the axes.
*
* @return the next valid child node.
*/
protected Node getNextNode()
{
if (m_isFresh)
m_isFresh = false;
Node current = this.getCurrentNode();
if (current.supports("NodeTestFilter", "1.0"))
((NodeTestFilter) current).setNodeTest(this);
Node next = (m_root == m_currentNode) ?
m_currentNode.getFirstChild() :
m_currentNode.getNextSibling();
if (null != next)
{
m_currentNode = next;
while (acceptNode(next) != NodeFilter.FILTER_ACCEPT)
{
next = next.getNextSibling();
if (null != next)
m_currentNode = next;
else
break;
}
}
if (null == next)
this.m_isDone = true;
return next;
}
/**
* Moves the <code>TreeWalker</code> to the next visible node in document
* order relative to the current node, and returns the new node. If the
* current node has no next node, or if the search for nextNode attempts
* to step upward from the TreeWalker's root node, returns
* <code>null</code> , and retains the current node.
*
* @return The new node, or <code>null</code> if the current node has no
* next node in the TreeWalker's logical view.
*/
public Node nextNode()
{
AxesWalker walker = m_lpi.getLastUsedWalker();
while(null != walker)
{
Node next = walker.getNextNode();
if(null != next)
{
if(null != walker.m_nextWalker)
{
walker = walker.m_nextWalker;
walker.setRoot(next);
m_lpi.setLastUsedWalker(walker);
}
else
return next;
}
else
{
walker = walker.m_prevWalker;
if(null != walker)
m_lpi.setLastUsedWalker(walker);
}
}
return null;
}
}
1.1
xml-xalan/java/src/org/apache/xpath/axes/ChildWalkerOneStep.java
Index: ChildWalkerOneStep.java
===================================================================
/*
* The Apache Software License, Version 1.1
*
*
* Copyright (c) 1999 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Xalan" and "Apache Software Foundation" must
* not be used to endorse or promote products derived from this
* software without prior written permission. For written
* permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache",
* nor may "Apache" appear in their name, without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation and was
* originally based on software copyright (c) 1999, Lotus
* Development Corporation., http://www.lotus.com. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
package org.apache.xpath.axes;
import org.w3c.dom.Node;
import org.w3c.dom.traversal.NodeFilter;
import org.apache.xpath.patterns.NodeTestFilter;
public class ChildWalkerOneStep extends AxesWalker
{
/**
* Construct an AxesWalker using a LocPathIterator.
*/
public ChildWalkerOneStep(LocPathIterator locPathIterator)
{
super(locPathIterator);
}
/**
* Tell what's the maximum level this axes can descend to.
*/
protected int getLevelMax()
{
return m_lpi.getDOMHelper().getLevel(m_root);
}
/**
* Set the analysis ID.
* @see org.apache.xpath.axes.WalkerFactory
*/
void setAnalysis(int a)
{
super.setAnalysis(a);
}
/**
* Get the next node in document order on the axes.
*/
public Node nextNode()
{
if(m_isFresh)
m_isFresh = false;
Node current = this.getCurrentNode();
if(current.supports("NodeTestFilter", "1.0"))
((NodeTestFilter)current).setNodeTest(this);
Node next;
if(m_root == m_currentNode)
next = m_currentNode.getFirstChild();
else
next = m_currentNode.getNextSibling();
if(null != next)
{
m_currentNode = next;
while(acceptNode(next) != NodeFilter.FILTER_ACCEPT)
{
next = next.getNextSibling();
if(null != next)
m_currentNode = next;
else
break;
}
}
if(null == next)
this.m_isDone = true;
return next;
}
}
1.1
xml-xalan/java/src/org/apache/xpath/axes/SelfWalkerOneStep.java
Index: SelfWalkerOneStep.java
===================================================================
/*
* The Apache Software License, Version 1.1
*
*
* Copyright (c) 1999 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Xalan" and "Apache Software Foundation" must
* not be used to endorse or promote products derived from this
* software without prior written permission. For written
* permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache",
* nor may "Apache" appear in their name, without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation and was
* originally based on software copyright (c) 1999, Lotus
* Development Corporation., http://www.lotus.com. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
package org.apache.xpath.axes;
import org.w3c.dom.Node;
import org.w3c.dom.traversal.NodeFilter;
/**
* <meta name="usage" content="internal"/>
* Class SelfWalkerOneStep
* <needs-description/>
*
* @author [EMAIL PROTECTED]
*/
public class SelfWalkerOneStep extends AxesWalker
{
/**
* Construct an AxesWalker using a LocPathIterator.
*
* @param locPathIterator
*/
public SelfWalkerOneStep(LocPathIterator locPathIterator)
{
super(locPathIterator);
}
/**
* Get the next node in document order on the axes.
*
* @return The self node or null.
*/
public Node nextNode()
{
if (m_isFresh)
{
m_isFresh = false;
if(acceptNode(m_root) == NodeFilter.FILTER_ACCEPT)
return m_root;
else
return null;
}
else
{
return null;
}
}
}
1.1
xml-xalan/java/src/org/apache/xpath/axes/WalkerFactory.java
Index: WalkerFactory.java
===================================================================
/*
* The Apache Software License, Version 1.1
*
*
* Copyright (c) 1999 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Xalan" and "Apache Software Foundation" must
* not be used to endorse or promote products derived from this
* software without prior written permission. For written
* permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache",
* nor may "Apache" appear in their name, without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation and was
* originally based on software copyright (c) 1999, Lotus
* Development Corporation., http://www.lotus.com. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
package org.apache.xpath.axes;
import org.apache.xpath.compiler.OpCodes;
import org.apache.xpath.compiler.Compiler;
import org.apache.xpath.patterns.NodeTest;
import org.w3c.dom.traversal.NodeFilter;
public class WalkerFactory
{
/**
* <meta name="usage" content="advanced"/>
* This method is for building an array of possible levels
* where the target element(s) could be found for a match.
* @param xpath The xpath that is executing.
* @param context The current source tree context node.
*/
static AxesWalker loadOneWalker(LocPathIterator lpi,
Compiler compiler, int stepOpCodePos)
throws org.xml.sax.SAXException
{
AxesWalker firstWalker = null;
int stepType = compiler.getOpMap()[stepOpCodePos];
if( stepType != OpCodes.ENDOP )
{
// m_axesWalkers = new AxesWalker[1];
// As we unwind from the recursion, create the iterators.
firstWalker = createDefaultWalker(compiler, stepType, lpi, 0);
firstWalker.init(compiler, stepOpCodePos, stepType);
}
return firstWalker;
}
/**
* <meta name="usage" content="advanced"/>
* This method is for building an array of possible levels
* where the target element(s) could be found for a match.
* @param xpath The xpath that is executing.
* @param context The current source tree context node.
*/
static AxesWalker loadWalkers(LocPathIterator lpi,
Compiler compiler, int stepOpCodePos,
int stepIndex)
throws org.xml.sax.SAXException
{
int stepType;
AxesWalker firstWalker = null;
AxesWalker walker, prevWalker = null;
int ops[] = compiler.getOpMap();
int analysis = analyze(compiler, stepOpCodePos, stepIndex);
while( OpCodes.ENDOP != (stepType = ops[stepOpCodePos]) )
{
walker = createDefaultWalker(compiler, stepOpCodePos, lpi, analysis);
walker.init(compiler, stepOpCodePos, stepType);
walker.setAnalysis(analysis);
if(null == firstWalker)
{
firstWalker = walker;
}
else
{
prevWalker.setNextWalker(walker);
walker.setPrevWalker(prevWalker);
}
prevWalker = walker;
stepOpCodePos = compiler.getNextStepPos(stepOpCodePos);
if(stepOpCodePos < 0)
break;
}
return firstWalker;
}
// There is no optimized walker that can handle
// this pattern, so use the default.
static final int NO_OPTIMIZE = 1;
// "."
static final int ONESTEP_SELF = 2;
// "*"
static final int ONESTEP_CHILDREN = 3;
// "foo"
static final int ONESTEP_ATTR = 4;
// "//foo"
static final int ONESTEP_DESCENDANTS = 5;
// "foo/baz/boo"
static final int MULTISTEP_CHILDREN = 6;
/**
* <meta name="usage" content="advanced"/>
*/
private static int analyze(Compiler compiler, int stepOpCodePos,
int stepIndex)
throws org.xml.sax.SAXException
{
int stepType;
int ops[] = compiler.getOpMap();
int stepCount = 0;
int analysisResult = NO_OPTIMIZE;
while( OpCodes.ENDOP != (stepType = ops[stepOpCodePos]) )
{
stepCount++;
int whatToShow = compiler.getWhatToShow(stepOpCodePos);
String namespace = compiler.getStepNS(stepOpCodePos);
// boolean isNSWild = (null != namespace)
// ? namespace.equals(NodeTest.WILD) : false;
String localname = compiler.getStepLocalName(stepOpCodePos);
boolean isWild = (null != localname) ? localname.equals(NodeTest.WILD)
: false;
int predAnalysis = analyzePredicate(compiler, stepOpCodePos, stepType);
switch(stepType)
{
case OpCodes.OP_VARIABLE:
case OpCodes.OP_EXTFUNCTION:
case OpCodes.OP_FUNCTION:
case OpCodes.OP_GROUP:
return NO_OPTIMIZE; // at least for now
case OpCodes.FROM_ROOT:
return NO_OPTIMIZE; // at least for now
case OpCodes.FROM_ANCESTORS:
return NO_OPTIMIZE; // at least for now
case OpCodes.FROM_ANCESTORS_OR_SELF:
return NO_OPTIMIZE; // at least for now
case OpCodes.FROM_ATTRIBUTES:
if(1 == stepCount)
{
analysisResult = ONESTEP_ATTR;
}
else
{
return NO_OPTIMIZE; // at least for now
}
break;
case OpCodes.FROM_NAMESPACE:
return NO_OPTIMIZE; // at least for now
case OpCodes.FROM_CHILDREN:
if(1 == stepCount)
{
analysisResult = ONESTEP_CHILDREN;
}
else
{
if((analysisResult == ONESTEP_CHILDREN) ||
(analysisResult == MULTISTEP_CHILDREN))
analysisResult = MULTISTEP_CHILDREN;
else
return NO_OPTIMIZE;
}
break;
case OpCodes.FROM_DESCENDANTS:
return NO_OPTIMIZE; // TODO
case OpCodes.FROM_DESCENDANTS_OR_SELF:
return NO_OPTIMIZE; // TODO
case OpCodes.FROM_FOLLOWING:
return NO_OPTIMIZE; // at least for now
case OpCodes.FROM_FOLLOWING_SIBLINGS:
return NO_OPTIMIZE; // at least for now
case OpCodes.FROM_PRECEDING:
return NO_OPTIMIZE; // at least for now
case OpCodes.FROM_PRECEDING_SIBLINGS:
return NO_OPTIMIZE; // at least for now
case OpCodes.FROM_PARENT:
return NO_OPTIMIZE; // at least for now
case OpCodes.FROM_SELF:
if(1 == stepCount)
analysisResult = ONESTEP_SELF;
else
return NO_OPTIMIZE; // at least for now
break;
case OpCodes.MATCH_ATTRIBUTE:
return NO_OPTIMIZE; // for now we shouldn't be dealing with match
patterns here.
case OpCodes.MATCH_ANY_ANCESTOR:
return NO_OPTIMIZE; // for now we shouldn't be dealing with match
patterns here.
case OpCodes.MATCH_IMMEDIATE_ANCESTOR:
return NO_OPTIMIZE; // for now we shouldn't be dealing with match
patterns here.
default:
throw new RuntimeException("Programmer's assertion: unknown opcode:
"+stepType);
}
stepOpCodePos = compiler.getNextStepPos(stepOpCodePos);
if(stepOpCodePos < 0)
break;
}
return analysisResult;
}
static final int HAS_PREDICATE = 1;
static final int HAS_NOPREDICATE = 2;
static final int HAS_BOOLEANPREDICATE = 3;
static final int MAYHAVE_INDEXPREDICATE = 4;
static int analyzePredicate(Compiler compiler, int opPos, int stepType)
throws org.xml.sax.SAXException
{
int argLen;
switch(stepType)
{
case OpCodes.OP_VARIABLE:
case OpCodes.OP_EXTFUNCTION:
case OpCodes.OP_FUNCTION:
case OpCodes.OP_GROUP:
argLen = compiler.getArgLength(opPos);
break;
default:
argLen = compiler.getArgLengthOfStep(opPos);
}
int pos = compiler.getFirstPredicateOpPos(opPos);
int nPredicates = compiler.countPredicates(pos);
return (nPredicates > 0) ? HAS_PREDICATE : HAS_NOPREDICATE;
}
/**
* Create the proper Walker from the axes type.
*/
private static AxesWalker createDefaultWalker(Compiler compiler,
int opPos,
LocPathIterator lpi,
int analysis)
{
AxesWalker ai;
int whatToShow = compiler.getWhatToShow(opPos);
int stepType = compiler.getOp(opPos);
boolean debug = false;
/*
System.out.println("0: "+compiler.getOp(opPos));
System.out.println("1: "+compiler.getOp(opPos+1));
System.out.println("2: "+compiler.getOp(opPos+2));
System.out.println("3: "+compiler.getOp(opPos+3));
System.out.println("4: "+compiler.getOp(opPos+4));
System.out.println("5: "+compiler.getOp(opPos+5));
*/
boolean simpleInit = false;
switch(stepType)
{
case OpCodes.OP_VARIABLE:
case OpCodes.OP_EXTFUNCTION:
case OpCodes.OP_FUNCTION:
case OpCodes.OP_GROUP:
ai = new FilterExprWalker(lpi);
simpleInit = true;
break;
case OpCodes.FROM_ROOT:
ai = new RootWalker(lpi);
simpleInit = true;
break;
case OpCodes.FROM_ANCESTORS:
ai = new AncestorWalker(lpi);
break;
case OpCodes.FROM_ANCESTORS_OR_SELF:
ai = new AncestorOrSelfWalker(lpi);
break;
case OpCodes.FROM_ATTRIBUTES:
switch(analysis)
{
case ONESTEP_ATTR:
ai = new AttributeWalkerOneStep(lpi);
break;
default:
ai = new AttributeWalker(lpi);
}
break;
case OpCodes.FROM_NAMESPACE:
ai = new NamespaceWalker(lpi);
break;
case OpCodes.FROM_CHILDREN:
switch(analysis)
{
case ONESTEP_CHILDREN:
{
if(debug)
System.out.println("analysis -- onestep child: "+analysis
+", "+compiler.toString());
ai = new ChildWalkerOneStep(lpi);
}
break;
case MULTISTEP_CHILDREN:
if(debug)
System.out.println("analysis -- multi-step child: "+analysis
+", "+compiler.toString());
ai = new ChildWalkerMultiStep(lpi);
break;
default:
ai = new ChildWalker(lpi);
}
break;
case OpCodes.FROM_DESCENDANTS:
ai = new DescendantWalker(lpi);
break;
case OpCodes.FROM_DESCENDANTS_OR_SELF:
ai = new DescendantOrSelfWalker(lpi);
break;
case OpCodes.FROM_FOLLOWING:
ai = new FollowingWalker(lpi);
break;
case OpCodes.FROM_FOLLOWING_SIBLINGS:
ai = new FollowingSiblingWalker(lpi);
break;
case OpCodes.FROM_PRECEDING:
ai = new PrecedingWalker(lpi);
break;
case OpCodes.FROM_PRECEDING_SIBLINGS:
ai = new PrecedingSiblingWalker(lpi);
break;
case OpCodes.FROM_PARENT:
ai = new ParentWalker(lpi);
break;
case OpCodes.FROM_SELF:
switch(analysis)
{
case ONESTEP_SELF:
ai = new SelfWalkerOneStep(lpi);
break;
default:
ai = new SelfWalker(lpi);
}
break;
case OpCodes.MATCH_ATTRIBUTE:
ai = new AttributeWalker(lpi);
break;
case OpCodes.MATCH_ANY_ANCESTOR:
ai = new ChildWalker(lpi);
break;
case OpCodes.MATCH_IMMEDIATE_ANCESTOR:
ai = new ChildWalker(lpi);
break;
default:
throw new RuntimeException("Programmer's assertion: unknown opcode:
"+stepType);
}
/*
System.out.print("construct: ");
NodeTest.debugWhatToShow(whatToShow);
System.out.println("or stuff: "+(whatToShow & (NodeFilter.SHOW_ATTRIBUTE
| NodeFilter.SHOW_ELEMENT
| NodeFilter.SHOW_PROCESSING_INSTRUCTION)));
*/
if((0 == (whatToShow & (NodeFilter.SHOW_ATTRIBUTE
| NodeFilter.SHOW_ELEMENT
| NodeFilter.SHOW_PROCESSING_INSTRUCTION))) ||
(whatToShow == NodeFilter.SHOW_ALL))
ai.initNodeTest(whatToShow);
else
{
ai.initNodeTest(whatToShow,
compiler.getStepNS(opPos),
compiler.getStepLocalName(opPos));
}
return ai;
}
}
