http://xml.apache.org/xalan-j/: Xalan-Java is an XSLT processor for transforming XML documents into HTML, text, or other XML document types. It implements XSL Transformations (XSLT) Version 1.0 and XML Path Language (XPath) Version 1.0 and can be used from the command line, in an applet or a servlet, or as a module in other program. (The Apache Software Foundation) 
/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements. See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership. The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the  "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
 * $Id: RedundentExprEliminator.java 468643 2006-10-28 06:56:03Z minchau $
 */
package org.apache.xalan.templates;

import java.util.Vector;

import org.apache.xalan.res.XSLMessages;
import org.apache.xalan.res.XSLTErrorResources;
import org.apache.xml.utils.QName;
import org.apache.xml.utils.WrappedRuntimeException;
import org.apache.xpath.Expression;
import org.apache.xpath.ExpressionNode;
import org.apache.xpath.ExpressionOwner;
import org.apache.xpath.XPath;
import org.apache.xpath.axes.AxesWalker;
import org.apache.xpath.axes.FilterExprIteratorSimple;
import org.apache.xpath.axes.FilterExprWalker;
import org.apache.xpath.axes.LocPathIterator;
import org.apache.xpath.axes.SelfIteratorNoPredicate;
import org.apache.xpath.axes.WalkerFactory;
import org.apache.xpath.axes.WalkingIterator;
import org.apache.xpath.operations.Variable;
import org.apache.xpath.operations.VariableSafeAbsRef;


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.

/**
 * 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.
 */
public class RedundentExprEliminator extends XSLTVisitor
{
  Vector m_paths;
  Vector m_absPaths;
  boolean m_isSameContext;
  AbsPathChecker m_absPathChecker = new AbsPathChecker();
  
  private static int m_uniquePseudoVarID = 1;
  static final String PSUEDOVARNAMESPACE = Constants.S_VENDORURL+"/xalan/psuedovar";
 
  public static final boolean DEBUG = false;
  public static final boolean DIAGNOSE_NUM_PATHS_REDUCED = false;
  public static final boolean DIAGNOSE_MULTISTEPLIST = false;

  
So we can reuse it over and over again.

/**
   * So we can reuse it over and over again.
   */
  VarNameCollector m_varNameCollector = new VarNameCollector();

  
Construct a RedundentExprEliminator.

/**
   * Construct a RedundentExprEliminator.
   */
  public RedundentExprEliminator()
  {
    m_isSameContext = true;
    m_absPaths = new Vector();
    m_paths = null;
  }
  
  
  
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.

Params:
  • psuedoVarRecipient – The recipient of the psuedo vars.  The 
variables will be inserted as first children of the element, before 
any existing variables.
/**
   * 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.
   * 
   * @param psuedoVarRecipient The recipient of the psuedo vars.  The 
   * variables will be inserted as first children of the element, before 
   * any existing variables.
   */
  public void eleminateRedundentLocals(ElemTemplateElement psuedoVarRecipient)
  {
    eleminateRedundent(psuedoVarRecipient, m_paths);
  }
  
  
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.

/**
   * 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.
   * 
   */
  public void eleminateRedundentGlobals(StylesheetRoot stylesheet)
  {
    eleminateRedundent(stylesheet, m_absPaths);
  }

  
  
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.

Params:
  • 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.
/**
   * 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.
   * 
   * @param psuedoVarRecipient The owner of the subtree from where the 
   *                           paths were collected.
   * @param paths A vector of paths that hold ExpressionOwner objects, 
   *              which must yield LocationPathIterators.
   */
  protected void eleminateRedundent(ElemTemplateElement psuedoVarRecipient, Vector paths)
  {
    int n = paths.size();
    int numPathsEliminated = 0;
    int numUniquePathsEliminated = 0;
    for (int i = 0; i < n; i++)
    {
      ExpressionOwner owner = (ExpressionOwner) paths.elementAt(i);
      if (null != owner)
      {
        int found = findAndEliminateRedundant(i + 1, i, owner, psuedoVarRecipient, paths);
        if (found > 0)
                  numUniquePathsEliminated++;
        numPathsEliminated += found;
      }
    }
    
    eleminateSharedPartialPaths(psuedoVarRecipient, paths);
    
    if(DIAGNOSE_NUM_PATHS_REDUCED)
		diagnoseNumPaths(paths, numPathsEliminated, numUniquePathsEliminated);
  }
  
  
Eliminate the shared partial paths in the expression list.

Params:
  • psuedoVarRecipient – The recipient of the psuedo vars.
  • paths – A vector of paths that hold ExpressionOwner objects, 
             which must yield LocationPathIterators.
/**
   * Eliminate the shared partial paths in the expression list.
   * 
   * @param psuedoVarRecipient The recipient of the psuedo vars.
   * 
   * @param paths A vector of paths that hold ExpressionOwner objects, 
   *              which must yield LocationPathIterators.
   */
  protected void eleminateSharedPartialPaths(ElemTemplateElement psuedoVarRecipient, Vector paths)
  {
  	MultistepExprHolder list = createMultistepExprList(paths);
  	if(null != list)
  	{
  		if(DIAGNOSE_MULTISTEPLIST)
        	list.diagnose();
        	
        boolean isGlobal = (paths == m_absPaths);
        	
        // Iterate over the list, starting with the most number of paths, 
        // trying to find the longest matches first.
        int longestStepsCount = list.m_stepCount;
    	for (int i = longestStepsCount-1; i >= 1; i--)
    	{
    		MultistepExprHolder next = list;
        	while(null != next)
        	{
        		if(next.m_stepCount < i)
        			break;
				list = matchAndEliminatePartialPaths(next, list, isGlobal, i, psuedoVarRecipient);
				next = next.m_next;
        	}
    	}
  	}
  }

  
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.
/**
   * 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.
   * 
   * @return The head of the list, which may have changed.
   */
  protected MultistepExprHolder matchAndEliminatePartialPaths(MultistepExprHolder testee, 
                                               MultistepExprHolder head,
                                               boolean isGlobal,
                                               int lengthToTest,
                                               ElemTemplateElement varScope)
  {  	
  	if(null == testee.m_exprOwner)
  		return head;
  		
    // Start with the longest possible match, and move down.
    WalkingIterator iter1 = (WalkingIterator) testee.m_exprOwner.getExpression();
    if(partialIsVariable(testee, lengthToTest))
    	return head;
    MultistepExprHolder matchedPaths = null;
    MultistepExprHolder matchedPathsTail = null;
    MultistepExprHolder meh = head;
    while( null != meh)
    {
      if ((meh != testee) && (null != meh.m_exprOwner))
      {
	      WalkingIterator iter2 = (WalkingIterator) meh.m_exprOwner.getExpression();
	      if (stepsEqual(iter1, iter2, lengthToTest))
	      {
	        if (null == matchedPaths)
	        {
	          try
	          {
	          	matchedPaths = (MultistepExprHolder)testee.clone();
	          	testee.m_exprOwner = null; // So it won't be processed again.
	          }
	          catch(CloneNotSupportedException cnse){}
	          matchedPathsTail = matchedPaths;
	          matchedPathsTail.m_next = null;
	        }
	       
	        try
	        {
	          matchedPathsTail.m_next = (MultistepExprHolder)meh.clone();
	          meh.m_exprOwner = null; // So it won't be processed again.
	        }
	        catch(CloneNotSupportedException cnse){}
	        matchedPathsTail = matchedPathsTail.m_next;
	        matchedPathsTail.m_next = null;
	      }
      }
      meh = meh.m_next;
    }
    	
	int matchCount = 0;
	if(null != matchedPaths)
	{
		ElemTemplateElement root = isGlobal ? varScope : findCommonAncestor(matchedPaths);
		WalkingIterator sharedIter = (WalkingIterator)matchedPaths.m_exprOwner.getExpression();
		WalkingIterator newIter = createIteratorFromSteps(sharedIter, lengthToTest);
		ElemVariable var = createPseudoVarDecl(root, newIter, isGlobal);
		if(DIAGNOSE_MULTISTEPLIST)
			System.err.println("Created var: "+var.getName()+(isGlobal ? "(Global)" : ""));
		while(null != matchedPaths)
		{
			ExpressionOwner owner = matchedPaths.m_exprOwner;
			WalkingIterator iter = (WalkingIterator)owner.getExpression();
			
			if(DIAGNOSE_MULTISTEPLIST)
				diagnoseLineNumber(iter);
			
			LocPathIterator newIter2 = 
			    changePartToRef(var.getName(), iter, lengthToTest, isGlobal);
			owner.setExpression(newIter2);
			
			matchedPaths = matchedPaths.m_next;
		}
	}
	
	if(DIAGNOSE_MULTISTEPLIST)
		diagnoseMultistepList(matchCount, lengthToTest, isGlobal);
    return head;
  }
  
  
Check if results of partial reduction will just be a variable, in 
which case, skip it.

/**
   * Check if results of partial reduction will just be a variable, in 
   * which case, skip it.
   */
  boolean partialIsVariable(MultistepExprHolder testee, int lengthToTest)
  {
  	if(1 == lengthToTest)
  	{
  		WalkingIterator wi = (WalkingIterator)testee.m_exprOwner.getExpression();
  		if(wi.getFirstWalker() instanceof FilterExprWalker)
  			return true;
  	}
  	return false;
  }

  
Tell what line number belongs to a given expression.

/**
   * Tell what line number belongs to a given expression.
   */
  protected void diagnoseLineNumber(Expression expr)
  {
    ElemTemplateElement e = getElemFromExpression(expr);
    System.err.println("   " + e.getSystemId() + " Line " + e.getLineNumber());
  }
      
  
Given a linked list of expressions, find the common ancestor that is 
suitable for holding a psuedo variable for shared access.

/**
   * Given a linked list of expressions, find the common ancestor that is 
   * suitable for holding a psuedo variable for shared access.
   */
  protected ElemTemplateElement findCommonAncestor(MultistepExprHolder head)
  {
  	// Not sure this algorithm is the best, but will do for the moment.
  	int numExprs = head.getLength();
  	// The following could be made cheaper by pre-allocating large arrays, 
  	// but then we would have to assume a max number of reductions, 
  	// which I am not inclined to do right now.
    ElemTemplateElement[] elems = new ElemTemplateElement[numExprs];
    int[] ancestorCounts = new int[numExprs];
    
    // Loop through, getting the parent elements, and counting the 
    // ancestors.
  	MultistepExprHolder next = head;
  	int shortestAncestorCount = 10000;
  	for(int i = 0; i < numExprs; i++)
  	{
  		ElemTemplateElement elem = 
  			getElemFromExpression(next.m_exprOwner.getExpression());
  		elems[i] = elem;
  		int numAncestors = countAncestors(elem);
  		ancestorCounts[i] = numAncestors;
  		if(numAncestors < shortestAncestorCount)
  		{
  			shortestAncestorCount = numAncestors;
  		}
  		next = next.m_next;
  	}
  	
  	// Now loop through and "correct" the elements that have more ancestors.
  	for(int i = 0; i < numExprs; i++)
  	{
  		if(ancestorCounts[i] > shortestAncestorCount)
  		{
  			int numStepCorrection = ancestorCounts[i] - shortestAncestorCount;
  			for(int j = 0; j < numStepCorrection; j++)
  			{
  				elems[i] = elems[i].getParentElem();
  			}
  		}
  	}
  	
  	// Now everyone has an equal number of ancestors.  Walk up from here 
  	// equally until all are equal.
  	ElemTemplateElement first = null;
  	while(shortestAncestorCount-- >= 0)
  	{
  		boolean areEqual = true;
  		first = elems[0];
  		for(int i = 1; i < numExprs; i++)
  		{
  			if(first != elems[i])
  			{
  				areEqual = false;
  				break;
  			}
  		}
  		// This second check is to make sure we have a common ancestor that is not the same 
  		// as the expression owner... i.e. the var decl has to go above the expression owner.
  		if(areEqual && isNotSameAsOwner(head, first) && first.canAcceptVariables())
  		{
  			if(DIAGNOSE_MULTISTEPLIST)
  			{
  				System.err.print(first.getClass().getName());
  				System.err.println(" at   " + first.getSystemId() + " Line " + first.getLineNumber());
  			}
  			return first;
  		}
   			
  		for(int i = 0; i < numExprs; i++)
  		{
  			elems[i] = elems[i].getParentElem();
  		}
  	}
  	
  	assertion(false, "Could not find common ancestor!!!");
  	return null;
  }
  
  
Find out if the given ElemTemplateElement is not the same as one of 
the ElemTemplateElement owners of the expressions.

Params:
  • 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.
/**
   * Find out if the given ElemTemplateElement is not the same as one of 
   * the ElemTemplateElement owners of the expressions.
   * 
   * @param head Head of linked list of expression owners.
   * @param ete The ElemTemplateElement that is a candidate for a psuedo 
   * variable parent.
   * @return 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.
   */
  protected boolean isNotSameAsOwner(MultistepExprHolder head, ElemTemplateElement ete)
  {
  	MultistepExprHolder next = head;
  	while(null != next)
  	{
  		ElemTemplateElement elemOwner = getElemFromExpression(next.m_exprOwner.getExpression());
  		if(elemOwner == ete)
  			return false;
  		next = next.m_next;
  	}
  	return true;
  }
  
  
Count the number of ancestors that a ElemTemplateElement has.

Params:
  • elem – An representation of an element in an XSLT stylesheet.
Returns:The number of ancestors of elem (including the element itself).
/**
   * Count the number of ancestors that a ElemTemplateElement has.
   * 
   * @param elem An representation of an element in an XSLT stylesheet.
   * @return The number of ancestors of elem (including the element itself).
   */
  protected int countAncestors(ElemTemplateElement elem)
  {
  	int count = 0;
  	while(null != elem)
  	{
  		count++;
  		elem = elem.getParentElem();
  	}
  	return count;
  }

  
Print out diagnostics about partial multistep evaluation.

/**
   * Print out diagnostics about partial multistep evaluation.
   */
  protected void diagnoseMultistepList(
      int matchCount,
      int lengthToTest,
      boolean isGlobal)
  {
      if (matchCount > 0)
        {
        System.err.print(
          "Found multistep matches: " + matchCount + ", " + lengthToTest + " length");
        if (isGlobal)
              System.err.println(" (global)");
        else
              System.err.println();
      }
  }
  
  
Change a given number of steps to a single variable reference.

Params:
  • 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.
/**
   * Change a given number of steps to a single variable reference.
   * 
   * @param uniquePseudoVarName The name of the variable reference.
   * @param wi The walking iterator that is to be changed.
   * @param numSteps The number of steps to be changed.
   * @param isGlobal true if this will be a global reference.
   */
  protected LocPathIterator changePartToRef(final QName uniquePseudoVarName, WalkingIterator wi, 
                                 final int numSteps, final boolean isGlobal)
  {
  	Variable var = new Variable();
  	var.setQName(uniquePseudoVarName);
  	var.setIsGlobal(isGlobal);
  	if(isGlobal)
  	{	ElemTemplateElement elem = getElemFromExpression(wi);
  		StylesheetRoot root = elem.getStylesheetRoot();
  		Vector vars = root.getVariablesAndParamsComposed();
  		var.setIndex(vars.size()-1);
  	}
  	
  	// Walk to the first walker after the one's we are replacing.
  	AxesWalker walker = wi.getFirstWalker();
  	for(int i = 0; i < numSteps; i++)
  	{
  		assertion(null != walker, "Walker should not be null!");
  		walker = walker.getNextWalker();
  	}
  	
  	if(null != walker)
  	{
  	
  	  FilterExprWalker few = new FilterExprWalker(wi);
  	  few.setInnerExpression(var);
  	  few.exprSetParent(wi);
  	  few.setNextWalker(walker);
  	  walker.setPrevWalker(few);
  	  wi.setFirstWalker(few);
  	  return wi;
  	}
  	else
  	{
  	  FilterExprIteratorSimple feis = new FilterExprIteratorSimple(var);
  	  feis.exprSetParent(wi.exprGetParent());
  	  return feis;
  	}
  }
  
  
Create a new WalkingIterator from the steps in another WalkingIterator.

Params:
  • 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.
/**
   * Create a new WalkingIterator from the steps in another WalkingIterator.
   * 
   * @param wi The iterator from where the steps will be taken.
   * @param numSteps The number of steps from the first to copy into the new 
   *                 iterator.
   * @return The new iterator.
   */
  protected WalkingIterator createIteratorFromSteps(final WalkingIterator wi, int numSteps)
  {
  	WalkingIterator newIter = new WalkingIterator(wi.getPrefixResolver());
  	try
  	{
  		AxesWalker walker = (AxesWalker)wi.getFirstWalker().clone();
  		newIter.setFirstWalker(walker);
  		walker.setLocPathIterator(newIter);
  		for(int i = 1; i < numSteps; i++)
  		{
  			AxesWalker next = (AxesWalker)walker.getNextWalker().clone();
  			walker.setNextWalker(next);
  			next.setLocPathIterator(newIter);
  			walker = next;
  		}
  		walker.setNextWalker(null);
  	}
  	catch(CloneNotSupportedException cnse)
  	{
  		throw new WrappedRuntimeException(cnse);
  	}
  	return newIter;
  }
    
  
Compare a given number of steps between two iterators, to see if they are equal.

Params:
  • 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.
/**
   * Compare a given number of steps between two iterators, to see if they are equal.
   * 
   * @param iter1 The first iterator to compare.
   * @param iter2 The second iterator to compare.
   * @param numSteps The number of steps to compare.
   * @return true If the given number of steps are equal.
   * 
   */
  protected boolean stepsEqual(WalkingIterator iter1, WalkingIterator iter2, 
                                         int numSteps)
  {
  	AxesWalker aw1 = iter1.getFirstWalker();
  	AxesWalker aw2 = iter2.getFirstWalker();
  	
  	for(int i = 0; (i < numSteps); i++)
  	{
  		if((null == aw1) || (null == aw2))
  		 	return false;
  		 	
  		if(!aw1.deepEquals(aw2))
  			return false;
  		
  		aw1 = aw1.getNextWalker();
  		aw2 = aw2.getNextWalker();
  	}
  	
  	assertion((null != aw1) || (null != aw2), "Total match is incorrect!");
  	
  	return true;
  }
  
  
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.

Params:
  • 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.
/**
   * 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.
   * 
   * @param paths Vector of ExpressionOwner objects, which may contain null entries. 
   *              The ExpressionOwner objects must own LocPathIterator objects.
   * @return 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.
   */
  protected MultistepExprHolder createMultistepExprList(Vector paths)
  {
  	MultistepExprHolder first = null;
  	int n = paths.size();
  	for(int i = 0; i < n; i++)
  	{
  		ExpressionOwner eo = (ExpressionOwner)paths.elementAt(i);
  		if(null == eo)
  			continue;
  			
  		// Assuming location path iterators should be OK.
  		LocPathIterator lpi = (LocPathIterator)eo.getExpression();
  		int numPaths = countSteps(lpi);
  		if(numPaths > 1)
  		{
  			if(null == first)
  				first = new MultistepExprHolder(eo, numPaths, null);
  			else
  				first = first.addInSortedOrder(eo, numPaths);
  		}
  	}
  	
  	if((null == first) || (first.getLength() <= 1))
  		return null;
  	else
  		return first;
  }
  
  
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.

Params:
  • 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.
/**
   * 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.
   * 
   * @param start The position to start looking in the vector.
   * @param firstOccuranceIndex The position of firstOccuranceOwner.
   * @param firstOccuranceOwner The owner of the expression we are looking for.
   * @param psuedoVarRecipient Where to put the psuedo variables.
   * 
   * @return The number of expression occurances that were modified.
   */
  protected int findAndEliminateRedundant(int start, int firstOccuranceIndex,
                         ExpressionOwner firstOccuranceOwner, 
                         ElemTemplateElement psuedoVarRecipient,
                         Vector paths) 
                 throws org.w3c.dom.DOMException 
  {
	MultistepExprHolder head = null;
	MultistepExprHolder tail = null;
	int numPathsFound = 0;
	int n = paths.size();
	
	Expression expr1 = firstOccuranceOwner.getExpression();
	if(DEBUG)
		assertIsLocPathIterator(expr1, firstOccuranceOwner);
	boolean isGlobal = (paths == m_absPaths);
	LocPathIterator lpi = (LocPathIterator)expr1;
	int stepCount = countSteps(lpi);
	for(int j = start; j < n; j++)
	{
		ExpressionOwner owner2 = (ExpressionOwner)paths.elementAt(j);
		if(null != owner2)
		{
			Expression expr2 = owner2.getExpression();
			boolean isEqual = expr2.deepEquals(lpi);
			if(isEqual)
			{  		
				LocPathIterator lpi2  = (LocPathIterator)expr2;				
				if(null == head)
				{
					head = new MultistepExprHolder(firstOccuranceOwner, stepCount, null);
					tail = head;
					numPathsFound++;
				}
				tail.m_next = new MultistepExprHolder(owner2, stepCount, null);
				tail = tail.m_next;
	
				// Null out the occurance, so we don't have to test it again.
				paths.setElementAt(null, j);
				
				// foundFirst = true;
				numPathsFound++;
			}
		}
	}
	
	// Change all globals in xsl:templates, etc, to global vars no matter what.
	if((0 == numPathsFound) && isGlobal)
	{
      head = new MultistepExprHolder(firstOccuranceOwner, stepCount, null);
      numPathsFound++;
	}
	
	if(null != head)
	{
		ElemTemplateElement root = isGlobal ? psuedoVarRecipient : findCommonAncestor(head);
		LocPathIterator sharedIter = (LocPathIterator)head.m_exprOwner.getExpression();
		ElemVariable var = createPseudoVarDecl(root, sharedIter, isGlobal);
		if(DIAGNOSE_MULTISTEPLIST)
			System.err.println("Created var: "+var.getName()+(isGlobal ? "(Global)" : ""));
		QName uniquePseudoVarName = var.getName();
		while(null != head)
		{
			ExpressionOwner owner = head.m_exprOwner;	
			if(DIAGNOSE_MULTISTEPLIST)
				diagnoseLineNumber(owner.getExpression());
			changeToVarRef(uniquePseudoVarName, owner, paths, root);
			head = head.m_next;
		}
		// Replace the first occurance with the variable's XPath, so  
		// that further reduction may take place if needed.
		paths.setElementAt(var.getSelect(), firstOccuranceIndex);
	}
	
	return numPathsFound;
  } 
  
  
To be removed.

/**
   * To be removed.
   */
  protected int oldFindAndEliminateRedundant(int start, int firstOccuranceIndex,
                         ExpressionOwner firstOccuranceOwner, 
                         ElemTemplateElement psuedoVarRecipient,
                         Vector paths) 
                 throws org.w3c.dom.DOMException 
  {
	QName uniquePseudoVarName = null;
	boolean foundFirst = false;
	int numPathsFound = 0;
	int n = paths.size();
	Expression expr1 = firstOccuranceOwner.getExpression();
	if(DEBUG)
		assertIsLocPathIterator(expr1, firstOccuranceOwner);
	boolean isGlobal = (paths == m_absPaths);
	LocPathIterator lpi = (LocPathIterator)expr1;
	for(int j = start; j < n; j++)
	{
		ExpressionOwner owner2 = (ExpressionOwner)paths.elementAt(j);
		if(null != owner2)
		{
			Expression expr2 = owner2.getExpression();
			boolean isEqual = expr2.deepEquals(lpi);
			if(isEqual)
			{  		
				LocPathIterator lpi2  = (LocPathIterator)expr2;				
				if(!foundFirst)
				{
					foundFirst = true;
					// Insert variable decl into psuedoVarRecipient
					// We want to insert this into the first legitimate 
					// position for a variable.
				    ElemVariable var = createPseudoVarDecl(psuedoVarRecipient, lpi, isGlobal);
				    if(null == var)
				    	return 0;
				    uniquePseudoVarName = var.getName();
	
					changeToVarRef(uniquePseudoVarName, firstOccuranceOwner, 
					               paths, psuedoVarRecipient);
					               
					// Replace the first occurance with the variable's XPath, so  
					// that further reduction may take place if needed.
					paths.setElementAt(var.getSelect(), firstOccuranceIndex);
					numPathsFound++;
				}
	
				changeToVarRef(uniquePseudoVarName, owner2, paths, psuedoVarRecipient);
	
				// Null out the occurance, so we don't have to test it again.
				paths.setElementAt(null, j);
				
				// foundFirst = true;
				numPathsFound++;
			}
		}
	}
	
	// Change all globals in xsl:templates, etc, to global vars no matter what.
	if((0 == numPathsFound) && (paths == m_absPaths))
	{
      ElemVariable var = createPseudoVarDecl(psuedoVarRecipient, lpi, true);
      if(null == var)
        return 0;
	  uniquePseudoVarName = var.getName();
      changeToVarRef(uniquePseudoVarName, firstOccuranceOwner, paths, psuedoVarRecipient);
      paths.setElementAt(var.getSelect(), firstOccuranceIndex);
      numPathsFound++;
	}
	return numPathsFound;
  }
  
  
Count the steps in a given location path.

Params:
  • lpi – The location path iterator that owns the steps.
Returns:The number of steps in the given location path.
/**
   * Count the steps in a given location path.
   * 
   * @param lpi The location path iterator that owns the steps.
   * @return The number of steps in the given location path.
   */
  protected int countSteps(LocPathIterator lpi)
  {
  	if(lpi instanceof WalkingIterator)
  	{
  		WalkingIterator wi = (WalkingIterator)lpi;
  		AxesWalker aw = wi.getFirstWalker();
  		int count = 0;
  		while(null != aw)
  		{
  			count++;
  			aw = aw.getNextWalker();
  		}
  		return count;
  	}
  	else
  		return 1;
  }
  
  
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.

Params:
  • 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.
/**
   * 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.
   * 
   * @param varName The name of the variable which will be referenced.
   * @param owner The owner of the expression which will be replaced by a variable ref.
   * @param paths The paths list that the iterator came from, mainly to determine
   *              if this is a local or global reduction.
   * @param psuedoVarRecipient The element within whose scope the variable is 
   *                           being inserted, possibly a StylesheetRoot.
   */
  protected void changeToVarRef(QName varName, ExpressionOwner owner, 
                                Vector paths, ElemTemplateElement psuedoVarRecipient) 
  {
	Variable varRef = (paths == m_absPaths) ? new VariableSafeAbsRef() : new Variable();
	varRef.setQName(varName);
	if(paths == m_absPaths)
	{
		StylesheetRoot root = (StylesheetRoot)psuedoVarRecipient;
		Vector globalVars = root.getVariablesAndParamsComposed();
		// Assume this operation is occuring just after the decl has 
		// been added.
		varRef.setIndex(globalVars.size()-1);
		varRef.setIsGlobal(true);
	}
	owner.setExpression(varRef);
  }
   
  private synchronized static int getPseudoVarID(){
      return m_uniquePseudoVarID++; 
  }
  
  
Create a psuedo variable reference that will represent the 
shared redundent XPath, and add it to the stylesheet.

Params:
  • 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.
/**
   * Create a psuedo variable reference that will represent the 
   * shared redundent XPath, and add it to the stylesheet.
   * 
   * @param psuedoVarRecipient The broadest scope of where the variable 
   * should be inserted, usually an xsl:template or xsl:for-each.
   * @param lpi The LocationPathIterator that the variable should represent.
   * @param isGlobal true if the paths are global.
   * @return The new psuedo var element.
   */
  protected ElemVariable createPseudoVarDecl(
      ElemTemplateElement psuedoVarRecipient,
      LocPathIterator lpi, boolean isGlobal)
      throws org.w3c.dom.DOMException
  {
    QName uniquePseudoVarName = new QName (PSUEDOVARNAMESPACE, "#"+getPseudoVarID());
  		
  	if(isGlobal)
  	{
  	  return createGlobalPseudoVarDecl(uniquePseudoVarName, 
  	                                  (StylesheetRoot)psuedoVarRecipient, lpi);
  	}
  	else						
      return createLocalPseudoVarDecl(uniquePseudoVarName, psuedoVarRecipient, lpi);
  }
  
  
Create a psuedo variable reference that will represent the 
shared redundent XPath, for a local reduction.

Params:
  • 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.
/**
   * Create a psuedo variable reference that will represent the 
   * shared redundent XPath, for a local reduction.
   * 
   * @param uniquePseudoVarName The name of the new variable.
   * @param stylesheetRoot The broadest scope of where the variable 
   *        should be inserted, which must be a StylesheetRoot element in this case.
   * @param lpi The LocationPathIterator that the variable should represent.
   * @return null if the decl was not created, otherwise the new Pseudo var  
   *              element.
   */
  protected ElemVariable createGlobalPseudoVarDecl(QName uniquePseudoVarName,
                                           StylesheetRoot stylesheetRoot, 
                                           LocPathIterator lpi) 
        throws org.w3c.dom.DOMException 
  {
  	ElemVariable psuedoVar = new ElemVariable();
  	psuedoVar.setIsTopLevel(true);
	XPath xpath = new XPath(lpi);
	psuedoVar.setSelect(xpath);
	psuedoVar.setName(uniquePseudoVarName);
	
	Vector globalVars = stylesheetRoot.getVariablesAndParamsComposed();
	psuedoVar.setIndex(globalVars.size());
	globalVars.addElement(psuedoVar);
	return psuedoVar;
  }

  
  

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

Params:
  • 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.
/**
   * Create a psuedo variable reference that will represent the 
   * shared redundent XPath, for a local reduction.
   * 
   * @param uniquePseudoVarName The name of the new variable.
   * @param psuedoVarRecipient The broadest scope of where the variable 
   * should be inserted, usually an xsl:template or xsl:for-each.
   * @param lpi The LocationPathIterator that the variable should represent.
   * @return null if the decl was not created, otherwise the new Pseudo var  
   *              element.
   */
  protected ElemVariable createLocalPseudoVarDecl(QName uniquePseudoVarName,
                                           ElemTemplateElement psuedoVarRecipient, 
                                           LocPathIterator lpi) 
        throws org.w3c.dom.DOMException 
  {
		ElemVariable psuedoVar = new ElemVariablePsuedo();
		
		XPath xpath = new XPath(lpi);
		psuedoVar.setSelect(xpath);
		psuedoVar.setName(uniquePseudoVarName);

		ElemVariable var = addVarDeclToElem(psuedoVarRecipient, lpi, psuedoVar);
		
		lpi.exprSetParent(var);
		
		return var;
  }

  
Add the given variable to the psuedoVarRecipient.

/**
   * Add the given variable to the psuedoVarRecipient.
   */
  protected ElemVariable addVarDeclToElem(
    ElemTemplateElement psuedoVarRecipient,
    LocPathIterator lpi,
    ElemVariable psuedoVar)
    throws org.w3c.dom.DOMException
  {
    // Create psuedo variable element
    ElemTemplateElement ete = psuedoVarRecipient.getFirstChildElem();

    lpi.callVisitors(null, m_varNameCollector);

    // If the location path contains variables, we have to insert the 
    // psuedo variable after the reference. (Otherwise, we want to 
    // insert it as close as possible to the top, so we'll be sure 
    // it is in scope for any other vars.
    if (m_varNameCollector.getVarCount() > 0)
    {
      ElemTemplateElement baseElem = getElemFromExpression(lpi);
      ElemVariable varElem = getPrevVariableElem(baseElem);
      while (null != varElem)
      {
        if (m_varNameCollector.doesOccur(varElem.getName()))
          {
          psuedoVarRecipient = varElem.getParentElem();
          ete = varElem.getNextSiblingElem();
          break;
        }
        varElem = getPrevVariableElem(varElem);
      }
    }

    if ((null != ete) && (Constants.ELEMNAME_PARAMVARIABLE == ete.getXSLToken()))
    {
      // Can't stick something in front of a param, so abandon! (see variable13.xsl)
      if(isParam(lpi))
        return null;

      while (null != ete)
      {
        ete = ete.getNextSiblingElem();
        if ((null != ete) && Constants.ELEMNAME_PARAMVARIABLE != ete.getXSLToken())
            break;
      }
    }
    psuedoVarRecipient.insertBefore(psuedoVar, ete);
    m_varNameCollector.reset();
    return psuedoVar;
  }
    
  
Tell if the expr param is contained within an xsl:param.

/**
   * Tell if the expr param is contained within an xsl:param.
   */
  protected boolean isParam(ExpressionNode expr)
  {
  	while(null != expr)
  	{
  		if(expr instanceof ElemTemplateElement)
  			break;
  		expr = expr.exprGetParent();
  	}
  	if(null != expr)
  	{
  		ElemTemplateElement ete = (ElemTemplateElement)expr;
  		while(null != ete)
  		{
  			int type = ete.getXSLToken();
  			switch(type)
  			{
  				case Constants.ELEMNAME_PARAMVARIABLE:
  					return true;
  				case Constants.ELEMNAME_TEMPLATE:
  				case Constants.ELEMNAME_STYLESHEET:
  					return false;
  			}
  			ete = ete.getParentElem();
  		}
  	}
  	return false;
  	
  }
  
  
Find the previous occurance of a xsl:variable.  Stop 
the search when a xsl:for-each, xsl:template, or xsl:stylesheet is 
encountered.

Params:
  • 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.
/**
   * Find the previous occurance of a xsl:variable.  Stop 
   * the search when a xsl:for-each, xsl:template, or xsl:stylesheet is 
   * encountered.
   * 
   * @param elem Should be non-null template element.
   * @return The first previous occurance of an xsl:variable or xsl:param, 
   * or null if none is found.
   */
  protected ElemVariable getPrevVariableElem(ElemTemplateElement elem)
  {
  	// This could be somewhat optimized.  since getPreviousSiblingElem is a  
  	// fairly expensive operation.
  	while(null != (elem = getPrevElementWithinContext(elem)))
  	{
  		int type = elem.getXSLToken();
  			
  		if((Constants.ELEMNAME_VARIABLE == type) ||
  		   (Constants.ELEMNAME_PARAMVARIABLE == type))
  		{
  			return (ElemVariable)elem;
  		}
  	}
  	return null;
  }
  
  
Get the previous sibling or parent of the given template, stopping at 
xsl:for-each, xsl:template, or xsl:stylesheet.

Params:
  • 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.
/**
   * Get the previous sibling or parent of the given template, stopping at 
   * xsl:for-each, xsl:template, or xsl:stylesheet.
   * 
   * @param elem Should be non-null template element.
   * @return previous sibling or parent, or null if previous is xsl:for-each, 
   * xsl:template, or xsl:stylesheet.
   */
  protected ElemTemplateElement getPrevElementWithinContext(ElemTemplateElement elem)
  {
  	ElemTemplateElement prev = elem.getPreviousSiblingElem();
  	if(null == prev)
  		prev = elem.getParentElem();
  	if(null != prev)
  	{
  	  int type = prev.getXSLToken();
  	  if((Constants.ELEMNAME_FOREACH == type) || 
  	     (Constants.ELEMNAME_TEMPLATE == type) ||
  	     (Constants.ELEMNAME_STYLESHEET == type))
  	  {
  	  	prev = null;
  	  }
  	}
  	return prev;
  }
  
  
From an XPath expression component, get the ElemTemplateElement 
owner.

Params:
  • expr – Should be static expression with proper parentage.
Returns:Valid ElemTemplateElement, or throw a runtime exception 
if it is not found.
/**
   * From an XPath expression component, get the ElemTemplateElement 
   * owner.
   * 
   * @param expr Should be static expression with proper parentage.
   * @return Valid ElemTemplateElement, or throw a runtime exception 
   * if it is not found.
   */
  protected ElemTemplateElement getElemFromExpression(Expression expr)
  {
  	ExpressionNode parent = expr.exprGetParent();
  	while(null != parent)
  	{
  		if(parent instanceof ElemTemplateElement)
  			return (ElemTemplateElement)parent;
  		parent = parent.exprGetParent();
  	}
  	throw new RuntimeException(XSLMessages.createMessage(XSLTErrorResources.ER_ASSERT_NO_TEMPLATE_PARENT, null));
  	// "Programmer's error! expr has no ElemTemplateElement parent!");
  }
      
  
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.
/**
   * Tell if the given LocPathIterator is relative to an absolute path, i.e. 
   * in not dependent on the context.
   * 
   * @return true if the LocPathIterator is not dependent on the context node.
   */
  public boolean isAbsolute(LocPathIterator path)
  {
  	int analysis = path.getAnalysisBits();
    boolean isAbs = (WalkerFactory.isSet(analysis, WalkerFactory.BIT_ROOT) || 
           WalkerFactory.isSet(analysis, WalkerFactory.BIT_ANY_DESCENDANT_FROM_ROOT));
    if(isAbs)
    {
    	isAbs = m_absPathChecker.checkAbsolute(path);
    }
    return isAbs;
  }


  
Visit a LocationPath.

Params:
  • 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.
/**
   * Visit a LocationPath.
   * @param owner The owner of the expression, to which the expression can 
   *              be reset if rewriting takes place.
   * @param path The LocationPath object.
   * @return true if the sub expressions should be traversed.
   */
  public boolean visitLocationPath(ExpressionOwner owner, LocPathIterator path)
  {
  	// Don't optimize "." or single step variable paths.
  	// Both of these cases could use some further optimization by themselves.
  	if(path instanceof SelfIteratorNoPredicate)
  	{
  		return true;
  	}
  	else if(path instanceof WalkingIterator)
  	{
  		WalkingIterator wi = (WalkingIterator)path;
  		AxesWalker aw = wi.getFirstWalker();
  		if((aw instanceof FilterExprWalker) && (null == aw.getNextWalker()))
  		{
  			FilterExprWalker few = (FilterExprWalker)aw;
  			Expression exp = few.getInnerExpression();
  			if(exp instanceof Variable)
  				return true;
  		}
  	}

    if (isAbsolute(path) && (null != m_absPaths))
    {
      if(DEBUG)
        validateNewAddition(m_absPaths, owner, path);
      m_absPaths.addElement(owner);
    }
    else if (m_isSameContext && (null != m_paths))
    {
      if(DEBUG)
        validateNewAddition(m_paths, owner, path);
      m_paths.addElement(owner);
    }

    return true;
  }

  
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.

Params:
  • 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.
/**
   * 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.
   * 
   * @param owner The owner of the expression, to which the expression can 
   *              be reset if rewriting takes place.
   * @param pred The predicate object.
   * @return true if the sub expressions should be traversed.
   */
  public boolean visitPredicate(ExpressionOwner owner, Expression pred)
  {
    boolean savedIsSame = m_isSameContext;
    m_isSameContext = false;

    // Any further down, just collect the absolute paths.
    pred.callVisitors(owner, this);

    m_isSameContext = savedIsSame;

    // We've already gone down the subtree, so don't go have the caller 
    // go any further.
    return false;
  }
  
  
Visit an XSLT top-level instruction.

Params:
  • elem – The xsl instruction element object.
Returns:true if the sub expressions should be traversed.
/**
   * Visit an XSLT top-level instruction.
   * 
   * @param elem The xsl instruction element object.
   * @return true if the sub expressions should be traversed.
   */
   public boolean visitTopLevelInstruction(ElemTemplateElement elem)
   {
     int type = elem.getXSLToken();
     switch(type)
     {
       case Constants.ELEMNAME_TEMPLATE :
         return visitInstruction(elem);
       default:
         return true;
     }
   }


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

Params:
  • elem – The xsl instruction element object.
Returns:true if the sub expressions should be traversed.
/**
   * Visit an XSLT instruction.  Any element that isn't called by one 
   * of the other visit methods, will be called by this method.
   * 
   * @param elem The xsl instruction element object.
   * @return true if the sub expressions should be traversed.
   */
  public boolean visitInstruction(ElemTemplateElement elem)
  {
    int type = elem.getXSLToken();
    switch (type)
    {
      case Constants.ELEMNAME_CALLTEMPLATE :
      case Constants.ELEMNAME_TEMPLATE :
      case Constants.ELEMNAME_FOREACH :
        {
          
          // Just get the select value.
          if(type == Constants.ELEMNAME_FOREACH)
          {
            ElemForEach efe = (ElemForEach) elem;
   		    
  		    Expression select = efe.getSelect();
  		    select.callVisitors(efe, this);
          }
         
  		  Vector savedPaths = m_paths;
  		  m_paths = new Vector();
  		    
  		  // Visit children.  Call the superclass callChildVisitors, because 
  		  // we don't want to visit the xsl:for-each select attribute, or, for 
  		  // that matter, the xsl:template's match attribute.
  		  elem.callChildVisitors(this, false);  		
  		  eleminateRedundentLocals(elem);
  		    
  		  m_paths = savedPaths;
 
          // select.callVisitors(efe, this);
          return false;
        }
      case Constants.ELEMNAME_NUMBER :
      case Constants.ELEMNAME_SORT :
        // Just collect absolute paths until and unless we can fully
        // analyze these cases.
        boolean savedIsSame = m_isSameContext;
        m_isSameContext = false;
        elem.callChildVisitors(this);
        m_isSameContext = savedIsSame;
        return false;
        
      default :
        return true;
    }
  }
  
  // ==== DIAGNOSTIC AND DEBUG FUNCTIONS ====
  
  
Print out to std err the number of paths reduced.

/**
   * Print out to std err the number of paths reduced.
   */
  protected void diagnoseNumPaths(Vector paths, int numPathsEliminated,  
                                  int numUniquePathsEliminated) 
  {
		if (numPathsEliminated > 0)
		{ 
		  if(paths == m_paths)
		  {
		    System.err.println("Eliminated " + numPathsEliminated + " total paths!");
		    System.err.println(
		      "Consolodated " + numUniquePathsEliminated + " redundent paths!");
		  }
		  else
		  {
		    System.err.println("Eliminated " + numPathsEliminated + " total global paths!");
		    System.err.println(
		      "Consolodated " + numUniquePathsEliminated + " redundent global paths!");
		  }
		}  
  }


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

/**
   * Assert that the expression is a LocPathIterator, and, if 
   * not, try to give some diagnostic info.
   */
  private final void assertIsLocPathIterator(Expression expr1, ExpressionOwner eo) 
    throws RuntimeException 
  {
		if(!(expr1 instanceof LocPathIterator))
		{
			String errMsg;
			if(expr1 instanceof Variable)
			{
				errMsg = "Programmer's assertion: expr1 not an iterator: "+
				          ((Variable)expr1).getQName();
			}
			else
			{
				errMsg = "Programmer's assertion: expr1 not an iterator: "+
				          expr1.getClass().getName();
			}
			throw new RuntimeException(errMsg + ", "+
				          eo.getClass().getName()+" "+
				          expr1.exprGetParent());
		}
  }


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

/**
   * Validate some assumptions about the new LocPathIterator and it's 
   * owner and the state of the list.
   */
  private static void validateNewAddition(Vector paths, ExpressionOwner owner, 
                                          LocPathIterator path) 
		throws RuntimeException 
  {
  	assertion(owner.getExpression() == path, "owner.getExpression() != path!!!");
	int n = paths.size();
	// There should never be any duplicates in the list!
	for(int i = 0; i < n; i++)
	{
		ExpressionOwner ew = (ExpressionOwner)paths.elementAt(i);
		assertion(ew != owner, "duplicate owner on the list!!!");
		assertion(ew.getExpression() != path, "duplicate expression on the list!!!");
	}
  }
  
  
Simple assertion.

/**
   * Simple assertion.
   */
  protected static void assertion(boolean b, String msg)
  {
  	if(!b)
  	{
  		throw new RuntimeException(XSLMessages.createMessage(XSLTErrorResources.ER_ASSERT_REDUNDENT_EXPR_ELIMINATOR, new Object[]{msg}));
  		// "Programmer's assertion in RundundentExprEliminator: "+msg);
  	}
  }
  
  
Since we want to sort multistep expressions by length, use 
a linked list with elements of type MultistepExprHolder.

/**
   * Since we want to sort multistep expressions by length, use 
   * a linked list with elements of type MultistepExprHolder.
   */
  class MultistepExprHolder implements Cloneable
  {
	ExpressionOwner m_exprOwner; // Will change to null once we have processed this item.
	final int m_stepCount;
	MultistepExprHolder m_next;
	
	
Clone this object.

/**
	 * Clone this object.
	 */
	public Object clone()
		throws CloneNotSupportedException
	{
		return super.clone();
	}
	
	
Create a MultistepExprHolder.

Params:
  • exprOwner – the owner of the expression we are holding.
                 It must hold a LocationPathIterator.
  • stepCount – The number of steps in the location path.
/**
	 * Create a MultistepExprHolder.
	 * 
	 * @param exprOwner the owner of the expression we are holding.
	 *                  It must hold a LocationPathIterator.
	 * @param stepCount The number of steps in the location path.
	 */
  	MultistepExprHolder(ExpressionOwner exprOwner, int stepCount, MultistepExprHolder next)
  	{
  		m_exprOwner = exprOwner;
  		assertion(null != m_exprOwner, "exprOwner can not be null!");
  		m_stepCount = stepCount;
  		m_next = next;
  	}
	
	
Add a new MultistepExprHolder in sorted order in the list.

Params:
  • exprOwner – the owner of the expression we are holding.
                 It must hold a LocationPathIterator.
  • stepCount – The number of steps in the location path.
Returns:The new head of the linked list.
/**
	 * Add a new MultistepExprHolder in sorted order in the list.
	 * 
	 * @param exprOwner the owner of the expression we are holding.
	 *                  It must hold a LocationPathIterator.
	 * @param stepCount The number of steps in the location path.
	 * @return The new head of the linked list.
	 */
	MultistepExprHolder addInSortedOrder(ExpressionOwner exprOwner, int stepCount)
	{
		MultistepExprHolder first = this;
		MultistepExprHolder next = this;
		MultistepExprHolder prev = null;
		while(null != next)
		{
			if(stepCount >= next.m_stepCount)
			{
				MultistepExprHolder newholder = new MultistepExprHolder(exprOwner, stepCount, next);
				if(null == prev)
					first = newholder;
				else
					prev.m_next = newholder;
					
				return first;
			}
			prev = next;
			next = next.m_next;
		}
		
		prev.m_next = new MultistepExprHolder(exprOwner, stepCount, null);
		return first;
	}
	
	
Remove the given element from the list.  'this' should 
be the head of the list.  If the item to be removed is not 
found, an assertion will be made.

Params:
  • itemToRemove – The item to remove from the list.
Returns:The head of the list, which may have changed if itemToRemove 
is the same as this element.  Null if the item to remove is the 
only item in the list.
/**
	 * Remove the given element from the list.  'this' should 
	 * be the head of the list.  If the item to be removed is not 
	 * found, an assertion will be made.
	 * 
	 * @param itemToRemove The item to remove from the list.
	 * @return The head of the list, which may have changed if itemToRemove 
	 * is the same as this element.  Null if the item to remove is the 
	 * only item in the list.
	 */
	MultistepExprHolder unlink(MultistepExprHolder itemToRemove)
	{
		MultistepExprHolder first = this;
		MultistepExprHolder next = this;
		MultistepExprHolder prev = null;
		while(null != next)
		{
			if(next == itemToRemove)
			{
				if(null == prev)
					first = next.m_next;
				else
					prev.m_next = next.m_next;
				
				next.m_next = null;
					
				return first;
			}
			prev = next;
			next = next.m_next;
		}
		
		assertion(false, "unlink failed!!!");
		return null;
	}
		
	
Get the number of linked list items.

/**
	 * Get the number of linked list items.
	 */
	int getLength()
	{
		int count = 0;
		MultistepExprHolder next = this;
		while(null != next)
		{
			count++;
			next = next.m_next;
		}
		return count;
	}
	
    
Print diagnostics out for the multistep list.

/**
     * Print diagnostics out for the multistep list.
     */
    protected void diagnose()
    {
      System.err.print("Found multistep iterators: " + this.getLength() + "  ");
      MultistepExprHolder next = this;
      while (null != next)
      {
        System.err.print("" + next.m_stepCount);
        next = next.m_next;
        if (null != next)
              System.err.print(", ");
      }
      System.err.println();
    }
	
  }

}