| /* |
| * 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. |
| */ |
| 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. |
| */ |
| VarNameCollector m_varNameCollector = new VarNameCollector(); |
| |
| /** |
| * 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. |
| * |
| * @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. |
| * |
| */ |
| 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 = 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. |
| */ |
| 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 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. |
| * |
| * @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 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. |
| */ |
| 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. |
| * |
| * @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); |
| } |
| |
| 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. |
| * |
| * @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. |
| * |
| * @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. |
| * |
| * @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. |
| */ |
| 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. |
| */ |
| 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. |
| * |
| * @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. |
| */ |
| 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(); |
| } |
| |
| } |
| |
| } |