redundentexpreliminator.java

来自「java jdk 1.4的源码」· Java 代码 · 共 1,474 行 · 第 1/4 页

/*
 * The Apache Software License, Version 1.1
 *
 *
 * Copyright (c) 2002 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 [e-mail].
 *
 * 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;