org.apache.xalan.templates
Class RedundentExprEliminator

java.lang.Object
  org.apache.xpath.XPathVisitor
      org.apache.xalan.templates.XSLTVisitor
          org.apache.xalan.templates.RedundentExprEliminator

public class RedundentExprEliminator
extends XSLTVisitor

This class eleminates redundent XPaths from a given subtree, and also collects all absolute paths within the subtree. First it must be called as a visitor to the subtree, and then eleminateRedundent must be called.

Nested Class Summary

(package private) class

RedundentExprEliminator.MultistepExprHolder Since we want to sort multistep expressions by length, use a linked list with elements of type MultistepExprHolder.

Field Summary

static boolean	DEBUG
static boolean	DIAGNOSE_MULTISTEPLIST
static boolean	DIAGNOSE_NUM_PATHS_REDUCED
(package private) AbsPathChecker	m_absPathChecker
(package private) java.util.Vector	m_absPaths
(package private) boolean	m_isSameContext
(package private) java.util.Vector	m_paths
private static int	m_uniquePseudoVarID
(package private) VarNameCollector	m_varNameCollector So we can reuse it over and over again.
(package private) static java.lang.String	PSUEDOVARNAMESPACE

Constructor Summary

RedundentExprEliminator()
Construct a RedundentExprEliminator.

Method Summary

protected ElemVariable	addVarDeclToElem(ElemTemplateElement psuedoVarRecipient, LocPathIterator lpi, ElemVariable psuedoVar) Add the given variable to the psuedoVarRecipient.
protected static void	assertion(boolean b, java.lang.String msg) Simple assertion.
private void	assertIsLocPathIterator(Expression expr1, ExpressionOwner eo) Assert that the expression is a LocPathIterator, and, if not, try to give some diagnostic info.
protected LocPathIterator	changePartToRef(QName uniquePseudoVarName, WalkingIterator wi, int numSteps, boolean isGlobal) Change a given number of steps to a single variable reference.
protected void	changeToVarRef(QName varName, ExpressionOwner owner, java.util.Vector paths, ElemTemplateElement psuedoVarRecipient) Change the expression owned by the owner argument to a variable reference of the given name.
protected int	countAncestors(ElemTemplateElement elem) Count the number of ancestors that a ElemTemplateElement has.
protected int	countSteps(LocPathIterator lpi) Count the steps in a given location path.
protected ElemVariable	createGlobalPseudoVarDecl(QName uniquePseudoVarName, StylesheetRoot stylesheetRoot, LocPathIterator lpi) Create a psuedo variable reference that will represent the shared redundent XPath, for a local reduction.
protected WalkingIterator	createIteratorFromSteps(WalkingIterator wi, int numSteps) Create a new WalkingIterator from the steps in another WalkingIterator.
protected ElemVariable	createLocalPseudoVarDecl(QName uniquePseudoVarName, ElemTemplateElement psuedoVarRecipient, LocPathIterator lpi) Create a psuedo variable reference that will represent the shared redundent XPath, for a local reduction.
protected RedundentExprEliminator.MultistepExprHolder	createMultistepExprList(java.util.Vector paths) For the reduction of location path parts, create a list of all the multistep paths with more than one step, sorted by the number of steps, with the most steps occuring earlier in the list.
protected ElemVariable	createPseudoVarDecl(ElemTemplateElement psuedoVarRecipient, LocPathIterator lpi, boolean isGlobal) Create a psuedo variable reference that will represent the shared redundent XPath, and add it to the stylesheet.
protected void	diagnoseLineNumber(Expression expr) Tell what line number belongs to a given expression.
protected void	diagnoseMultistepList(int matchCount, int lengthToTest, boolean isGlobal) Print out diagnostics about partial multistep evaluation.
protected void	diagnoseNumPaths(java.util.Vector paths, int numPathsEliminated, int numUniquePathsEliminated) Print out to std err the number of paths reduced.
protected void	eleminateRedundent(ElemTemplateElement psuedoVarRecipient, java.util.Vector paths) Method to be called after the all expressions within an node context have been visited.
void	eleminateRedundentGlobals(StylesheetRoot stylesheet) Method to be called after the all global expressions within a stylesheet have been collected.
void	eleminateRedundentLocals(ElemTemplateElement psuedoVarRecipient) Method to be called after the all expressions within an node context have been visited.
protected void	eleminateSharedPartialPaths(ElemTemplateElement psuedoVarRecipient, java.util.Vector paths) Eliminate the shared partial paths in the expression list.
protected int	findAndEliminateRedundant(int start, int firstOccuranceIndex, ExpressionOwner firstOccuranceOwner, ElemTemplateElement psuedoVarRecipient, java.util.Vector paths) Look through the vector from start point, looking for redundant occurances.
protected ElemTemplateElement	findCommonAncestor(RedundentExprEliminator.MultistepExprHolder head) Given a linked list of expressions, find the common ancestor that is suitable for holding a psuedo variable for shared access.
protected ElemTemplateElement	getElemFromExpression(Expression expr) From an XPath expression component, get the ElemTemplateElement owner.
protected ElemTemplateElement	getPrevElementWithinContext(ElemTemplateElement elem) Get the previous sibling or parent of the given template, stopping at xsl:for-each, xsl:template, or xsl:stylesheet.
protected ElemVariable	getPrevVariableElem(ElemTemplateElement elem) Find the previous occurance of a xsl:variable.
private static int	getPseudoVarID()
boolean	isAbsolute(LocPathIterator path) Tell if the given LocPathIterator is relative to an absolute path, i.e.
protected boolean	isNotSameAsOwner(RedundentExprEliminator.MultistepExprHolder head, ElemTemplateElement ete) Find out if the given ElemTemplateElement is not the same as one of the ElemTemplateElement owners of the expressions.
protected boolean	isParam(ExpressionNode expr) Tell if the expr param is contained within an xsl:param.
protected RedundentExprEliminator.MultistepExprHolder	matchAndEliminatePartialPaths(RedundentExprEliminator.MultistepExprHolder testee, RedundentExprEliminator.MultistepExprHolder head, boolean isGlobal, int lengthToTest, ElemTemplateElement varScope) For a given path, see if there are any partitial matches in the list, and, if there are, replace those partial paths with psuedo variable refs, and create the psuedo variable decl.
protected int	oldFindAndEliminateRedundant(int start, int firstOccuranceIndex, ExpressionOwner firstOccuranceOwner, ElemTemplateElement psuedoVarRecipient, java.util.Vector paths) To be removed.
(package private) boolean	partialIsVariable(RedundentExprEliminator.MultistepExprHolder testee, int lengthToTest) Check if results of partial reduction will just be a variable, in which case, skip it.
protected boolean	stepsEqual(WalkingIterator iter1, WalkingIterator iter2, int numSteps) Compare a given number of steps between two iterators, to see if they are equal.
private static void	validateNewAddition(java.util.Vector paths, ExpressionOwner owner, LocPathIterator path) Validate some assumptions about the new LocPathIterator and it's owner and the state of the list.
boolean	visitInstruction(ElemTemplateElement elem) Visit an XSLT instruction.
boolean	visitLocationPath(ExpressionOwner owner, LocPathIterator path) Visit a LocationPath.
boolean	visitPredicate(ExpressionOwner owner, Expression pred) Visit a predicate within a location path.
boolean	visitTopLevelInstruction(ElemTemplateElement elem) Visit an XSLT top-level instruction.

Methods inherited from class org.apache.xalan.templates.XSLTVisitor

visitAVT, visitExtensionElement, visitLiteralResultElement, visitStylesheet, visitTopLevelVariableOrParamDecl, visitVariableOrParamDecl

Methods inherited from class org.apache.xpath.XPathVisitor

visitBinaryOperation, visitFunction, visitMatchPattern, visitNumberLiteral, visitStep, visitStringLiteral, visitUnaryOperation, visitUnionPath, visitUnionPattern, visitVariableRef

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

m_paths

java.util.Vector m_paths

m_absPaths

java.util.Vector m_absPaths

m_isSameContext

boolean m_isSameContext

m_absPathChecker

AbsPathChecker m_absPathChecker

m_uniquePseudoVarID

private static int m_uniquePseudoVarID

PSUEDOVARNAMESPACE

static final java.lang.String PSUEDOVARNAMESPACE

See Also:

Constant Field Values

DEBUG

public static final boolean DEBUG

See Also:

Constant Field Values

DIAGNOSE_NUM_PATHS_REDUCED

public static final boolean DIAGNOSE_NUM_PATHS_REDUCED

See Also:

Constant Field Values

DIAGNOSE_MULTISTEPLIST

public static final boolean DIAGNOSE_MULTISTEPLIST

See Also:

Constant Field Values

m_varNameCollector

VarNameCollector m_varNameCollector

So we can reuse it over and over again.

Constructor Detail

RedundentExprEliminator

public RedundentExprEliminator()

Construct a RedundentExprEliminator.

Method Detail

eleminateRedundentLocals

public void eleminateRedundentLocals(ElemTemplateElement psuedoVarRecipient)

Method to be called after the all expressions within an node context have been visited. It eliminates redundent expressions by creating a variable in the psuedoVarRecipient for each redundent expression, and then rewriting the redundent expression to be a variable reference.

Parameters:

psuedoVarRecipient - The recipient of the psuedo vars. The variables will be inserted as first children of the element, before any existing variables.

eleminateRedundentGlobals

public void eleminateRedundentGlobals(StylesheetRoot stylesheet)

Method to be called after the all global expressions within a stylesheet have been collected. It eliminates redundent expressions by creating a variable in the psuedoVarRecipient for each redundent expression, and then rewriting the redundent expression to be a variable reference.

eleminateRedundent

protected void eleminateRedundent(ElemTemplateElement psuedoVarRecipient,
                                  java.util.Vector paths)

Method to be called after the all expressions within an node context have been visited. It eliminates redundent expressions by creating a variable in the psuedoVarRecipient for each redundent expression, and then rewriting the redundent expression to be a variable reference.

Parameters:

psuedoVarRecipient - The owner of the subtree from where the paths were collected.

paths - A vector of paths that hold ExpressionOwner objects, which must yield LocationPathIterators.

eleminateSharedPartialPaths

protected void eleminateSharedPartialPaths(ElemTemplateElement psuedoVarRecipient,
                                           java.util.Vector paths)

Eliminate the shared partial paths in the expression list.

Parameters:

psuedoVarRecipient - The recipient of the psuedo vars.

paths - A vector of paths that hold ExpressionOwner objects, which must yield LocationPathIterators.

matchAndEliminatePartialPaths

protected RedundentExprEliminator.MultistepExprHolder matchAndEliminatePartialPaths(RedundentExprEliminator.MultistepExprHolder testee,
                                                                                    RedundentExprEliminator.MultistepExprHolder head,
                                                                                    boolean isGlobal,
                                                                                    int lengthToTest,
                                                                                    ElemTemplateElement varScope)

For a given path, see if there are any partitial matches in the list, and, if there are, replace those partial paths with psuedo variable refs, and create the psuedo variable decl.

Returns:

The head of the list, which may have changed.

partialIsVariable

boolean partialIsVariable(RedundentExprEliminator.MultistepExprHolder testee,
                          int lengthToTest)

Check if results of partial reduction will just be a variable, in which case, skip it.

diagnoseLineNumber

protected void diagnoseLineNumber(Expression expr)

Tell what line number belongs to a given expression.

findCommonAncestor

protected ElemTemplateElement findCommonAncestor(RedundentExprEliminator.MultistepExprHolder head)

Given a linked list of expressions, find the common ancestor that is suitable for holding a psuedo variable for shared access.

isNotSameAsOwner

protected boolean isNotSameAsOwner(RedundentExprEliminator.MultistepExprHolder head,
                                   ElemTemplateElement ete)

Find out if the given ElemTemplateElement is not the same as one of the ElemTemplateElement owners of the expressions.

Parameters:

head - Head of linked list of expression owners.

ete - The ElemTemplateElement that is a candidate for a psuedo variable parent.

Returns:

true if the given ElemTemplateElement is not the same as one of the ElemTemplateElement owners of the expressions. This is to make sure we find an ElemTemplateElement that is in a viable position to hold psuedo variables that are visible to the references.

countAncestors

protected int countAncestors(ElemTemplateElement elem)

Count the number of ancestors that a ElemTemplateElement has.

Parameters:

elem - An representation of an element in an XSLT stylesheet.

Returns:

The number of ancestors of elem (including the element itself).

diagnoseMultistepList

protected void diagnoseMultistepList(int matchCount,
                                     int lengthToTest,
                                     boolean isGlobal)

Print out diagnostics about partial multistep evaluation.

changePartToRef

protected LocPathIterator changePartToRef(QName uniquePseudoVarName,
                                          WalkingIterator wi,
                                          int numSteps,
                                          boolean isGlobal)

Change a given number of steps to a single variable reference.

Parameters:

uniquePseudoVarName - The name of the variable reference.

wi - The walking iterator that is to be changed.

numSteps - The number of steps to be changed.

isGlobal - true if this will be a global reference.

createIteratorFromSteps

protected WalkingIterator createIteratorFromSteps(WalkingIterator wi,
                                                  int numSteps)

Create a new WalkingIterator from the steps in another WalkingIterator.

Parameters:

wi - The iterator from where the steps will be taken.

numSteps - The number of steps from the first to copy into the new iterator.

Returns:

The new iterator.

stepsEqual

protected boolean stepsEqual(WalkingIterator iter1,
                             WalkingIterator iter2,
                             int numSteps)

Compare a given number of steps between two iterators, to see if they are equal.

Parameters:

iter1 - The first iterator to compare.

iter2 - The second iterator to compare.

numSteps - The number of steps to compare.

Returns:

true If the given number of steps are equal.

createMultistepExprList

protected RedundentExprEliminator.MultistepExprHolder createMultistepExprList(java.util.Vector paths)

For the reduction of location path parts, create a list of all the multistep paths with more than one step, sorted by the number of steps, with the most steps occuring earlier in the list. If the list is only one member, don't bother returning it.

Parameters:

paths - Vector of ExpressionOwner objects, which may contain null entries. The ExpressionOwner objects must own LocPathIterator objects.

Returns:

null if no multipart paths are found or the list is only of length 1, otherwise the first MultistepExprHolder in a linked list of these objects.

findAndEliminateRedundant

protected int findAndEliminateRedundant(int start,
                                        int firstOccuranceIndex,
                                        ExpressionOwner firstOccuranceOwner,
                                        ElemTemplateElement psuedoVarRecipient,
                                        java.util.Vector paths)
                                 throws org.w3c.dom.DOMException

Look through the vector from start point, looking for redundant occurances. When one or more are found, create a psuedo variable declaration, insert it into the stylesheet, and replace the occurance with a reference to the psuedo variable. When a redundent variable is found, it's slot in the vector will be replaced by null.

Parameters:

start - The position to start looking in the vector.

firstOccuranceIndex - The position of firstOccuranceOwner.

firstOccuranceOwner - The owner of the expression we are looking for.

psuedoVarRecipient - Where to put the psuedo variables.

Returns:

The number of expression occurances that were modified.

Throws:

org.w3c.dom.DOMException

oldFindAndEliminateRedundant

protected int oldFindAndEliminateRedundant(int start,
                                           int firstOccuranceIndex,
                                           ExpressionOwner firstOccuranceOwner,
                                           ElemTemplateElement psuedoVarRecipient,
                                           java.util.Vector paths)
                                    throws org.w3c.dom.DOMException

To be removed.

Throws:

org.w3c.dom.DOMException

countSteps

protected int countSteps(LocPathIterator lpi)

Count the steps in a given location path.

Parameters:

lpi - The location path iterator that owns the steps.

Returns:

The number of steps in the given location path.

changeToVarRef

protected void changeToVarRef(QName varName,
                              ExpressionOwner owner,
                              java.util.Vector paths,
                              ElemTemplateElement psuedoVarRecipient)

Change the expression owned by the owner argument to a variable reference of the given name. Warning: For global vars, this function relies on the variable declaration to which it refers having been added just prior to this function being called, so that the reference index can be determined from the size of the global variables list minus one.

Parameters:

varName - The name of the variable which will be referenced.

owner - The owner of the expression which will be replaced by a variable ref.

paths - The paths list that the iterator came from, mainly to determine if this is a local or global reduction.

psuedoVarRecipient - The element within whose scope the variable is being inserted, possibly a StylesheetRoot.

getPseudoVarID

private static int getPseudoVarID()

createPseudoVarDecl

protected ElemVariable createPseudoVarDecl(ElemTemplateElement psuedoVarRecipient,
                                           LocPathIterator lpi,
                                           boolean isGlobal)
                                    throws org.w3c.dom.DOMException

Create a psuedo variable reference that will represent the shared redundent XPath, and add it to the stylesheet.

Parameters:

psuedoVarRecipient - The broadest scope of where the variable should be inserted, usually an xsl:template or xsl:for-each.

lpi - The LocationPathIterator that the variable should represent.

isGlobal - true if the paths are global.

Returns:

The new psuedo var element.

Throws:

org.w3c.dom.DOMException

createGlobalPseudoVarDecl

protected ElemVariable createGlobalPseudoVarDecl(QName uniquePseudoVarName,
                                                 StylesheetRoot stylesheetRoot,
                                                 LocPathIterator lpi)
                                          throws org.w3c.dom.DOMException

Create a psuedo variable reference that will represent the shared redundent XPath, for a local reduction.

Parameters:

uniquePseudoVarName - The name of the new variable.

stylesheetRoot - The broadest scope of where the variable should be inserted, which must be a StylesheetRoot element in this case.

lpi - The LocationPathIterator that the variable should represent.

Returns:

null if the decl was not created, otherwise the new Pseudo var element.

Throws:

org.w3c.dom.DOMException

createLocalPseudoVarDecl

protected ElemVariable createLocalPseudoVarDecl(QName uniquePseudoVarName,
                                                ElemTemplateElement psuedoVarRecipient,
                                                LocPathIterator lpi)
                                         throws org.w3c.dom.DOMException

Create a psuedo variable reference that will represent the shared redundent XPath, for a local reduction.

Parameters:

uniquePseudoVarName - The name of the new variable.

psuedoVarRecipient - The broadest scope of where the variable should be inserted, usually an xsl:template or xsl:for-each.

lpi - The LocationPathIterator that the variable should represent.

Returns:

null if the decl was not created, otherwise the new Pseudo var element.

Throws:

org.w3c.dom.DOMException

addVarDeclToElem

protected ElemVariable addVarDeclToElem(ElemTemplateElement psuedoVarRecipient,
                                        LocPathIterator lpi,
                                        ElemVariable psuedoVar)
                                 throws org.w3c.dom.DOMException

Add the given variable to the psuedoVarRecipient.

Throws:

org.w3c.dom.DOMException

isParam

protected boolean isParam(ExpressionNode expr)

Tell if the expr param is contained within an xsl:param.

getPrevVariableElem

protected ElemVariable getPrevVariableElem(ElemTemplateElement elem)

Find the previous occurance of a xsl:variable. Stop the search when a xsl:for-each, xsl:template, or xsl:stylesheet is encountered.

Parameters:

elem - Should be non-null template element.

Returns:

The first previous occurance of an xsl:variable or xsl:param, or null if none is found.

getPrevElementWithinContext

protected ElemTemplateElement getPrevElementWithinContext(ElemTemplateElement elem)

Get the previous sibling or parent of the given template, stopping at xsl:for-each, xsl:template, or xsl:stylesheet.

Parameters:

elem - Should be non-null template element.

Returns:

previous sibling or parent, or null if previous is xsl:for-each, xsl:template, or xsl:stylesheet.

getElemFromExpression

protected ElemTemplateElement getElemFromExpression(Expression expr)

From an XPath expression component, get the ElemTemplateElement owner.

Parameters:

expr - Should be static expression with proper parentage.

Returns:

Valid ElemTemplateElement, or throw a runtime exception if it is not found.

isAbsolute

public boolean isAbsolute(LocPathIterator path)

Tell if the given LocPathIterator is relative to an absolute path, i.e. in not dependent on the context.

Returns:

true if the LocPathIterator is not dependent on the context node.

visitLocationPath

public boolean visitLocationPath(ExpressionOwner owner,
                                 LocPathIterator path)

Visit a LocationPath.

Overrides:

visitLocationPath in class XPathVisitor

Parameters:

owner - The owner of the expression, to which the expression can be reset if rewriting takes place.

path - The LocationPath object.

Returns:

true if the sub expressions should be traversed.

visitPredicate

public boolean visitPredicate(ExpressionOwner owner,
                              Expression pred)

Visit a predicate within a location path. Note that there isn't a proper unique component for predicates, and that the expression will be called also for whatever type Expression is.

Overrides:

visitPredicate in class XPathVisitor

Parameters:

owner - The owner of the expression, to which the expression can be reset if rewriting takes place.

pred - The predicate object.

Returns:

true if the sub expressions should be traversed.

visitTopLevelInstruction

public boolean visitTopLevelInstruction(ElemTemplateElement elem)

Visit an XSLT top-level instruction.

Overrides:

visitTopLevelInstruction in class XSLTVisitor

Parameters:

elem - The xsl instruction element object.

Returns:

true if the sub expressions should be traversed.

visitInstruction

public boolean visitInstruction(ElemTemplateElement elem)

Visit an XSLT instruction. Any element that isn't called by one of the other visit methods, will be called by this method.

Overrides:

visitInstruction in class XSLTVisitor

Parameters:

elem - The xsl instruction element object.

Returns:

true if the sub expressions should be traversed.

diagnoseNumPaths

protected void diagnoseNumPaths(java.util.Vector paths,
                                int numPathsEliminated,
                                int numUniquePathsEliminated)

Print out to std err the number of paths reduced.

assertIsLocPathIterator

private final void assertIsLocPathIterator(Expression expr1,
                                           ExpressionOwner eo)
                                    throws java.lang.RuntimeException

Assert that the expression is a LocPathIterator, and, if not, try to give some diagnostic info.

Throws:

java.lang.RuntimeException

validateNewAddition

private static void validateNewAddition(java.util.Vector paths,
                                        ExpressionOwner owner,
                                        LocPathIterator path)
                                 throws java.lang.RuntimeException

Validate some assumptions about the new LocPathIterator and it's owner and the state of the list.

Throws:

java.lang.RuntimeException

assertion

protected static void assertion(boolean b,
                                java.lang.String msg)

Simple assertion.