/*
 * The Apache Software License, Version 1.1
 *
 *
 * Copyright (c) 2002-2003 The Apache Software Foundation.  All rights 
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer. 
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:  
 *       "This product includes software developed by the
 *        Apache Software Foundation (http://www.apache.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Xalan" and "Apache Software Foundation" must
 *    not be used to endorse or promote products derived from this
 *    software without prior written permission. For written 
 *    permission, please contact apache@apache.org.
 *
 * 5. Products derived from this software may not be called "Apache",
 *    nor may "Apache" appear in their name, without prior written
 *    permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation and was
 * originally based on software copyright (c) 1999, Lotus
 * Development Corporation., http://www.lotus.com.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 */
package org.apache.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;
import org.w3c.dom.DOMException;

/**
 * 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();
  
  static int m_uniquePsuedoVarID = 1;
  static final String PSUEDOVARNAMESPACE = Constants.S_VENDORURL+"/xalan/psuedovar";
 
  public static boolean DEBUG = false;
  public static boolean DIAGNOSE_NUM_PATHS_REDUCED = false;
  public static boolean DIAGNOSE_MULTISTEPLIST = false;

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

  /**
   * Construct a RedundentExprEliminator.
   * 
   * @param absPathsList Vector to which absolute paths will 
   * be inserted.  The vector may be null, if the caller does 
   * not wish to collect absolute paths.
   */
  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.
   * 
   * @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.
   * 
   * @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 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.
   * 
   * @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.
   * 
   * @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.
   * 
   * @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 = createPsuedoVarDecl(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.
   */
  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.
   */
  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.
   */
  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.
   * 
   * @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.
   * 
   * @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.
   */
  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.
   * 
   * @param uniquePsuedoVarName 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 uniquePsuedoVarName, WalkingIterator wi, 
                                 final int numSteps, final boolean isGlobal)
  {
  	Variable var = new Variable();
  	var.setQName(uniquePsuedoVarName);
  	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.
   * 
   * @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.
   * 
   * @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.
   * 
   * @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.
   * 
   * @param start The position to start looking in the vector.
   * @param targetIndex 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 = createPsuedoVarDecl(root, sharedIter, isGlobal);
		if(DIAGNOSE_MULTISTEPLIST)
			System.err.println("Created var: "+var.getName()+(isGlobal ? "(Global)" : ""));
		QName uniquePsuedoVarName = var.getName();
		while(null != head)
		{
			ExpressionOwner owner = head.m_exprOwner;	
			if(DIAGNOSE_MULTISTEPLIST)
				diagnoseLineNumber(owner.getExpression());
			changeToVarRef(uniquePsuedoVarName, 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.
   */
  protected int oldFindAndEliminateRedundant(int start, int firstOccuranceIndex,
                         ExpressionOwner firstOccuranceOwner, 
                         ElemTemplateElement psuedoVarRecipient,
                         Vector paths) 
                 throws org.w3c.dom.DOMException 
  {
	QName uniquePsuedoVarName = 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 = createPsuedoVarDecl(psuedoVarRecipient, lpi, isGlobal);
				    if(null == var)
				    	return 0;
				    uniquePsuedoVarName = var.getName();
	
					changeToVarRef(uniquePsuedoVarName, 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(uniquePsuedoVarName, 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 = createPsuedoVarDecl(psuedoVarRecipient, lpi, true);
      if(null == var)
        return 0;
	  uniquePsuedoVarName = var.getName();
      changeToVarRef(uniquePsuedoVarName, firstOccuranceOwner, paths, psuedoVarRecipient);
      paths.setElementAt(var.getSelect(), firstOccuranceIndex);
      numPathsFound++;
	}
	return numPathsFound;
  }
  
  /**
   * 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.
   * 
   * @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);
  }

  /**
   * 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 createPsuedoVarDecl(
      ElemTemplateElement psuedoVarRecipient,
      LocPathIterator lpi, boolean isGlobal)
      throws org.w3c.dom.DOMException
  {
    QName uniquePsuedoVarName = new QName (PSUEDOVARNAMESPACE, "#"+m_uniquePsuedoVarID);
    m_uniquePsuedoVarID++;
  		
  	if(isGlobal)
  	{
  	  return createGlobalPsuedoVarDecl(uniquePsuedoVarName, 
  	                                  (StylesheetRoot)psuedoVarRecipient, lpi);
  	}
  	else						
      return createLocalPsuedoVarDecl(uniquePsuedoVarName, psuedoVarRecipient, lpi);
  }
  
  /**
   * Create a psuedo variable reference that will represent the 
   * shared redundent XPath, for a local reduction.
   * 
   * @param uniquePsuedoVarName 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 Psuedo var  
   *              element.
   */
  protected ElemVariable createGlobalPsuedoVarDecl(QName uniquePsuedoVarName,
                                           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(uniquePsuedoVarName);
	
	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.
   * 
   * @param uniquePsuedoVarName 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.
   * @param addToContext true if the decl should be added to psuedoVarRecipient.
   * @return null if the decl was not created, otherwise the new Psuedo var  
   *              element.
   */
  protected ElemVariable createLocalPsuedoVarDecl(QName uniquePsuedoVarName,
                                           ElemTemplateElement psuedoVarRecipient, 
                                           LocPathIterator lpi) 
        throws org.w3c.dom.DOMException 
  {
		ElemVariable psuedoVar = new ElemVariablePsuedo();
		
		XPath xpath = new XPath(lpi);
		psuedoVar.setSelect(xpath);
		psuedoVar.setName(uniquePsuedoVarName);

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

  /**
   * 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.
   */
  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.
   * 
   * @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.
   * 
   * @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.
   * 
   * @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.
   * 
   * @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.
   * @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.
   * 
   * @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.
   * 
   * @param elem The xsl instruction element object.
   * @return true if the sub expressions should be traversed.
   */
   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.
   * 
   * @param elem The xsl instruction element object.
   * @return true if the sub expressions should be traversed.
   */
  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.
   */
  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.
   */
  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.
   */
  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.
   */
  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.
   */
  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.
	 */
	public Object clone()
		throws CloneNotSupportedException
	{
		return super.clone();
	}
	
	/**
	 * 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.
	 * 
	 * @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.
	 * 
	 * @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.
	 */
	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.
     */
    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();
    }
	
  }

}