org.apache.xpath.axes
Class WalkerFactory

java.lang.Object
  extended byorg.apache.xpath.axes.WalkerFactory

public class WalkerFactory
extends Object

This class is both a factory for XPath location path expressions, which are built from the opcode map output, and an analysis engine for the location path expressions in order to provide optimization hints.


Field Summary
static int BIT_ANCESTOR
          Bit is on if any of the walkers contain an ancestor step.
static int BIT_ANCESTOR_OR_SELF
          Bit is on if any of the walkers contain an ancestor-or-self step.
static int BIT_ANY_DESCENDANT_FROM_ROOT
          Found "//foo" pattern
static int BIT_ATTRIBUTE
          Bit is on if any of the walkers contain an attribute step.
static int BIT_BACKWARDS_SELF
          Bit is on if any of the walkers can go backwards in document order from the context node.
static int BIT_CHILD
          Bit is on if any of the walkers contain a child step.
static int BIT_DESCENDANT
          Bit is on if any of the walkers contain a descendant step.
static int BIT_DESCENDANT_OR_SELF
          Bit is on if any of the walkers contain a descendant-or-self step.
static int BIT_FILTER
          Bit is on if any of the walkers contain a filter (i.e. id(), extension function, etc.) step.
static int BIT_FOLLOWING
          Bit is on if any of the walkers contain a following step.
static int BIT_FOLLOWING_SIBLING
          Bit is on if any of the walkers contain a following-sibiling step.
static int BIT_MATCH_PATTERN
          Bit is on if the expression is a match pattern.
static int BIT_NAMESPACE
          Bit is on if any of the walkers contain a namespace step.
static int BIT_NODETEST_ANY
          Bit is on if any of the walkers contain an node() test.
static int BIT_PARENT
          Bit is on if any of the walkers contain a parent step.
static int BIT_PRECEDING
          Bit is on if any of the walkers contain a preceding step.
static int BIT_PRECEDING_SIBLING
          Bit is on if any of the walkers contain a preceding-sibling step.
static int BIT_PREDICATE
          Bit is on if the expression contains a top-level predicate.
static int BIT_ROOT
          Bit is on if any of the walkers contain a root step.
static int BIT_SELF
          Bit is on if any of the walkers contain a self step.
static int BITMASK_TRAVERSES_OUTSIDE_SUBTREE
          If any of these bits are on, the expression may likely traverse outside the given subtree.
static int BITS_COUNT
          First 8 bits are the number of top-level location steps.
static int BITS_RESERVED
          4 bits are reserved for future use.
(package private) static boolean DEBUG_ITERATOR_CREATION
          Set to true for diagnostics about iterator creation
(package private) static boolean DEBUG_PATTERN_CREATION
          Set to true for diagnostics about walker creation
(package private) static boolean DEBUG_WALKER_CREATION
          Set to true for diagnostics about walker creation
 
Constructor Summary
WalkerFactory()
           
 
Method Summary
private static int analyze(Compiler compiler, int stepOpCodePos, int stepIndex)
          Analyze the location path and return 32 bits that give information about the location path as a whole.
(package private) static boolean analyzePredicate(Compiler compiler, int opPos, int stepType)
          Analyze a step and give information about it's predicates.
static boolean canCrissCross(int analysis)
           
static boolean canSkipSubtrees(int analysis)
           
private static StepPattern createDefaultStepPattern(Compiler compiler, int opPos, MatchPatternIterator mpi, int analysis, StepPattern tail, StepPattern head)
          Create a StepPattern that is contained within a LocationPath.
private static AxesWalker createDefaultWalker(Compiler compiler, int opPos, WalkingIterator lpi, int analysis)
          Create the proper Walker from the axes type.
static void diagnoseIterator(String name, int analysis, Compiler compiler)
           
(package private) static boolean functionProximateOrContainsProximate(Compiler compiler, int opPos)
           
static int getAnalysisBitFromAxes(int axis)
          Get a corresponding BIT_XXX from an axis.
static String getAnalysisString(int analysis)
           
static int getAxisFromStep(Compiler compiler, int stepOpCodePos)
          Special purpose function to see if we can optimize the pattern for a DescendantIterator.
static int getStepCount(int analysis)
           
static boolean hasPredicate(int analysis)
           
static boolean isAbsolute(int analysis)
           
static boolean isDownwardAxisOfMany(int axis)
          Tell if the given axis goes downword.
private static boolean isNaturalDocOrder(Compiler compiler, int stepOpCodePos, int stepIndex, int analysis)
          Tell if the pattern can be 'walked' with the iteration steps in natural document order, without duplicates.
static boolean isNaturalDocOrder(int analysis)
          Tell if the pattern can be 'walked' with the iteration steps in natural document order, without duplicates.
static boolean isOneStep(int analysis)
           
private static boolean isOptimizableForDescendantIterator(Compiler compiler, int stepOpCodePos, int stepIndex)
          Special purpose function to see if we can optimize the pattern for a DescendantIterator.
(package private) static boolean isProximateInnerExpr(Compiler compiler, int opPos)
           
static boolean isSet(int analysis, int bits)
           
static boolean isWild(int analysis)
           
(package private) static AxesWalker loadOneWalker(WalkingIterator lpi, Compiler compiler, int stepOpCodePos)
           This method is for building an array of possible levels where the target element(s) could be found for a match.
(package private) static StepPattern loadSteps(MatchPatternIterator mpi, Compiler compiler, int stepOpCodePos, int stepIndex)
          Read a LocationPath as a generalized match pattern.
(package private) static AxesWalker loadWalkers(WalkingIterator lpi, Compiler compiler, int stepOpCodePos, int stepIndex)
           This method is for building an array of possible levels where the target element(s) could be found for a match.
static boolean mightBeProximate(Compiler compiler, int opPos, int stepType)
          Tell if the predicates need to have proximity knowledge.
static DTMIterator newDTMIterator(Compiler compiler, int opPos, boolean isTopLevel)
          Create a new LocPathIterator iterator.
static boolean walksAncestors(int analysis)
           
static boolean walksAttributes(int analysis)
           
static boolean walksChildren(int analysis)
           
static boolean walksChildrenAndExtraAndSelfOnly(int analysis)
           
static boolean walksChildrenOnly(int analysis)
           
static boolean walksDescendants(int analysis)
           
static boolean walksDescendantsAndExtraAndSelfOnly(int analysis)
           
static boolean walksDownExtraOnly(int analysis)
           
static boolean walksDownOnly(int analysis)
           
static boolean walksExtraNodes(int analysis)
           
static boolean walksExtraNodesOnly(int analysis)
           
static boolean walksFilteredList(int analysis)
           
static boolean walksFollowingOnlyMaybeAbsolute(int analysis)
           
static boolean walksInDocOrder(int analysis)
           
static boolean walksNamespaces(int analysis)
           
static boolean walksSelfOnly(int analysis)
           
static boolean walksSideways(int analysis)
           
static boolean walksSubtree(int analysis)
           
static boolean walksSubtreeOnly(int analysis)
           
static boolean walksSubtreeOnlyFromRootOrContext(int analysis)
           
static boolean walksSubtreeOnlyMaybeAbsolute(int analysis)
           
static boolean walksUp(int analysis)
           
static boolean walksUpOnly(int analysis)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEBUG_PATTERN_CREATION

static final boolean DEBUG_PATTERN_CREATION
Set to true for diagnostics about walker creation

See Also:
Constant Field Values

DEBUG_WALKER_CREATION

static final boolean DEBUG_WALKER_CREATION
Set to true for diagnostics about walker creation

See Also:
Constant Field Values

DEBUG_ITERATOR_CREATION

static final boolean DEBUG_ITERATOR_CREATION
Set to true for diagnostics about iterator creation

See Also:
Constant Field Values

BITS_COUNT

public static final int BITS_COUNT
First 8 bits are the number of top-level location steps. Hopefully there will never be more that 255 location steps!!!

See Also:
Constant Field Values

BITS_RESERVED

public static final int BITS_RESERVED
4 bits are reserved for future use.

See Also:
Constant Field Values

BIT_PREDICATE

public static final int BIT_PREDICATE
Bit is on if the expression contains a top-level predicate.

See Also:
Constant Field Values

BIT_ANCESTOR

public static final int BIT_ANCESTOR
Bit is on if any of the walkers contain an ancestor step.

See Also:
Constant Field Values

BIT_ANCESTOR_OR_SELF

public static final int BIT_ANCESTOR_OR_SELF
Bit is on if any of the walkers contain an ancestor-or-self step.

See Also:
Constant Field Values

BIT_ATTRIBUTE

public static final int BIT_ATTRIBUTE
Bit is on if any of the walkers contain an attribute step.

See Also:
Constant Field Values

BIT_CHILD

public static final int BIT_CHILD
Bit is on if any of the walkers contain a child step.

See Also:
Constant Field Values

BIT_DESCENDANT

public static final int BIT_DESCENDANT
Bit is on if any of the walkers contain a descendant step.

See Also:
Constant Field Values

BIT_DESCENDANT_OR_SELF

public static final int BIT_DESCENDANT_OR_SELF
Bit is on if any of the walkers contain a descendant-or-self step.

See Also:
Constant Field Values

BIT_FOLLOWING

public static final int BIT_FOLLOWING
Bit is on if any of the walkers contain a following step.

See Also:
Constant Field Values

BIT_FOLLOWING_SIBLING

public static final int BIT_FOLLOWING_SIBLING
Bit is on if any of the walkers contain a following-sibiling step.

See Also:
Constant Field Values

BIT_NAMESPACE

public static final int BIT_NAMESPACE
Bit is on if any of the walkers contain a namespace step.

See Also:
Constant Field Values

BIT_PARENT

public static final int BIT_PARENT
Bit is on if any of the walkers contain a parent step.

See Also:
Constant Field Values

BIT_PRECEDING

public static final int BIT_PRECEDING
Bit is on if any of the walkers contain a preceding step.

See Also:
Constant Field Values

BIT_PRECEDING_SIBLING

public static final int BIT_PRECEDING_SIBLING
Bit is on if any of the walkers contain a preceding-sibling step.

See Also:
Constant Field Values

BIT_SELF

public static final int BIT_SELF
Bit is on if any of the walkers contain a self step.

See Also:
Constant Field Values

BIT_FILTER

public static final int BIT_FILTER
Bit is on if any of the walkers contain a filter (i.e. id(), extension function, etc.) step.

See Also:
Constant Field Values

BIT_ROOT

public static final int BIT_ROOT
Bit is on if any of the walkers contain a root step.

See Also:
Constant Field Values

BITMASK_TRAVERSES_OUTSIDE_SUBTREE

public static final int BITMASK_TRAVERSES_OUTSIDE_SUBTREE
If any of these bits are on, the expression may likely traverse outside the given subtree.

See Also:
Constant Field Values

BIT_BACKWARDS_SELF

public static final int BIT_BACKWARDS_SELF
Bit is on if any of the walkers can go backwards in document order from the context node.

See Also:
Constant Field Values

BIT_ANY_DESCENDANT_FROM_ROOT

public static final int BIT_ANY_DESCENDANT_FROM_ROOT
Found "//foo" pattern

See Also:
Constant Field Values

BIT_NODETEST_ANY

public static final int BIT_NODETEST_ANY
Bit is on if any of the walkers contain an node() test. This is really only useful if the count is 1.

See Also:
Constant Field Values

BIT_MATCH_PATTERN

public static final int BIT_MATCH_PATTERN
Bit is on if the expression is a match pattern.

See Also:
Constant Field Values
Constructor Detail

WalkerFactory

public WalkerFactory()
Method Detail

loadOneWalker

static AxesWalker loadOneWalker(WalkingIterator lpi,
                                Compiler compiler,
                                int stepOpCodePos)
                         throws javax.xml.transform.TransformerException
This method is for building an array of possible levels where the target element(s) could be found for a match.

Parameters:
lpi - The owning location path iterator.
compiler - non-null reference to compiler object that has processed the XPath operations into an opcode map.
stepOpCodePos - The opcode position for the step.
Returns:
non-null AxesWalker derivative.
Throws:
javax.xml.transform.TransformerException

loadWalkers

static AxesWalker loadWalkers(WalkingIterator lpi,
                              Compiler compiler,
                              int stepOpCodePos,
                              int stepIndex)
                       throws javax.xml.transform.TransformerException
This method is for building an array of possible levels where the target element(s) could be found for a match.

Parameters:
lpi - The owning location path iterator object.
compiler - non-null reference to compiler object that has processed the XPath operations into an opcode map.
stepOpCodePos - The opcode position for the step.
stepIndex - The top-level step index withing the iterator.
Returns:
non-null AxesWalker derivative.
Throws:
javax.xml.transform.TransformerException

isSet

public static boolean isSet(int analysis,
                            int bits)

diagnoseIterator

public static void diagnoseIterator(String name,
                                    int analysis,
                                    Compiler compiler)

newDTMIterator

public static DTMIterator newDTMIterator(Compiler compiler,
                                         int opPos,
                                         boolean isTopLevel)
                                  throws javax.xml.transform.TransformerException
Create a new LocPathIterator iterator. The exact type of iterator returned is based on an analysis of the XPath operations.

Parameters:
compiler - non-null reference to compiler object that has processed the XPath operations into an opcode map.
opPos - The position of the operation code for this itterator.
Returns:
non-null reference to a LocPathIterator or derivative.
Throws:
javax.xml.transform.TransformerException

getAxisFromStep

public static int getAxisFromStep(Compiler compiler,
                                  int stepOpCodePos)
                           throws javax.xml.transform.TransformerException
Special purpose function to see if we can optimize the pattern for a DescendantIterator.

Parameters:
compiler - non-null reference to compiler object that has processed the XPath operations into an opcode map.
stepOpCodePos - The opcode position for the step.
Returns:
32 bits as an integer that give information about the location path as a whole.
Throws:
javax.xml.transform.TransformerException

getAnalysisBitFromAxes

public static int getAnalysisBitFromAxes(int axis)
Get a corresponding BIT_XXX from an axis.

Parameters:
axis - One of Axis.ANCESTOR, etc.
Returns:
One of BIT_ANCESTOR, etc.

functionProximateOrContainsProximate

static boolean functionProximateOrContainsProximate(Compiler compiler,
                                                    int opPos)

isProximateInnerExpr

static boolean isProximateInnerExpr(Compiler compiler,
                                    int opPos)

mightBeProximate

public static boolean mightBeProximate(Compiler compiler,
                                       int opPos,
                                       int stepType)
                                throws javax.xml.transform.TransformerException
Tell if the predicates need to have proximity knowledge.

Throws:
javax.xml.transform.TransformerException

isOptimizableForDescendantIterator

private static boolean isOptimizableForDescendantIterator(Compiler compiler,
                                                          int stepOpCodePos,
                                                          int stepIndex)
                                                   throws javax.xml.transform.TransformerException
Special purpose function to see if we can optimize the pattern for a DescendantIterator.

Parameters:
compiler - non-null reference to compiler object that has processed the XPath operations into an opcode map.
stepOpCodePos - The opcode position for the step.
stepIndex - The top-level step index withing the iterator.
Returns:
32 bits as an integer that give information about the location path as a whole.
Throws:
javax.xml.transform.TransformerException

analyze

private static int analyze(Compiler compiler,
                           int stepOpCodePos,
                           int stepIndex)
                    throws javax.xml.transform.TransformerException
Analyze the location path and return 32 bits that give information about the location path as a whole. See the BIT_XXX constants for meaning about each of the bits.

Parameters:
compiler - non-null reference to compiler object that has processed the XPath operations into an opcode map.
stepOpCodePos - The opcode position for the step.
stepIndex - The top-level step index withing the iterator.
Returns:
32 bits as an integer that give information about the location path as a whole.
Throws:
javax.xml.transform.TransformerException

isDownwardAxisOfMany

public static boolean isDownwardAxisOfMany(int axis)
Tell if the given axis goes downword. Bogus name, if you can think of a better one, please do tell. This really has to do with inverting attribute axis.

Parameters:
axis - One of Axis.XXX.
Returns:
true if the axis is not a child axis and does not go up from the axis root.

loadSteps

static StepPattern loadSteps(MatchPatternIterator mpi,
                             Compiler compiler,
                             int stepOpCodePos,
                             int stepIndex)
                      throws javax.xml.transform.TransformerException
Read a LocationPath as a generalized match pattern. What this means is that the LocationPath is read backwards, as a test on a given node, to see if it matches the criteria of the selection, and ends up at the context node. Essentially, this is a backwards query from a given node, to find the context node.

So, the selection "foo/daz[2]" is, in non-abreviated expanded syntax, "self::node()/following-sibling::foo/child::daz[position()=2]". Taking this as a match pattern for a probable node, it works out to "self::daz/parent::foo[child::daz[position()=2 and isPrevStepNode()] precedingSibling::node()[isContextNodeOfLocationPath()]", adding magic isPrevStepNode and isContextNodeOfLocationPath operations. Predicates in the location path have to be executed by the following step, because they have to know the context of their execution.

Parameters:
mpi - The MatchPatternIterator to which the steps will be attached.
compiler - The compiler that holds the syntax tree/op map to construct from.
stepOpCodePos - The current op code position within the opmap.
stepIndex - The top-level step index withing the iterator.
Returns:
A StepPattern object, which may contain relative StepPatterns.
Throws:
javax.xml.transform.TransformerException

createDefaultStepPattern

private static StepPattern createDefaultStepPattern(Compiler compiler,
                                                    int opPos,
                                                    MatchPatternIterator mpi,
                                                    int analysis,
                                                    StepPattern tail,
                                                    StepPattern head)
                                             throws javax.xml.transform.TransformerException
Create a StepPattern that is contained within a LocationPath.

Parameters:
compiler - The compiler that holds the syntax tree/op map to construct from.
mpi - The MatchPatternIterator to which the steps will be attached.
analysis - 32 bits of analysis, from which the type of AxesWalker may be influenced.
tail - The step that is the first step analyzed, but the last step in the relative match linked list, i.e. the tail. May be null.
head - The step that is the current head of the relative match step linked list. May be null.
Returns:
the head of the list.
Throws:
javax.xml.transform.TransformerException

analyzePredicate

static boolean analyzePredicate(Compiler compiler,
                                int opPos,
                                int stepType)
                         throws javax.xml.transform.TransformerException
Analyze a step and give information about it's predicates. Right now this just returns true or false if the step has a predicate.

Parameters:
compiler - non-null reference to compiler object that has processed the XPath operations into an opcode map.
opPos - The opcode position for the step.
stepType - The type of step, one of OP_GROUP, etc.
Returns:
true if step has a predicate.
Throws:
javax.xml.transform.TransformerException

createDefaultWalker

private static AxesWalker createDefaultWalker(Compiler compiler,
                                              int opPos,
                                              WalkingIterator lpi,
                                              int analysis)
Create the proper Walker from the axes type.

Parameters:
compiler - non-null reference to compiler object that has processed the XPath operations into an opcode map.
opPos - The opcode position for the step.
lpi - The owning location path iterator.
analysis - 32 bits of analysis, from which the type of AxesWalker may be influenced.
Returns:
non-null reference to AxesWalker derivative.
Throws:
RuntimeException - if the input is bad.

getAnalysisString

public static String getAnalysisString(int analysis)

hasPredicate

public static boolean hasPredicate(int analysis)

isWild

public static boolean isWild(int analysis)

walksAncestors

public static boolean walksAncestors(int analysis)

walksAttributes

public static boolean walksAttributes(int analysis)

walksNamespaces

public static boolean walksNamespaces(int analysis)

walksChildren

public static boolean walksChildren(int analysis)

walksDescendants

public static boolean walksDescendants(int analysis)

walksSubtree

public static boolean walksSubtree(int analysis)

walksSubtreeOnlyMaybeAbsolute

public static boolean walksSubtreeOnlyMaybeAbsolute(int analysis)

walksSubtreeOnly

public static boolean walksSubtreeOnly(int analysis)

walksFilteredList

public static boolean walksFilteredList(int analysis)

walksSubtreeOnlyFromRootOrContext

public static boolean walksSubtreeOnlyFromRootOrContext(int analysis)

walksInDocOrder

public static boolean walksInDocOrder(int analysis)

walksFollowingOnlyMaybeAbsolute

public static boolean walksFollowingOnlyMaybeAbsolute(int analysis)

walksUp

public static boolean walksUp(int analysis)

walksSideways

public static boolean walksSideways(int analysis)

walksExtraNodes

public static boolean walksExtraNodes(int analysis)

walksExtraNodesOnly

public static boolean walksExtraNodesOnly(int analysis)

isAbsolute

public static boolean isAbsolute(int analysis)

walksChildrenOnly

public static boolean walksChildrenOnly(int analysis)

walksChildrenAndExtraAndSelfOnly

public static boolean walksChildrenAndExtraAndSelfOnly(int analysis)

walksDescendantsAndExtraAndSelfOnly

public static boolean walksDescendantsAndExtraAndSelfOnly(int analysis)

walksSelfOnly

public static boolean walksSelfOnly(int analysis)

walksUpOnly

public static boolean walksUpOnly(int analysis)

walksDownOnly

public static boolean walksDownOnly(int analysis)

walksDownExtraOnly

public static boolean walksDownExtraOnly(int analysis)

canSkipSubtrees

public static boolean canSkipSubtrees(int analysis)

canCrissCross

public static boolean canCrissCross(int analysis)

isNaturalDocOrder

public static boolean isNaturalDocOrder(int analysis)
Tell if the pattern can be 'walked' with the iteration steps in natural document order, without duplicates.

Parameters:
analysis - The general analysis of the pattern.
Returns:
true if the walk can be done in natural order.
Throws:
javax.xml.transform.TransformerException

isNaturalDocOrder

private static boolean isNaturalDocOrder(Compiler compiler,
                                         int stepOpCodePos,
                                         int stepIndex,
                                         int analysis)
                                  throws javax.xml.transform.TransformerException
Tell if the pattern can be 'walked' with the iteration steps in natural document order, without duplicates.

Parameters:
compiler - non-null reference to compiler object that has processed the XPath operations into an opcode map.
stepOpCodePos - The opcode position for the step.
stepIndex - The top-level step index withing the iterator.
analysis - The general analysis of the pattern.
Returns:
true if the walk can be done in natural order.
Throws:
javax.xml.transform.TransformerException

isOneStep

public static boolean isOneStep(int analysis)

getStepCount

public static int getStepCount(int analysis)