001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the "License");
007 * you may not use this file except in compliance with the License.
008 * You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018 /*
019 * $Id: RedundentExprEliminator.java 468643 2006-10-28 06:56:03Z minchau $
020 */
021 package org.apache.xalan.templates;
022
023 import java.util.Vector;
024
025 import org.apache.xalan.res.XSLMessages;
026 import org.apache.xalan.res.XSLTErrorResources;
027 import org.apache.xml.utils.QName;
028 import org.apache.xml.utils.WrappedRuntimeException;
029 import org.apache.xpath.Expression;
030 import org.apache.xpath.ExpressionNode;
031 import org.apache.xpath.ExpressionOwner;
032 import org.apache.xpath.XPath;
033 import org.apache.xpath.axes.AxesWalker;
034 import org.apache.xpath.axes.FilterExprIteratorSimple;
035 import org.apache.xpath.axes.FilterExprWalker;
036 import org.apache.xpath.axes.LocPathIterator;
037 import org.apache.xpath.axes.SelfIteratorNoPredicate;
038 import org.apache.xpath.axes.WalkerFactory;
039 import org.apache.xpath.axes.WalkingIterator;
040 import org.apache.xpath.operations.Variable;
041 import org.apache.xpath.operations.VariableSafeAbsRef;
042
043 /**
044 * This class eleminates redundent XPaths from a given subtree,
045 * and also collects all absolute paths within the subtree. First
046 * it must be called as a visitor to the subtree, and then
047 * eleminateRedundent must be called.
048 */
049 public class RedundentExprEliminator extends XSLTVisitor
050 {
051 Vector m_paths;
052 Vector m_absPaths;
053 boolean m_isSameContext;
054 AbsPathChecker m_absPathChecker = new AbsPathChecker();
055
056 private static int m_uniquePseudoVarID = 1;
057 static final String PSUEDOVARNAMESPACE = Constants.S_VENDORURL+"/xalan/psuedovar";
058
059 public static final boolean DEBUG = false;
060 public static final boolean DIAGNOSE_NUM_PATHS_REDUCED = false;
061 public static final boolean DIAGNOSE_MULTISTEPLIST = false;
062
063 /**
064 * So we can reuse it over and over again.
065 */
066 VarNameCollector m_varNameCollector = new VarNameCollector();
067
068 /**
069 * Construct a RedundentExprEliminator.
070 */
071 public RedundentExprEliminator()
072 {
073 m_isSameContext = true;
074 m_absPaths = new Vector();
075 m_paths = null;
076 }
077
078
079 /**
080 * Method to be called after the all expressions within an
081 * node context have been visited. It eliminates redundent
082 * expressions by creating a variable in the psuedoVarRecipient
083 * for each redundent expression, and then rewriting the redundent
084 * expression to be a variable reference.
085 *
086 * @param psuedoVarRecipient The recipient of the psuedo vars. The
087 * variables will be inserted as first children of the element, before
088 * any existing variables.
089 */
090 public void eleminateRedundentLocals(ElemTemplateElement psuedoVarRecipient)
091 {
092 eleminateRedundent(psuedoVarRecipient, m_paths);
093 }
094
095 /**
096 * Method to be called after the all global expressions within a stylesheet
097 * have been collected. It eliminates redundent
098 * expressions by creating a variable in the psuedoVarRecipient
099 * for each redundent expression, and then rewriting the redundent
100 * expression to be a variable reference.
101 *
102 */
103 public void eleminateRedundentGlobals(StylesheetRoot stylesheet)
104 {
105 eleminateRedundent(stylesheet, m_absPaths);
106 }
107
108
109 /**
110 * Method to be called after the all expressions within an
111 * node context have been visited. It eliminates redundent
112 * expressions by creating a variable in the psuedoVarRecipient
113 * for each redundent expression, and then rewriting the redundent
114 * expression to be a variable reference.
115 *
116 * @param psuedoVarRecipient The owner of the subtree from where the
117 * paths were collected.
118 * @param paths A vector of paths that hold ExpressionOwner objects,
119 * which must yield LocationPathIterators.
120 */
121 protected void eleminateRedundent(ElemTemplateElement psuedoVarRecipient, Vector paths)
122 {
123 int n = paths.size();
124 int numPathsEliminated = 0;
125 int numUniquePathsEliminated = 0;
126 for (int i = 0; i < n; i++)
127 {
128 ExpressionOwner owner = (ExpressionOwner) paths.elementAt(i);
129 if (null != owner)
130 {
131 int found = findAndEliminateRedundant(i + 1, i, owner, psuedoVarRecipient, paths);
132 if (found > 0)
133 numUniquePathsEliminated++;
134 numPathsEliminated += found;
135 }
136 }
137
138 eleminateSharedPartialPaths(psuedoVarRecipient, paths);
139
140 if(DIAGNOSE_NUM_PATHS_REDUCED)
141 diagnoseNumPaths(paths, numPathsEliminated, numUniquePathsEliminated);
142 }
143
144 /**
145 * Eliminate the shared partial paths in the expression list.
146 *
147 * @param psuedoVarRecipient The recipient of the psuedo vars.
148 *
149 * @param paths A vector of paths that hold ExpressionOwner objects,
150 * which must yield LocationPathIterators.
151 */
152 protected void eleminateSharedPartialPaths(ElemTemplateElement psuedoVarRecipient, Vector paths)
153 {
154 MultistepExprHolder list = createMultistepExprList(paths);
155 if(null != list)
156 {
157 if(DIAGNOSE_MULTISTEPLIST)
158 list.diagnose();
159
160 boolean isGlobal = (paths == m_absPaths);
161
162 // Iterate over the list, starting with the most number of paths,
163 // trying to find the longest matches first.
164 int longestStepsCount = list.m_stepCount;
165 for (int i = longestStepsCount-1; i >= 1; i--)
166 {
167 MultistepExprHolder next = list;
168 while(null != next)
169 {
170 if(next.m_stepCount < i)
171 break;
172 list = matchAndEliminatePartialPaths(next, list, isGlobal, i, psuedoVarRecipient);
173 next = next.m_next;
174 }
175 }
176 }
177 }
178
179 /**
180 * For a given path, see if there are any partitial matches in the list,
181 * and, if there are, replace those partial paths with psuedo variable refs,
182 * and create the psuedo variable decl.
183 *
184 * @return The head of the list, which may have changed.
185 */
186 protected MultistepExprHolder matchAndEliminatePartialPaths(MultistepExprHolder testee,
187 MultistepExprHolder head,
188 boolean isGlobal,
189 int lengthToTest,
190 ElemTemplateElement varScope)
191 {
192 if(null == testee.m_exprOwner)
193 return head;
194
195 // Start with the longest possible match, and move down.
196 WalkingIterator iter1 = (WalkingIterator) testee.m_exprOwner.getExpression();
197 if(partialIsVariable(testee, lengthToTest))
198 return head;
199 MultistepExprHolder matchedPaths = null;
200 MultistepExprHolder matchedPathsTail = null;
201 MultistepExprHolder meh = head;
202 while( null != meh)
203 {
204 if ((meh != testee) && (null != meh.m_exprOwner))
205 {
206 WalkingIterator iter2 = (WalkingIterator) meh.m_exprOwner.getExpression();
207 if (stepsEqual(iter1, iter2, lengthToTest))
208 {
209 if (null == matchedPaths)
210 {
211 try
212 {
213 matchedPaths = (MultistepExprHolder)testee.clone();
214 testee.m_exprOwner = null; // So it won't be processed again.
215 }
216 catch(CloneNotSupportedException cnse){}
217 matchedPathsTail = matchedPaths;
218 matchedPathsTail.m_next = null;
219 }
220
221 try
222 {
223 matchedPathsTail.m_next = (MultistepExprHolder)meh.clone();
224 meh.m_exprOwner = null; // So it won't be processed again.
225 }
226 catch(CloneNotSupportedException cnse){}
227 matchedPathsTail = matchedPathsTail.m_next;
228 matchedPathsTail.m_next = null;
229 }
230 }
231 meh = meh.m_next;
232 }
233
234 int matchCount = 0;
235 if(null != matchedPaths)
236 {
237 ElemTemplateElement root = isGlobal ? varScope : findCommonAncestor(matchedPaths);
238 WalkingIterator sharedIter = (WalkingIterator)matchedPaths.m_exprOwner.getExpression();
239 WalkingIterator newIter = createIteratorFromSteps(sharedIter, lengthToTest);
240 ElemVariable var = createPseudoVarDecl(root, newIter, isGlobal);
241 if(DIAGNOSE_MULTISTEPLIST)
242 System.err.println("Created var: "+var.getName()+(isGlobal ? "(Global)" : ""));
243 while(null != matchedPaths)
244 {
245 ExpressionOwner owner = matchedPaths.m_exprOwner;
246 WalkingIterator iter = (WalkingIterator)owner.getExpression();
247
248 if(DIAGNOSE_MULTISTEPLIST)
249 diagnoseLineNumber(iter);
250
251 LocPathIterator newIter2 =
252 changePartToRef(var.getName(), iter, lengthToTest, isGlobal);
253 owner.setExpression(newIter2);
254
255 matchedPaths = matchedPaths.m_next;
256 }
257 }
258
259 if(DIAGNOSE_MULTISTEPLIST)
260 diagnoseMultistepList(matchCount, lengthToTest, isGlobal);
261 return head;
262 }
263
264 /**
265 * Check if results of partial reduction will just be a variable, in
266 * which case, skip it.
267 */
268 boolean partialIsVariable(MultistepExprHolder testee, int lengthToTest)
269 {
270 if(1 == lengthToTest)
271 {
272 WalkingIterator wi = (WalkingIterator)testee.m_exprOwner.getExpression();
273 if(wi.getFirstWalker() instanceof FilterExprWalker)
274 return true;
275 }
276 return false;
277 }
278
279 /**
280 * Tell what line number belongs to a given expression.
281 */
282 protected void diagnoseLineNumber(Expression expr)
283 {
284 ElemTemplateElement e = getElemFromExpression(expr);
285 System.err.println(" " + e.getSystemId() + " Line " + e.getLineNumber());
286 }
287
288 /**
289 * Given a linked list of expressions, find the common ancestor that is
290 * suitable for holding a psuedo variable for shared access.
291 */
292 protected ElemTemplateElement findCommonAncestor(MultistepExprHolder head)
293 {
294 // Not sure this algorithm is the best, but will do for the moment.
295 int numExprs = head.getLength();
296 // The following could be made cheaper by pre-allocating large arrays,
297 // but then we would have to assume a max number of reductions,
298 // which I am not inclined to do right now.
299 ElemTemplateElement[] elems = new ElemTemplateElement[numExprs];
300 int[] ancestorCounts = new int[numExprs];
301
302 // Loop through, getting the parent elements, and counting the
303 // ancestors.
304 MultistepExprHolder next = head;
305 int shortestAncestorCount = 10000;
306 for(int i = 0; i < numExprs; i++)
307 {
308 ElemTemplateElement elem =
309 getElemFromExpression(next.m_exprOwner.getExpression());
310 elems[i] = elem;
311 int numAncestors = countAncestors(elem);
312 ancestorCounts[i] = numAncestors;
313 if(numAncestors < shortestAncestorCount)
314 {
315 shortestAncestorCount = numAncestors;
316 }
317 next = next.m_next;
318 }
319
320 // Now loop through and "correct" the elements that have more ancestors.
321 for(int i = 0; i < numExprs; i++)
322 {
323 if(ancestorCounts[i] > shortestAncestorCount)
324 {
325 int numStepCorrection = ancestorCounts[i] - shortestAncestorCount;
326 for(int j = 0; j < numStepCorrection; j++)
327 {
328 elems[i] = elems[i].getParentElem();
329 }
330 }
331 }
332
333 // Now everyone has an equal number of ancestors. Walk up from here
334 // equally until all are equal.
335 ElemTemplateElement first = null;
336 while(shortestAncestorCount-- >= 0)
337 {
338 boolean areEqual = true;
339 first = elems[0];
340 for(int i = 1; i < numExprs; i++)
341 {
342 if(first != elems[i])
343 {
344 areEqual = false;
345 break;
346 }
347 }
348 // This second check is to make sure we have a common ancestor that is not the same
349 // as the expression owner... i.e. the var decl has to go above the expression owner.
350 if(areEqual && isNotSameAsOwner(head, first) && first.canAcceptVariables())
351 {
352 if(DIAGNOSE_MULTISTEPLIST)
353 {
354 System.err.print(first.getClass().getName());
355 System.err.println(" at " + first.getSystemId() + " Line " + first.getLineNumber());
356 }
357 return first;
358 }
359
360 for(int i = 0; i < numExprs; i++)
361 {
362 elems[i] = elems[i].getParentElem();
363 }
364 }
365
366 assertion(false, "Could not find common ancestor!!!");
367 return null;
368 }
369
370 /**
371 * Find out if the given ElemTemplateElement is not the same as one of
372 * the ElemTemplateElement owners of the expressions.
373 *
374 * @param head Head of linked list of expression owners.
375 * @param ete The ElemTemplateElement that is a candidate for a psuedo
376 * variable parent.
377 * @return true if the given ElemTemplateElement is not the same as one of
378 * the ElemTemplateElement owners of the expressions. This is to make sure
379 * we find an ElemTemplateElement that is in a viable position to hold
380 * psuedo variables that are visible to the references.
381 */
382 protected boolean isNotSameAsOwner(MultistepExprHolder head, ElemTemplateElement ete)
383 {
384 MultistepExprHolder next = head;
385 while(null != next)
386 {
387 ElemTemplateElement elemOwner = getElemFromExpression(next.m_exprOwner.getExpression());
388 if(elemOwner == ete)
389 return false;
390 next = next.m_next;
391 }
392 return true;
393 }
394
395 /**
396 * Count the number of ancestors that a ElemTemplateElement has.
397 *
398 * @param elem An representation of an element in an XSLT stylesheet.
399 * @return The number of ancestors of elem (including the element itself).
400 */
401 protected int countAncestors(ElemTemplateElement elem)
402 {
403 int count = 0;
404 while(null != elem)
405 {
406 count++;
407 elem = elem.getParentElem();
408 }
409 return count;
410 }
411
412 /**
413 * Print out diagnostics about partial multistep evaluation.
414 */
415 protected void diagnoseMultistepList(
416 int matchCount,
417 int lengthToTest,
418 boolean isGlobal)
419 {
420 if (matchCount > 0)
421 {
422 System.err.print(
423 "Found multistep matches: " + matchCount + ", " + lengthToTest + " length");
424 if (isGlobal)
425 System.err.println(" (global)");
426 else
427 System.err.println();
428 }
429 }
430
431 /**
432 * Change a given number of steps to a single variable reference.
433 *
434 * @param uniquePseudoVarName The name of the variable reference.
435 * @param wi The walking iterator that is to be changed.
436 * @param numSteps The number of steps to be changed.
437 * @param isGlobal true if this will be a global reference.
438 */
439 protected LocPathIterator changePartToRef(final QName uniquePseudoVarName, WalkingIterator wi,
440 final int numSteps, final boolean isGlobal)
441 {
442 Variable var = new Variable();
443 var.setQName(uniquePseudoVarName);
444 var.setIsGlobal(isGlobal);
445 if(isGlobal)
446 { ElemTemplateElement elem = getElemFromExpression(wi);
447 StylesheetRoot root = elem.getStylesheetRoot();
448 Vector vars = root.getVariablesAndParamsComposed();
449 var.setIndex(vars.size()-1);
450 }
451
452 // Walk to the first walker after the one's we are replacing.
453 AxesWalker walker = wi.getFirstWalker();
454 for(int i = 0; i < numSteps; i++)
455 {
456 assertion(null != walker, "Walker should not be null!");
457 walker = walker.getNextWalker();
458 }
459
460 if(null != walker)
461 {
462
463 FilterExprWalker few = new FilterExprWalker(wi);
464 few.setInnerExpression(var);
465 few.exprSetParent(wi);
466 few.setNextWalker(walker);
467 walker.setPrevWalker(few);
468 wi.setFirstWalker(few);
469 return wi;
470 }
471 else
472 {
473 FilterExprIteratorSimple feis = new FilterExprIteratorSimple(var);
474 feis.exprSetParent(wi.exprGetParent());
475 return feis;
476 }
477 }
478
479 /**
480 * Create a new WalkingIterator from the steps in another WalkingIterator.
481 *
482 * @param wi The iterator from where the steps will be taken.
483 * @param numSteps The number of steps from the first to copy into the new
484 * iterator.
485 * @return The new iterator.
486 */
487 protected WalkingIterator createIteratorFromSteps(final WalkingIterator wi, int numSteps)
488 {
489 WalkingIterator newIter = new WalkingIterator(wi.getPrefixResolver());
490 try
491 {
492 AxesWalker walker = (AxesWalker)wi.getFirstWalker().clone();
493 newIter.setFirstWalker(walker);
494 walker.setLocPathIterator(newIter);
495 for(int i = 1; i < numSteps; i++)
496 {
497 AxesWalker next = (AxesWalker)walker.getNextWalker().clone();
498 walker.setNextWalker(next);
499 next.setLocPathIterator(newIter);
500 walker = next;
501 }
502 walker.setNextWalker(null);
503 }
504 catch(CloneNotSupportedException cnse)
505 {
506 throw new WrappedRuntimeException(cnse);
507 }
508 return newIter;
509 }
510
511 /**
512 * Compare a given number of steps between two iterators, to see if they are equal.
513 *
514 * @param iter1 The first iterator to compare.
515 * @param iter2 The second iterator to compare.
516 * @param numSteps The number of steps to compare.
517 * @return true If the given number of steps are equal.
518 *
519 */
520 protected boolean stepsEqual(WalkingIterator iter1, WalkingIterator iter2,
521 int numSteps)
522 {
523 AxesWalker aw1 = iter1.getFirstWalker();
524 AxesWalker aw2 = iter2.getFirstWalker();
525
526 for(int i = 0; (i < numSteps); i++)
527 {
528 if((null == aw1) || (null == aw2))
529 return false;
530
531 if(!aw1.deepEquals(aw2))
532 return false;
533
534 aw1 = aw1.getNextWalker();
535 aw2 = aw2.getNextWalker();
536 }
537
538 assertion((null != aw1) || (null != aw2), "Total match is incorrect!");
539
540 return true;
541 }
542
543 /**
544 * For the reduction of location path parts, create a list of all
545 * the multistep paths with more than one step, sorted by the
546 * number of steps, with the most steps occuring earlier in the list.
547 * If the list is only one member, don't bother returning it.
548 *
549 * @param paths Vector of ExpressionOwner objects, which may contain null entries.
550 * The ExpressionOwner objects must own LocPathIterator objects.
551 * @return null if no multipart paths are found or the list is only of length 1,
552 * otherwise the first MultistepExprHolder in a linked list of these objects.
553 */
554 protected MultistepExprHolder createMultistepExprList(Vector paths)
555 {
556 MultistepExprHolder first = null;
557 int n = paths.size();
558 for(int i = 0; i < n; i++)
559 {
560 ExpressionOwner eo = (ExpressionOwner)paths.elementAt(i);
561 if(null == eo)
562 continue;
563
564 // Assuming location path iterators should be OK.
565 LocPathIterator lpi = (LocPathIterator)eo.getExpression();
566 int numPaths = countSteps(lpi);
567 if(numPaths > 1)
568 {
569 if(null == first)
570 first = new MultistepExprHolder(eo, numPaths, null);
571 else
572 first = first.addInSortedOrder(eo, numPaths);
573 }
574 }
575
576 if((null == first) || (first.getLength() <= 1))
577 return null;
578 else
579 return first;
580 }
581
582 /**
583 * Look through the vector from start point, looking for redundant occurances.
584 * When one or more are found, create a psuedo variable declaration, insert
585 * it into the stylesheet, and replace the occurance with a reference to
586 * the psuedo variable. When a redundent variable is found, it's slot in
587 * the vector will be replaced by null.
588 *
589 * @param start The position to start looking in the vector.
590 * @param firstOccuranceIndex The position of firstOccuranceOwner.
591 * @param firstOccuranceOwner The owner of the expression we are looking for.
592 * @param psuedoVarRecipient Where to put the psuedo variables.
593 *
594 * @return The number of expression occurances that were modified.
595 */
596 protected int findAndEliminateRedundant(int start, int firstOccuranceIndex,
597 ExpressionOwner firstOccuranceOwner,
598 ElemTemplateElement psuedoVarRecipient,
599 Vector paths)
600 throws org.w3c.dom.DOMException
601 {
602 MultistepExprHolder head = null;
603 MultistepExprHolder tail = null;
604 int numPathsFound = 0;
605 int n = paths.size();
606
607 Expression expr1 = firstOccuranceOwner.getExpression();
608 if(DEBUG)
609 assertIsLocPathIterator(expr1, firstOccuranceOwner);
610 boolean isGlobal = (paths == m_absPaths);
611 LocPathIterator lpi = (LocPathIterator)expr1;
612 int stepCount = countSteps(lpi);
613 for(int j = start; j < n; j++)
614 {
615 ExpressionOwner owner2 = (ExpressionOwner)paths.elementAt(j);
616 if(null != owner2)
617 {
618 Expression expr2 = owner2.getExpression();
619 boolean isEqual = expr2.deepEquals(lpi);
620 if(isEqual)
621 {
622 LocPathIterator lpi2 = (LocPathIterator)expr2;
623 if(null == head)
624 {
625 head = new MultistepExprHolder(firstOccuranceOwner, stepCount, null);
626 tail = head;
627 numPathsFound++;
628 }
629 tail.m_next = new MultistepExprHolder(owner2, stepCount, null);
630 tail = tail.m_next;
631
632 // Null out the occurance, so we don't have to test it again.
633 paths.setElementAt(null, j);
634
635 // foundFirst = true;
636 numPathsFound++;
637 }
638 }
639 }
640
641 // Change all globals in xsl:templates, etc, to global vars no matter what.
642 if((0 == numPathsFound) && isGlobal)
643 {
644 head = new MultistepExprHolder(firstOccuranceOwner, stepCount, null);
645 numPathsFound++;
646 }
647
648 if(null != head)
649 {
650 ElemTemplateElement root = isGlobal ? psuedoVarRecipient : findCommonAncestor(head);
651 LocPathIterator sharedIter = (LocPathIterator)head.m_exprOwner.getExpression();
652 ElemVariable var = createPseudoVarDecl(root, sharedIter, isGlobal);
653 if(DIAGNOSE_MULTISTEPLIST)
654 System.err.println("Created var: "+var.getName()+(isGlobal ? "(Global)" : ""));
655 QName uniquePseudoVarName = var.getName();
656 while(null != head)
657 {
658 ExpressionOwner owner = head.m_exprOwner;
659 if(DIAGNOSE_MULTISTEPLIST)
660 diagnoseLineNumber(owner.getExpression());
661 changeToVarRef(uniquePseudoVarName, owner, paths, root);
662 head = head.m_next;
663 }
664 // Replace the first occurance with the variable's XPath, so
665 // that further reduction may take place if needed.
666 paths.setElementAt(var.getSelect(), firstOccuranceIndex);
667 }
668
669 return numPathsFound;
670 }
671
672 /**
673 * To be removed.
674 */
675 protected int oldFindAndEliminateRedundant(int start, int firstOccuranceIndex,
676 ExpressionOwner firstOccuranceOwner,
677 ElemTemplateElement psuedoVarRecipient,
678 Vector paths)
679 throws org.w3c.dom.DOMException
680 {
681 QName uniquePseudoVarName = null;
682 boolean foundFirst = false;
683 int numPathsFound = 0;
684 int n = paths.size();
685 Expression expr1 = firstOccuranceOwner.getExpression();
686 if(DEBUG)
687 assertIsLocPathIterator(expr1, firstOccuranceOwner);
688 boolean isGlobal = (paths == m_absPaths);
689 LocPathIterator lpi = (LocPathIterator)expr1;
690 for(int j = start; j < n; j++)
691 {
692 ExpressionOwner owner2 = (ExpressionOwner)paths.elementAt(j);
693 if(null != owner2)
694 {
695 Expression expr2 = owner2.getExpression();
696 boolean isEqual = expr2.deepEquals(lpi);
697 if(isEqual)
698 {
699 LocPathIterator lpi2 = (LocPathIterator)expr2;
700 if(!foundFirst)
701 {
702 foundFirst = true;
703 // Insert variable decl into psuedoVarRecipient
704 // We want to insert this into the first legitimate
705 // position for a variable.
706 ElemVariable var = createPseudoVarDecl(psuedoVarRecipient, lpi, isGlobal);
707 if(null == var)
708 return 0;
709 uniquePseudoVarName = var.getName();
710
711 changeToVarRef(uniquePseudoVarName, firstOccuranceOwner,
712 paths, psuedoVarRecipient);
713
714 // Replace the first occurance with the variable's XPath, so
715 // that further reduction may take place if needed.
716 paths.setElementAt(var.getSelect(), firstOccuranceIndex);
717 numPathsFound++;
718 }
719
720 changeToVarRef(uniquePseudoVarName, owner2, paths, psuedoVarRecipient);
721
722 // Null out the occurance, so we don't have to test it again.
723 paths.setElementAt(null, j);
724
725 // foundFirst = true;
726 numPathsFound++;
727 }
728 }
729 }
730
731 // Change all globals in xsl:templates, etc, to global vars no matter what.
732 if((0 == numPathsFound) && (paths == m_absPaths))
733 {
734 ElemVariable var = createPseudoVarDecl(psuedoVarRecipient, lpi, true);
735 if(null == var)
736 return 0;
737 uniquePseudoVarName = var.getName();
738 changeToVarRef(uniquePseudoVarName, firstOccuranceOwner, paths, psuedoVarRecipient);
739 paths.setElementAt(var.getSelect(), firstOccuranceIndex);
740 numPathsFound++;
741 }
742 return numPathsFound;
743 }
744
745 /**
746 * Count the steps in a given location path.
747 *
748 * @param lpi The location path iterator that owns the steps.
749 * @return The number of steps in the given location path.
750 */
751 protected int countSteps(LocPathIterator lpi)
752 {
753 if(lpi instanceof WalkingIterator)
754 {
755 WalkingIterator wi = (WalkingIterator)lpi;
756 AxesWalker aw = wi.getFirstWalker();
757 int count = 0;
758 while(null != aw)
759 {
760 count++;
761 aw = aw.getNextWalker();
762 }
763 return count;
764 }
765 else
766 return 1;
767 }
768
769 /**
770 * Change the expression owned by the owner argument to a variable reference
771 * of the given name.
772 *
773 * Warning: For global vars, this function relies on the variable declaration
774 * to which it refers having been added just prior to this function being called,
775 * so that the reference index can be determined from the size of the global variables
776 * list minus one.
777 *
778 * @param varName The name of the variable which will be referenced.
779 * @param owner The owner of the expression which will be replaced by a variable ref.
780 * @param paths The paths list that the iterator came from, mainly to determine
781 * if this is a local or global reduction.
782 * @param psuedoVarRecipient The element within whose scope the variable is
783 * being inserted, possibly a StylesheetRoot.
784 */
785 protected void changeToVarRef(QName varName, ExpressionOwner owner,
786 Vector paths, ElemTemplateElement psuedoVarRecipient)
787 {
788 Variable varRef = (paths == m_absPaths) ? new VariableSafeAbsRef() : new Variable();
789 varRef.setQName(varName);
790 if(paths == m_absPaths)
791 {
792 StylesheetRoot root = (StylesheetRoot)psuedoVarRecipient;
793 Vector globalVars = root.getVariablesAndParamsComposed();
794 // Assume this operation is occuring just after the decl has
795 // been added.
796 varRef.setIndex(globalVars.size()-1);
797 varRef.setIsGlobal(true);
798 }
799 owner.setExpression(varRef);
800 }
801
802 private synchronized static int getPseudoVarID(){
803 return m_uniquePseudoVarID++;
804 }
805
806 /**
807 * Create a psuedo variable reference that will represent the
808 * shared redundent XPath, and add it to the stylesheet.
809 *
810 * @param psuedoVarRecipient The broadest scope of where the variable
811 * should be inserted, usually an xsl:template or xsl:for-each.
812 * @param lpi The LocationPathIterator that the variable should represent.
813 * @param isGlobal true if the paths are global.
814 * @return The new psuedo var element.
815 */
816 protected ElemVariable createPseudoVarDecl(
817 ElemTemplateElement psuedoVarRecipient,
818 LocPathIterator lpi, boolean isGlobal)
819 throws org.w3c.dom.DOMException
820 {
821 QName uniquePseudoVarName = new QName (PSUEDOVARNAMESPACE, "#"+getPseudoVarID());
822
823 if(isGlobal)
824 {
825 return createGlobalPseudoVarDecl(uniquePseudoVarName,
826 (StylesheetRoot)psuedoVarRecipient, lpi);
827 }
828 else
829 return createLocalPseudoVarDecl(uniquePseudoVarName, psuedoVarRecipient, lpi);
830 }
831
832 /**
833 * Create a psuedo variable reference that will represent the
834 * shared redundent XPath, for a local reduction.
835 *
836 * @param uniquePseudoVarName The name of the new variable.
837 * @param stylesheetRoot The broadest scope of where the variable
838 * should be inserted, which must be a StylesheetRoot element in this case.
839 * @param lpi The LocationPathIterator that the variable should represent.
840 * @return null if the decl was not created, otherwise the new Pseudo var
841 * element.
842 */
843 protected ElemVariable createGlobalPseudoVarDecl(QName uniquePseudoVarName,
844 StylesheetRoot stylesheetRoot,
845 LocPathIterator lpi)
846 throws org.w3c.dom.DOMException
847 {
848 ElemVariable psuedoVar = new ElemVariable();
849 psuedoVar.setIsTopLevel(true);
850 XPath xpath = new XPath(lpi);
851 psuedoVar.setSelect(xpath);
852 psuedoVar.setName(uniquePseudoVarName);
853
854 Vector globalVars = stylesheetRoot.getVariablesAndParamsComposed();
855 psuedoVar.setIndex(globalVars.size());
856 globalVars.addElement(psuedoVar);
857 return psuedoVar;
858 }
859
860
861
862
863 /**
864 * Create a psuedo variable reference that will represent the
865 * shared redundent XPath, for a local reduction.
866 *
867 * @param uniquePseudoVarName The name of the new variable.
868 * @param psuedoVarRecipient The broadest scope of where the variable
869 * should be inserted, usually an xsl:template or xsl:for-each.
870 * @param lpi The LocationPathIterator that the variable should represent.
871 * @return null if the decl was not created, otherwise the new Pseudo var
872 * element.
873 */
874 protected ElemVariable createLocalPseudoVarDecl(QName uniquePseudoVarName,
875 ElemTemplateElement psuedoVarRecipient,
876 LocPathIterator lpi)
877 throws org.w3c.dom.DOMException
878 {
879 ElemVariable psuedoVar = new ElemVariablePsuedo();
880
881 XPath xpath = new XPath(lpi);
882 psuedoVar.setSelect(xpath);
883 psuedoVar.setName(uniquePseudoVarName);
884
885 ElemVariable var = addVarDeclToElem(psuedoVarRecipient, lpi, psuedoVar);
886
887 lpi.exprSetParent(var);
888
889 return var;
890 }
891
892 /**
893 * Add the given variable to the psuedoVarRecipient.
894 */
895 protected ElemVariable addVarDeclToElem(
896 ElemTemplateElement psuedoVarRecipient,
897 LocPathIterator lpi,
898 ElemVariable psuedoVar)
899 throws org.w3c.dom.DOMException
900 {
901 // Create psuedo variable element
902 ElemTemplateElement ete = psuedoVarRecipient.getFirstChildElem();
903
904 lpi.callVisitors(null, m_varNameCollector);
905
906 // If the location path contains variables, we have to insert the
907 // psuedo variable after the reference. (Otherwise, we want to
908 // insert it as close as possible to the top, so we'll be sure
909 // it is in scope for any other vars.
910 if (m_varNameCollector.getVarCount() > 0)
911 {
912 ElemTemplateElement baseElem = getElemFromExpression(lpi);
913 ElemVariable varElem = getPrevVariableElem(baseElem);
914 while (null != varElem)
915 {
916 if (m_varNameCollector.doesOccur(varElem.getName()))
917 {
918 psuedoVarRecipient = varElem.getParentElem();
919 ete = varElem.getNextSiblingElem();
920 break;
921 }
922 varElem = getPrevVariableElem(varElem);
923 }
924 }
925
926 if ((null != ete) && (Constants.ELEMNAME_PARAMVARIABLE == ete.getXSLToken()))
927 {
928 // Can't stick something in front of a param, so abandon! (see variable13.xsl)
929 if(isParam(lpi))
930 return null;
931
932 while (null != ete)
933 {
934 ete = ete.getNextSiblingElem();
935 if ((null != ete) && Constants.ELEMNAME_PARAMVARIABLE != ete.getXSLToken())
936 break;
937 }
938 }
939 psuedoVarRecipient.insertBefore(psuedoVar, ete);
940 m_varNameCollector.reset();
941 return psuedoVar;
942 }
943
944 /**
945 * Tell if the expr param is contained within an xsl:param.
946 */
947 protected boolean isParam(ExpressionNode expr)
948 {
949 while(null != expr)
950 {
951 if(expr instanceof ElemTemplateElement)
952 break;
953 expr = expr.exprGetParent();
954 }
955 if(null != expr)
956 {
957 ElemTemplateElement ete = (ElemTemplateElement)expr;
958 while(null != ete)
959 {
960 int type = ete.getXSLToken();
961 switch(type)
962 {
963 case Constants.ELEMNAME_PARAMVARIABLE:
964 return true;
965 case Constants.ELEMNAME_TEMPLATE:
966 case Constants.ELEMNAME_STYLESHEET:
967 return false;
968 }
969 ete = ete.getParentElem();
970 }
971 }
972 return false;
973
974 }
975
976 /**
977 * Find the previous occurance of a xsl:variable. Stop
978 * the search when a xsl:for-each, xsl:template, or xsl:stylesheet is
979 * encountered.
980 *
981 * @param elem Should be non-null template element.
982 * @return The first previous occurance of an xsl:variable or xsl:param,
983 * or null if none is found.
984 */
985 protected ElemVariable getPrevVariableElem(ElemTemplateElement elem)
986 {
987 // This could be somewhat optimized. since getPreviousSiblingElem is a
988 // fairly expensive operation.
989 while(null != (elem = getPrevElementWithinContext(elem)))
990 {
991 int type = elem.getXSLToken();
992
993 if((Constants.ELEMNAME_VARIABLE == type) ||
994 (Constants.ELEMNAME_PARAMVARIABLE == type))
995 {
996 return (ElemVariable)elem;
997 }
998 }
999 return null;
1000 }
1001
1002 /**
1003 * Get the previous sibling or parent of the given template, stopping at
1004 * xsl:for-each, xsl:template, or xsl:stylesheet.
1005 *
1006 * @param elem Should be non-null template element.
1007 * @return previous sibling or parent, or null if previous is xsl:for-each,
1008 * xsl:template, or xsl:stylesheet.
1009 */
1010 protected ElemTemplateElement getPrevElementWithinContext(ElemTemplateElement elem)
1011 {
1012 ElemTemplateElement prev = elem.getPreviousSiblingElem();
1013 if(null == prev)
1014 prev = elem.getParentElem();
1015 if(null != prev)
1016 {
1017 int type = prev.getXSLToken();
1018 if((Constants.ELEMNAME_FOREACH == type) ||
1019 (Constants.ELEMNAME_TEMPLATE == type) ||
1020 (Constants.ELEMNAME_STYLESHEET == type))
1021 {
1022 prev = null;
1023 }
1024 }
1025 return prev;
1026 }
1027
1028 /**
1029 * From an XPath expression component, get the ElemTemplateElement
1030 * owner.
1031 *
1032 * @param expr Should be static expression with proper parentage.
1033 * @return Valid ElemTemplateElement, or throw a runtime exception
1034 * if it is not found.
1035 */
1036 protected ElemTemplateElement getElemFromExpression(Expression expr)
1037 {
1038 ExpressionNode parent = expr.exprGetParent();
1039 while(null != parent)
1040 {
1041 if(parent instanceof ElemTemplateElement)
1042 return (ElemTemplateElement)parent;
1043 parent = parent.exprGetParent();
1044 }
1045 throw new RuntimeException(XSLMessages.createMessage(XSLTErrorResources.ER_ASSERT_NO_TEMPLATE_PARENT, null));
1046 // "Programmer's error! expr has no ElemTemplateElement parent!");
1047 }
1048
1049 /**
1050 * Tell if the given LocPathIterator is relative to an absolute path, i.e.
1051 * in not dependent on the context.
1052 *
1053 * @return true if the LocPathIterator is not dependent on the context node.
1054 */
1055 public boolean isAbsolute(LocPathIterator path)
1056 {
1057 int analysis = path.getAnalysisBits();
1058 boolean isAbs = (WalkerFactory.isSet(analysis, WalkerFactory.BIT_ROOT) ||
1059 WalkerFactory.isSet(analysis, WalkerFactory.BIT_ANY_DESCENDANT_FROM_ROOT));
1060 if(isAbs)
1061 {
1062 isAbs = m_absPathChecker.checkAbsolute(path);
1063 }
1064 return isAbs;
1065 }
1066
1067
1068 /**
1069 * Visit a LocationPath.
1070 * @param owner The owner of the expression, to which the expression can
1071 * be reset if rewriting takes place.
1072 * @param path The LocationPath object.
1073 * @return true if the sub expressions should be traversed.
1074 */
1075 public boolean visitLocationPath(ExpressionOwner owner, LocPathIterator path)
1076 {
1077 // Don't optimize "." or single step variable paths.
1078 // Both of these cases could use some further optimization by themselves.
1079 if(path instanceof SelfIteratorNoPredicate)
1080 {
1081 return true;
1082 }
1083 else if(path instanceof WalkingIterator)
1084 {
1085 WalkingIterator wi = (WalkingIterator)path;
1086 AxesWalker aw = wi.getFirstWalker();
1087 if((aw instanceof FilterExprWalker) && (null == aw.getNextWalker()))
1088 {
1089 FilterExprWalker few = (FilterExprWalker)aw;
1090 Expression exp = few.getInnerExpression();
1091 if(exp instanceof Variable)
1092 return true;
1093 }
1094 }
1095
1096 if (isAbsolute(path) && (null != m_absPaths))
1097 {
1098 if(DEBUG)
1099 validateNewAddition(m_absPaths, owner, path);
1100 m_absPaths.addElement(owner);
1101 }
1102 else if (m_isSameContext && (null != m_paths))
1103 {
1104 if(DEBUG)
1105 validateNewAddition(m_paths, owner, path);
1106 m_paths.addElement(owner);
1107 }
1108
1109 return true;
1110 }
1111
1112 /**
1113 * Visit a predicate within a location path. Note that there isn't a
1114 * proper unique component for predicates, and that the expression will
1115 * be called also for whatever type Expression is.
1116 *
1117 * @param owner The owner of the expression, to which the expression can
1118 * be reset if rewriting takes place.
1119 * @param pred The predicate object.
1120 * @return true if the sub expressions should be traversed.
1121 */
1122 public boolean visitPredicate(ExpressionOwner owner, Expression pred)
1123 {
1124 boolean savedIsSame = m_isSameContext;
1125 m_isSameContext = false;
1126
1127 // Any further down, just collect the absolute paths.
1128 pred.callVisitors(owner, this);
1129
1130 m_isSameContext = savedIsSame;
1131
1132 // We've already gone down the subtree, so don't go have the caller
1133 // go any further.
1134 return false;
1135 }
1136
1137 /**
1138 * Visit an XSLT top-level instruction.
1139 *
1140 * @param elem The xsl instruction element object.
1141 * @return true if the sub expressions should be traversed.
1142 */
1143 public boolean visitTopLevelInstruction(ElemTemplateElement elem)
1144 {
1145 int type = elem.getXSLToken();
1146 switch(type)
1147 {
1148 case Constants.ELEMNAME_TEMPLATE :
1149 return visitInstruction(elem);
1150 default:
1151 return true;
1152 }
1153 }
1154
1155
1156 /**
1157 * Visit an XSLT instruction. Any element that isn't called by one
1158 * of the other visit methods, will be called by this method.
1159 *
1160 * @param elem The xsl instruction element object.
1161 * @return true if the sub expressions should be traversed.
1162 */
1163 public boolean visitInstruction(ElemTemplateElement elem)
1164 {
1165 int type = elem.getXSLToken();
1166 switch (type)
1167 {
1168 case Constants.ELEMNAME_CALLTEMPLATE :
1169 case Constants.ELEMNAME_TEMPLATE :
1170 case Constants.ELEMNAME_FOREACH :
1171 {
1172
1173 // Just get the select value.
1174 if(type == Constants.ELEMNAME_FOREACH)
1175 {
1176 ElemForEach efe = (ElemForEach) elem;
1177
1178 Expression select = efe.getSelect();
1179 select.callVisitors(efe, this);
1180 }
1181
1182 Vector savedPaths = m_paths;
1183 m_paths = new Vector();
1184
1185 // Visit children. Call the superclass callChildVisitors, because
1186 // we don't want to visit the xsl:for-each select attribute, or, for
1187 // that matter, the xsl:template's match attribute.
1188 elem.callChildVisitors(this, false);
1189 eleminateRedundentLocals(elem);
1190
1191 m_paths = savedPaths;
1192
1193 // select.callVisitors(efe, this);
1194 return false;
1195 }
1196 case Constants.ELEMNAME_NUMBER :
1197 case Constants.ELEMNAME_SORT :
1198 // Just collect absolute paths until and unless we can fully
1199 // analyze these cases.
1200 boolean savedIsSame = m_isSameContext;
1201 m_isSameContext = false;
1202 elem.callChildVisitors(this);
1203 m_isSameContext = savedIsSame;
1204 return false;
1205
1206 default :
1207 return true;
1208 }
1209 }
1210
1211 // ==== DIAGNOSTIC AND DEBUG FUNCTIONS ====
1212
1213 /**
1214 * Print out to std err the number of paths reduced.
1215 */
1216 protected void diagnoseNumPaths(Vector paths, int numPathsEliminated,
1217 int numUniquePathsEliminated)
1218 {
1219 if (numPathsEliminated > 0)
1220 {
1221 if(paths == m_paths)
1222 {
1223 System.err.println("Eliminated " + numPathsEliminated + " total paths!");
1224 System.err.println(
1225 "Consolodated " + numUniquePathsEliminated + " redundent paths!");
1226 }
1227 else
1228 {
1229 System.err.println("Eliminated " + numPathsEliminated + " total global paths!");
1230 System.err.println(
1231 "Consolodated " + numUniquePathsEliminated + " redundent global paths!");
1232 }
1233 }
1234 }
1235
1236
1237 /**
1238 * Assert that the expression is a LocPathIterator, and, if
1239 * not, try to give some diagnostic info.
1240 */
1241 private final void assertIsLocPathIterator(Expression expr1, ExpressionOwner eo)
1242 throws RuntimeException
1243 {
1244 if(!(expr1 instanceof LocPathIterator))
1245 {
1246 String errMsg;
1247 if(expr1 instanceof Variable)
1248 {
1249 errMsg = "Programmer's assertion: expr1 not an iterator: "+
1250 ((Variable)expr1).getQName();
1251 }
1252 else
1253 {
1254 errMsg = "Programmer's assertion: expr1 not an iterator: "+
1255 expr1.getClass().getName();
1256 }
1257 throw new RuntimeException(errMsg + ", "+
1258 eo.getClass().getName()+" "+
1259 expr1.exprGetParent());
1260 }
1261 }
1262
1263
1264 /**
1265 * Validate some assumptions about the new LocPathIterator and it's
1266 * owner and the state of the list.
1267 */
1268 private static void validateNewAddition(Vector paths, ExpressionOwner owner,
1269 LocPathIterator path)
1270 throws RuntimeException
1271 {
1272 assertion(owner.getExpression() == path, "owner.getExpression() != path!!!");
1273 int n = paths.size();
1274 // There should never be any duplicates in the list!
1275 for(int i = 0; i < n; i++)
1276 {
1277 ExpressionOwner ew = (ExpressionOwner)paths.elementAt(i);
1278 assertion(ew != owner, "duplicate owner on the list!!!");
1279 assertion(ew.getExpression() != path, "duplicate expression on the list!!!");
1280 }
1281 }
1282
1283 /**
1284 * Simple assertion.
1285 */
1286 protected static void assertion(boolean b, String msg)
1287 {
1288 if(!b)
1289 {
1290 throw new RuntimeException(XSLMessages.createMessage(XSLTErrorResources.ER_ASSERT_REDUNDENT_EXPR_ELIMINATOR, new Object[]{msg}));
1291 // "Programmer's assertion in RundundentExprEliminator: "+msg);
1292 }
1293 }
1294
1295 /**
1296 * Since we want to sort multistep expressions by length, use
1297 * a linked list with elements of type MultistepExprHolder.
1298 */
1299 class MultistepExprHolder implements Cloneable
1300 {
1301 ExpressionOwner m_exprOwner; // Will change to null once we have processed this item.
1302 final int m_stepCount;
1303 MultistepExprHolder m_next;
1304
1305 /**
1306 * Clone this object.
1307 */
1308 public Object clone()
1309 throws CloneNotSupportedException
1310 {
1311 return super.clone();
1312 }
1313
1314 /**
1315 * Create a MultistepExprHolder.
1316 *
1317 * @param exprOwner the owner of the expression we are holding.
1318 * It must hold a LocationPathIterator.
1319 * @param stepCount The number of steps in the location path.
1320 */
1321 MultistepExprHolder(ExpressionOwner exprOwner, int stepCount, MultistepExprHolder next)
1322 {
1323 m_exprOwner = exprOwner;
1324 assertion(null != m_exprOwner, "exprOwner can not be null!");
1325 m_stepCount = stepCount;
1326 m_next = next;
1327 }
1328
1329 /**
1330 * Add a new MultistepExprHolder in sorted order in the list.
1331 *
1332 * @param exprOwner the owner of the expression we are holding.
1333 * It must hold a LocationPathIterator.
1334 * @param stepCount The number of steps in the location path.
1335 * @return The new head of the linked list.
1336 */
1337 MultistepExprHolder addInSortedOrder(ExpressionOwner exprOwner, int stepCount)
1338 {
1339 MultistepExprHolder first = this;
1340 MultistepExprHolder next = this;
1341 MultistepExprHolder prev = null;
1342 while(null != next)
1343 {
1344 if(stepCount >= next.m_stepCount)
1345 {
1346 MultistepExprHolder newholder = new MultistepExprHolder(exprOwner, stepCount, next);
1347 if(null == prev)
1348 first = newholder;
1349 else
1350 prev.m_next = newholder;
1351
1352 return first;
1353 }
1354 prev = next;
1355 next = next.m_next;
1356 }
1357
1358 prev.m_next = new MultistepExprHolder(exprOwner, stepCount, null);
1359 return first;
1360 }
1361
1362 /**
1363 * Remove the given element from the list. 'this' should
1364 * be the head of the list. If the item to be removed is not
1365 * found, an assertion will be made.
1366 *
1367 * @param itemToRemove The item to remove from the list.
1368 * @return The head of the list, which may have changed if itemToRemove
1369 * is the same as this element. Null if the item to remove is the
1370 * only item in the list.
1371 */
1372 MultistepExprHolder unlink(MultistepExprHolder itemToRemove)
1373 {
1374 MultistepExprHolder first = this;
1375 MultistepExprHolder next = this;
1376 MultistepExprHolder prev = null;
1377 while(null != next)
1378 {
1379 if(next == itemToRemove)
1380 {
1381 if(null == prev)
1382 first = next.m_next;
1383 else
1384 prev.m_next = next.m_next;
1385
1386 next.m_next = null;
1387
1388 return first;
1389 }
1390 prev = next;
1391 next = next.m_next;
1392 }
1393
1394 assertion(false, "unlink failed!!!");
1395 return null;
1396 }
1397
1398 /**
1399 * Get the number of linked list items.
1400 */
1401 int getLength()
1402 {
1403 int count = 0;
1404 MultistepExprHolder next = this;
1405 while(null != next)
1406 {
1407 count++;
1408 next = next.m_next;
1409 }
1410 return count;
1411 }
1412
1413 /**
1414 * Print diagnostics out for the multistep list.
1415 */
1416 protected void diagnose()
1417 {
1418 System.err.print("Found multistep iterators: " + this.getLength() + " ");
1419 MultistepExprHolder next = this;
1420 while (null != next)
1421 {
1422 System.err.print("" + next.m_stepCount);
1423 next = next.m_next;
1424 if (null != next)
1425 System.err.print(", ");
1426 }
1427 System.err.println();
1428 }
1429
1430 }
1431
1432 }