KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > xalan > templates > RedundentExprEliminator


1 /*
2  * Copyright 2002-2004 The Apache Software Foundation.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */

16 /*
17  * $Id: RedundentExprEliminator.java,v 1.9 2004/02/16 20:32:32 minchau Exp $
18  */

19 package org.apache.xalan.templates;
20
21 import java.util.Vector JavaDoc;
22
23 import org.apache.xalan.res.XSLMessages;
24 import org.apache.xalan.res.XSLTErrorResources;
25 import org.apache.xml.utils.QName;
26 import org.apache.xml.utils.WrappedRuntimeException;
27 import org.apache.xpath.Expression;
28 import org.apache.xpath.ExpressionNode;
29 import org.apache.xpath.ExpressionOwner;
30 import org.apache.xpath.XPath;
31 import org.apache.xpath.axes.AxesWalker;
32 import org.apache.xpath.axes.FilterExprIteratorSimple;
33 import org.apache.xpath.axes.FilterExprWalker;
34 import org.apache.xpath.axes.LocPathIterator;
35 import org.apache.xpath.axes.SelfIteratorNoPredicate;
36 import org.apache.xpath.axes.WalkerFactory;
37 import org.apache.xpath.axes.WalkingIterator;
38 import org.apache.xpath.operations.Variable;
39 import org.apache.xpath.operations.VariableSafeAbsRef;
40
41 /**
42  * This class eleminates redundent XPaths from a given subtree,
43  * and also collects all absolute paths within the subtree. First
44  * it must be called as a visitor to the subtree, and then
45  * eleminateRedundent must be called.
46  */

47 public class RedundentExprEliminator extends XSLTVisitor
48 {
49   Vector JavaDoc m_paths;
50   Vector JavaDoc m_absPaths;
51   boolean m_isSameContext;
52   AbsPathChecker m_absPathChecker = new AbsPathChecker();
53   
54   static int m_uniquePsuedoVarID = 1;
55   static final String JavaDoc PSUEDOVARNAMESPACE = Constants.S_VENDORURL+"/xalan/psuedovar";
56  
57   public static boolean DEBUG = false;
58   public static boolean DIAGNOSE_NUM_PATHS_REDUCED = false;
59   public static boolean DIAGNOSE_MULTISTEPLIST = false;
60
61   /**
62    * So we can reuse it over and over again.
63    */

64   VarNameCollector m_varNameCollector = new VarNameCollector();
65
66   /**
67    * Construct a RedundentExprEliminator.
68    *
69    * @param absPathsList Vector to which absolute paths will
70    * be inserted. The vector may be null, if the caller does
71    * not wish to collect absolute paths.
72    */

73   public RedundentExprEliminator()
74   {
75     m_isSameContext = true;
76     m_absPaths = new Vector JavaDoc();
77     m_paths = null;
78   }
79   
80   
81   /**
82    * Method to be called after the all expressions within an
83    * node context have been visited. It eliminates redundent
84    * expressions by creating a variable in the psuedoVarRecipient
85    * for each redundent expression, and then rewriting the redundent
86    * expression to be a variable reference.
87    *
88    * @param psuedoVarRecipient The recipient of the psuedo vars. The
89    * variables will be inserted as first children of the element, before
90    * any existing variables.
91    */

92   public void eleminateRedundentLocals(ElemTemplateElement psuedoVarRecipient)
93   {
94     eleminateRedundent(psuedoVarRecipient, m_paths);
95   }
96   
97   /**
98    * Method to be called after the all global expressions within a stylesheet
99    * have been collected. It eliminates redundent
100    * expressions by creating a variable in the psuedoVarRecipient
101    * for each redundent expression, and then rewriting the redundent
102    * expression to be a variable reference.
103    *
104    * @param psuedoVarRecipient The recipient of the psuedo vars. The
105    * variables will be inserted as first children of the element, before
106    * any existing variables.
107    */

108   public void eleminateRedundentGlobals(StylesheetRoot stylesheet)
109   {
110     eleminateRedundent(stylesheet, m_absPaths);
111   }
112
113   
114   /**
115    * Method to be called after the all expressions within an
116    * node context have been visited. It eliminates redundent
117    * expressions by creating a variable in the psuedoVarRecipient
118    * for each redundent expression, and then rewriting the redundent
119    * expression to be a variable reference.
120    *
121    * @param psuedoVarRecipient The owner of the subtree from where the
122    * paths were collected.
123    * @param paths A vector of paths that hold ExpressionOwner objects,
124    * which must yield LocationPathIterators.
125    */

126   protected void eleminateRedundent(ElemTemplateElement psuedoVarRecipient, Vector JavaDoc paths)
127   {
128     int n = paths.size();
129     int numPathsEliminated = 0;
130     int numUniquePathsEliminated = 0;
131     for (int i = 0; i < n; i++)
132     {
133       ExpressionOwner owner = (ExpressionOwner) paths.elementAt(i);
134       if (null != owner)
135       {
136         int found = findAndEliminateRedundant(i + 1, i, owner, psuedoVarRecipient, paths);
137         if (found > 0)
138                   numUniquePathsEliminated++;
139         numPathsEliminated += found;
140       }
141     }
142     
143     eleminateSharedPartialPaths(psuedoVarRecipient, paths);
144     
145     if(DIAGNOSE_NUM_PATHS_REDUCED)
146         diagnoseNumPaths(paths, numPathsEliminated, numUniquePathsEliminated);
147   }
148   
149   /**
150    * Eliminate the shared partial paths in the expression list.
151    *
152    * @param psuedoVarRecipient The recipient of the psuedo vars.
153    *
154    * @param paths A vector of paths that hold ExpressionOwner objects,
155    * which must yield LocationPathIterators.
156    */

157   protected void eleminateSharedPartialPaths(ElemTemplateElement psuedoVarRecipient, Vector JavaDoc paths)
158   {
159     MultistepExprHolder list = createMultistepExprList(paths);
160     if(null != list)
161     {
162         if(DIAGNOSE_MULTISTEPLIST)
163             list.diagnose();
164             
165         boolean isGlobal = (paths == m_absPaths);
166             
167         // Iterate over the list, starting with the most number of paths,
168
// trying to find the longest matches first.
169
int longestStepsCount = list.m_stepCount;
170         for (int i = longestStepsCount-1; i >= 1; i--)
171         {
172             MultistepExprHolder next = list;
173             while(null != next)
174             {
175                 if(next.m_stepCount < i)
176                     break;
177                 list = matchAndEliminatePartialPaths(next, list, isGlobal, i, psuedoVarRecipient);
178                 next = next.m_next;
179             }
180         }
181     }
182   }
183
184   /**
185    * For a given path, see if there are any partitial matches in the list,
186    * and, if there are, replace those partial paths with psuedo variable refs,
187    * and create the psuedo variable decl.
188    *
189    * @return The head of the list, which may have changed.
190    */

191   protected MultistepExprHolder matchAndEliminatePartialPaths(MultistepExprHolder testee,
192                                                MultistepExprHolder head,
193                                                boolean isGlobal,
194                                                int lengthToTest,
195                                                ElemTemplateElement varScope)
196   {
197     if(null == testee.m_exprOwner)
198         return head;
199         
200     // Start with the longest possible match, and move down.
201
WalkingIterator iter1 = (WalkingIterator) testee.m_exprOwner.getExpression();
202     if(partialIsVariable(testee, lengthToTest))
203         return head;
204     MultistepExprHolder matchedPaths = null;
205     MultistepExprHolder matchedPathsTail = null;
206     MultistepExprHolder meh = head;
207     while( null != meh)
208     {
209       if ((meh != testee) && (null != meh.m_exprOwner))
210       {
211           WalkingIterator iter2 = (WalkingIterator) meh.m_exprOwner.getExpression();
212           if (stepsEqual(iter1, iter2, lengthToTest))
213           {
214             if (null == matchedPaths)
215             {
216               try
217               {
218                 matchedPaths = (MultistepExprHolder)testee.clone();
219                 testee.m_exprOwner = null; // So it won't be processed again.
220
}
221               catch(CloneNotSupportedException JavaDoc cnse){}
222               matchedPathsTail = matchedPaths;
223               matchedPathsTail.m_next = null;
224             }
225            
226             try
227             {
228               matchedPathsTail.m_next = (MultistepExprHolder)meh.clone();
229               meh.m_exprOwner = null; // So it won't be processed again.
230
}
231             catch(CloneNotSupportedException JavaDoc cnse){}
232             matchedPathsTail = matchedPathsTail.m_next;
233             matchedPathsTail.m_next = null;
234           }
235       }
236       meh = meh.m_next;
237     }
238         
239     int matchCount = 0;
240     if(null != matchedPaths)
241     {
242         ElemTemplateElement root = isGlobal ? varScope : findCommonAncestor(matchedPaths);
243         WalkingIterator sharedIter = (WalkingIterator)matchedPaths.m_exprOwner.getExpression();
244         WalkingIterator newIter = createIteratorFromSteps(sharedIter, lengthToTest);
245         ElemVariable var = createPsuedoVarDecl(root, newIter, isGlobal);
246         if(DIAGNOSE_MULTISTEPLIST)
247             System.err.println("Created var: "+var.getName()+(isGlobal ? "(Global)" : ""));
248         while(null != matchedPaths)
249         {
250             ExpressionOwner owner = matchedPaths.m_exprOwner;
251             WalkingIterator iter = (WalkingIterator)owner.getExpression();
252             
253             if(DIAGNOSE_MULTISTEPLIST)
254                 diagnoseLineNumber(iter);
255             
256             LocPathIterator newIter2 =
257                 changePartToRef(var.getName(), iter, lengthToTest, isGlobal);
258             owner.setExpression(newIter2);
259             
260             matchedPaths = matchedPaths.m_next;
261         }
262     }
263     
264     if(DIAGNOSE_MULTISTEPLIST)
265         diagnoseMultistepList(matchCount, lengthToTest, isGlobal);
266     return head;
267   }
268   
269   /**
270    * Check if results of partial reduction will just be a variable, in
271    * which case, skip it.
272    */

273   boolean partialIsVariable(MultistepExprHolder testee, int lengthToTest)
274   {
275     if(1 == lengthToTest)
276     {
277         WalkingIterator wi = (WalkingIterator)testee.m_exprOwner.getExpression();
278         if(wi.getFirstWalker() instanceof FilterExprWalker)
279             return true;
280     }
281     return false;
282   }
283
284   /**
285    * Tell what line number belongs to a given expression.
286    */

287   protected void diagnoseLineNumber(Expression expr)
288   {
289     ElemTemplateElement e = getElemFromExpression(expr);
290     System.err.println(" " + e.getSystemId() + " Line " + e.getLineNumber());
291   }
292       
293   /**
294    * Given a linked list of expressions, find the common ancestor that is
295    * suitable for holding a psuedo variable for shared access.
296    */

297   protected ElemTemplateElement findCommonAncestor(MultistepExprHolder head)
298   {
299     // Not sure this algorithm is the best, but will do for the moment.
300
int numExprs = head.getLength();
301     // The following could be made cheaper by pre-allocating large arrays,
302
// but then we would have to assume a max number of reductions,
303
// which I am not inclined to do right now.
304
ElemTemplateElement[] elems = new ElemTemplateElement[numExprs];
305     int[] ancestorCounts = new int[numExprs];
306     
307     // Loop through, getting the parent elements, and counting the
308
// ancestors.
309
MultistepExprHolder next = head;
310     int shortestAncestorCount = 10000;
311     for(int i = 0; i < numExprs; i++)
312     {
313         ElemTemplateElement elem =
314             getElemFromExpression(next.m_exprOwner.getExpression());
315         elems[i] = elem;
316         int numAncestors = countAncestors(elem);
317         ancestorCounts[i] = numAncestors;
318         if(numAncestors < shortestAncestorCount)
319         {
320             shortestAncestorCount = numAncestors;
321         }
322         next = next.m_next;
323     }
324     
325     // Now loop through and "correct" the elements that have more ancestors.
326
for(int i = 0; i < numExprs; i++)
327     {
328         if(ancestorCounts[i] > shortestAncestorCount)
329         {
330             int numStepCorrection = ancestorCounts[i] - shortestAncestorCount;
331             for(int j = 0; j < numStepCorrection; j++)
332             {
333                 elems[i] = elems[i].getParentElem();
334             }
335         }
336     }
337     
338     // Now everyone has an equal number of ancestors. Walk up from here
339
// equally until all are equal.
340
ElemTemplateElement first = null;
341     while(shortestAncestorCount-- >= 0)
342     {
343         boolean areEqual = true;
344         first = elems[0];
345         for(int i = 1; i < numExprs; i++)
346         {
347             if(first != elems[i])
348             {
349                 areEqual = false;
350                 break;
351             }
352         }
353         // This second check is to make sure we have a common ancestor that is not the same
354
// as the expression owner... i.e. the var decl has to go above the expression owner.
355
if(areEqual && isNotSameAsOwner(head, first) && first.canAcceptVariables())
356         {
357             if(DIAGNOSE_MULTISTEPLIST)
358             {
359                 System.err.print(first.getClass().getName());
360                 System.err.println(" at " + first.getSystemId() + " Line " + first.getLineNumber());
361             }
362             return first;
363         }
364             
365         for(int i = 0; i < numExprs; i++)
366         {
367             elems[i] = elems[i].getParentElem();
368         }
369     }
370     
371     assertion(false, "Could not find common ancestor!!!");
372     return null;
373   }
374   
375   /**
376    * Find out if the given ElemTemplateElement is not the same as one of
377    * the ElemTemplateElement owners of the expressions.
378    *
379    * @param head Head of linked list of expression owners.
380    * @param ete The ElemTemplateElement that is a candidate for a psuedo
381    * variable parent.
382    * @return true if the given ElemTemplateElement is not the same as one of
383    * the ElemTemplateElement owners of the expressions. This is to make sure
384    * we find an ElemTemplateElement that is in a viable position to hold
385    * psuedo variables that are visible to the references.
386    */

387   protected boolean isNotSameAsOwner(MultistepExprHolder head, ElemTemplateElement ete)
388   {
389     MultistepExprHolder next = head;
390     while(null != next)
391     {
392         ElemTemplateElement elemOwner = getElemFromExpression(next.m_exprOwner.getExpression());
393         if(elemOwner == ete)
394             return false;
395         next = next.m_next;
396     }
397     return true;
398   }
399   
400   /**
401    * Count the number of ancestors that a ElemTemplateElement has.
402    *
403    * @param elem An representation of an element in an XSLT stylesheet.
404    * @return The number of ancestors of elem (including the element itself).
405    */

406   protected int countAncestors(ElemTemplateElement elem)
407   {
408     int count = 0;
409     while(null != elem)
410     {
411         count++;
412         elem = elem.getParentElem();
413     }
414     return count;
415   }
416
417   /**
418    * Print out diagnostics about partial multistep evaluation.
419    */

420   protected void diagnoseMultistepList(
421       int matchCount,
422       int lengthToTest,
423       boolean isGlobal)
424   {
425       if (matchCount > 0)
426         {
427         System.err.print(
428           "Found multistep matches: " + matchCount + ", " + lengthToTest + " length");
429         if (isGlobal)
430               System.err.println(" (global)");
431         else
432               System.err.println();
433       }
434   }
435   
436   /**
437    * Change a given number of steps to a single variable reference.
438    *
439    * @param uniquePsuedoVarName The name of the variable reference.
440    * @param wi The walking iterator that is to be changed.
441    * @param numSteps The number of steps to be changed.
442    * @param isGlobal true if this will be a global reference.
443    */

444   protected LocPathIterator changePartToRef(final QName uniquePsuedoVarName, WalkingIterator wi,
445                                  final int numSteps, final boolean isGlobal)
446   {
447     Variable var = new Variable();
448     var.setQName(uniquePsuedoVarName);
449     var.setIsGlobal(isGlobal);
450     if(isGlobal)
451     { ElemTemplateElement elem = getElemFromExpression(wi);
452         StylesheetRoot root = elem.getStylesheetRoot();
453         Vector JavaDoc vars = root.getVariablesAndParamsComposed();
454         var.setIndex(vars.size()-1);
455     }
456     
457     // Walk to the first walker after the one's we are replacing.
458
AxesWalker walker = wi.getFirstWalker();
459     for(int i = 0; i < numSteps; i++)
460     {
461         assertion(null != walker, "Walker should not be null!");
462         walker = walker.getNextWalker();
463     }
464     
465     if(null != walker)
466     {
467     
468       FilterExprWalker few = new FilterExprWalker(wi);
469       few.setInnerExpression(var);
470       few.exprSetParent(wi);
471       few.setNextWalker(walker);
472       walker.setPrevWalker(few);
473       wi.setFirstWalker(few);
474       return wi;
475     }
476     else
477     {
478       FilterExprIteratorSimple feis = new FilterExprIteratorSimple(var);
479       feis.exprSetParent(wi.exprGetParent());
480       return feis;
481     }
482   }
483   
484   /**
485    * Create a new WalkingIterator from the steps in another WalkingIterator.
486    *
487    * @param wi The iterator from where the steps will be taken.
488    * @param numSteps The number of steps from the first to copy into the new
489    * iterator.
490    * @return The new iterator.
491    */

492   protected WalkingIterator createIteratorFromSteps(final WalkingIterator wi, int numSteps)
493   {
494     WalkingIterator newIter = new WalkingIterator(wi.getPrefixResolver());
495     try
496     {
497         AxesWalker walker = (AxesWalker)wi.getFirstWalker().clone();
498         newIter.setFirstWalker(walker);
499         walker.setLocPathIterator(newIter);
500         for(int i = 1; i < numSteps; i++)
501         {
502             AxesWalker next = (AxesWalker)walker.getNextWalker().clone();
503             walker.setNextWalker(next);
504             next.setLocPathIterator(newIter);
505             walker = next;
506         }
507         walker.setNextWalker(null);
508     }
509     catch(CloneNotSupportedException JavaDoc cnse)
510     {
511         throw new WrappedRuntimeException(cnse);
512     }
513     return newIter;
514   }
515     
516   /**
517    * Compare a given number of steps between two iterators, to see if they are equal.
518    *
519    * @param iter1 The first iterator to compare.
520    * @param iter2 The second iterator to compare.
521    * @param numSteps The number of steps to compare.
522    * @return true If the given number of steps are equal.
523    *
524    */

525   protected boolean stepsEqual(WalkingIterator iter1, WalkingIterator iter2,
526                                          int numSteps)
527   {
528     AxesWalker aw1 = iter1.getFirstWalker();
529     AxesWalker aw2 = iter2.getFirstWalker();
530     
531     for(int i = 0; (i < numSteps); i++)
532     {
533         if((null == aw1) || (null == aw2))
534             return false;
535             
536         if(!aw1.deepEquals(aw2))
537             return false;
538         
539         aw1 = aw1.getNextWalker();
540         aw2 = aw2.getNextWalker();
541     }
542     
543     assertion((null != aw1) || (null != aw2), "Total match is incorrect!");
544     
545     return true;
546   }
547   
548   /**
549    * For the reduction of location path parts, create a list of all
550    * the multistep paths with more than one step, sorted by the
551    * number of steps, with the most steps occuring earlier in the list.
552    * If the list is only one member, don't bother returning it.
553    *
554    * @param paths Vector of ExpressionOwner objects, which may contain null entries.
555    * The ExpressionOwner objects must own LocPathIterator objects.
556    * @return null if no multipart paths are found or the list is only of length 1,
557    * otherwise the first MultistepExprHolder in a linked list of these objects.
558    */

559   protected MultistepExprHolder createMultistepExprList(Vector JavaDoc paths)
560   {
561     MultistepExprHolder first = null;
562     int n = paths.size();
563     for(int i = 0; i < n; i++)
564     {
565         ExpressionOwner eo = (ExpressionOwner)paths.elementAt(i);
566         if(null == eo)
567             continue;
568             
569         // Assuming location path iterators should be OK.
570
LocPathIterator lpi = (LocPathIterator)eo.getExpression();
571         int numPaths = countSteps(lpi);
572         if(numPaths > 1)
573         {
574             if(null == first)
575                 first = new MultistepExprHolder(eo, numPaths, null);
576             else
577                 first = first.addInSortedOrder(eo, numPaths);
578         }
579     }
580     
581     if((null == first) || (first.getLength() <= 1))
582         return null;
583     else
584         return first;
585   }
586   
587   /**
588    * Look through the vector from start point, looking for redundant occurances.
589    * When one or more are found, create a psuedo variable declaration, insert
590    * it into the stylesheet, and replace the occurance with a reference to
591    * the psuedo variable. When a redundent variable is found, it's slot in
592    * the vector will be replaced by null.
593    *
594    * @param start The position to start looking in the vector.
595    * @param targetIndex The position of firstOccuranceOwner.
596    * @param firstOccuranceOwner The owner of the expression we are looking for.
597    * @param psuedoVarRecipient Where to put the psuedo variables.
598    *
599    * @return The number of expression occurances that were modified.
600    */

601   protected int findAndEliminateRedundant(int start, int firstOccuranceIndex,
602                          ExpressionOwner firstOccuranceOwner,
603                          ElemTemplateElement psuedoVarRecipient,
604                          Vector JavaDoc paths)
605                  throws org.w3c.dom.DOMException JavaDoc
606   {
607     MultistepExprHolder head = null;
608     MultistepExprHolder tail = null;
609     int numPathsFound = 0;
610     int n = paths.size();
611     
612     Expression expr1 = firstOccuranceOwner.getExpression();
613     if(DEBUG)
614         assertIsLocPathIterator(expr1, firstOccuranceOwner);
615     boolean isGlobal = (paths == m_absPaths);
616     LocPathIterator lpi = (LocPathIterator)expr1;
617     int stepCount = countSteps(lpi);
618     for(int j = start; j < n; j++)
619     {
620         ExpressionOwner owner2 = (ExpressionOwner)paths.elementAt(j);
621         if(null != owner2)
622         {
623             Expression expr2 = owner2.getExpression();
624             boolean isEqual = expr2.deepEquals(lpi);
625             if(isEqual)
626             {
627                 LocPathIterator lpi2 = (LocPathIterator)expr2;
628                 if(null == head)
629                 {
630                     head = new MultistepExprHolder(firstOccuranceOwner, stepCount, null);
631                     tail = head;
632                     numPathsFound++;
633                 }
634                 tail.m_next = new MultistepExprHolder(owner2, stepCount, null);
635                 tail = tail.m_next;
636     
637                 // Null out the occurance, so we don't have to test it again.
638
paths.setElementAt(null, j);
639                 
640                 // foundFirst = true;
641
numPathsFound++;
642             }
643         }
644     }
645     
646     // Change all globals in xsl:templates, etc, to global vars no matter what.
647
if((0 == numPathsFound) && isGlobal)
648     {
649       head = new MultistepExprHolder(firstOccuranceOwner, stepCount, null);
650       numPathsFound++;
651     }
652     
653     if(null != head)
654     {
655         ElemTemplateElement root = isGlobal ? psuedoVarRecipient : findCommonAncestor(head);
656         LocPathIterator sharedIter = (LocPathIterator)head.m_exprOwner.getExpression();
657         ElemVariable var = createPsuedoVarDecl(root, sharedIter, isGlobal);
658         if(DIAGNOSE_MULTISTEPLIST)
659             System.err.println("Created var: "+var.getName()+(isGlobal ? "(Global)" : ""));
660         QName uniquePsuedoVarName = var.getName();
661         while(null != head)
662         {
663             ExpressionOwner owner = head.m_exprOwner;
664             if(DIAGNOSE_MULTISTEPLIST)
665                 diagnoseLineNumber(owner.getExpression());
666             changeToVarRef(uniquePsuedoVarName, owner, paths, root);
667             head = head.m_next;
668         }
669         // Replace the first occurance with the variable's XPath, so
670
// that further reduction may take place if needed.
671
paths.setElementAt(var.getSelect(), firstOccuranceIndex);
672     }
673     
674     return numPathsFound;
675   }
676   
677   /**
678    * To be removed.
679    */

680   protected int oldFindAndEliminateRedundant(int start, int firstOccuranceIndex,
681                          ExpressionOwner firstOccuranceOwner,
682                          ElemTemplateElement psuedoVarRecipient,
683                          Vector JavaDoc paths)
684                  throws org.w3c.dom.DOMException JavaDoc
685   {
686     QName uniquePsuedoVarName = null;
687     boolean foundFirst = false;
688     int numPathsFound = 0;
689     int n = paths.size();
690     Expression expr1 = firstOccuranceOwner.getExpression();
691     if(DEBUG)
692         assertIsLocPathIterator(expr1, firstOccuranceOwner);
693     boolean isGlobal = (paths == m_absPaths);
694     LocPathIterator lpi = (LocPathIterator)expr1;
695     for(int j = start; j < n; j++)
696     {
697         ExpressionOwner owner2 = (ExpressionOwner)paths.elementAt(j);
698         if(null != owner2)
699         {
700             Expression expr2 = owner2.getExpression();
701             boolean isEqual = expr2.deepEquals(lpi);
702             if(isEqual)
703             {
704                 LocPathIterator lpi2 = (LocPathIterator)expr2;
705                 if(!foundFirst)
706                 {
707                     foundFirst = true;
708                     // Insert variable decl into psuedoVarRecipient
709
// We want to insert this into the first legitimate
710
// position for a variable.
711
ElemVariable var = createPsuedoVarDecl(psuedoVarRecipient, lpi, isGlobal);
712                     if(null == var)
713                         return 0;
714                     uniquePsuedoVarName = var.getName();
715     
716                     changeToVarRef(uniquePsuedoVarName, firstOccuranceOwner,
717                                    paths, psuedoVarRecipient);
718                                    
719                     // Replace the first occurance with the variable's XPath, so
720
// that further reduction may take place if needed.
721
paths.setElementAt(var.getSelect(), firstOccuranceIndex);
722                     numPathsFound++;
723                 }
724     
725                 changeToVarRef(uniquePsuedoVarName, owner2, paths, psuedoVarRecipient);
726     
727                 // Null out the occurance, so we don't have to test it again.
728
paths.setElementAt(null, j);
729                 
730                 // foundFirst = true;
731
numPathsFound++;
732             }
733         }
734     }
735     
736     // Change all globals in xsl:templates, etc, to global vars no matter what.
737
if((0 == numPathsFound) && (paths == m_absPaths))
738     {
739       ElemVariable var = createPsuedoVarDecl(psuedoVarRecipient, lpi, true);
740       if(null == var)
741         return 0;
742       uniquePsuedoVarName = var.getName();
743       changeToVarRef(uniquePsuedoVarName, firstOccuranceOwner, paths, psuedoVarRecipient);
744       paths.setElementAt(var.getSelect(), firstOccuranceIndex);
745       numPathsFound++;
746     }
747     return numPathsFound;
748   }
749   
750   /**
751    * Count the steps in a given location path.
752    *
753    * @param lpi The location path iterator that owns the steps.
754    * @return The number of steps in the given location path.
755    */

756   protected int countSteps(LocPathIterator lpi)
757   {
758     if(lpi instanceof WalkingIterator)
759     {
760         WalkingIterator wi = (WalkingIterator)lpi;
761         AxesWalker aw = wi.getFirstWalker();
762         int count = 0;
763         while(null != aw)
764         {
765             count++;
766             aw = aw.getNextWalker();
767         }
768         return count;
769     }
770     else
771         return 1;
772   }
773   
774   /**
775    * Change the expression owned by the owner argument to a variable reference
776    * of the given name.
777    *
778    * Warning: For global vars, this function relies on the variable declaration
779    * to which it refers having been added just prior to this function being called,
780    * so that the reference index can be determined from the size of the global variables
781    * list minus one.
782    *
783    * @param varName The name of the variable which will be referenced.
784    * @param owner The owner of the expression which will be replaced by a variable ref.
785    * @param paths The paths list that the iterator came from, mainly to determine
786    * if this is a local or global reduction.
787    * @param psuedoVarRecipient The element within whose scope the variable is
788    * being inserted, possibly a StylesheetRoot.
789    */

790   protected void changeToVarRef(QName varName, ExpressionOwner owner,
791                                 Vector JavaDoc paths, ElemTemplateElement psuedoVarRecipient)
792   {
793     Variable varRef = (paths == m_absPaths) ? new VariableSafeAbsRef() : new Variable();
794     varRef.setQName(varName);
795     if(paths == m_absPaths)
796     {
797         StylesheetRoot root = (StylesheetRoot)psuedoVarRecipient;
798         Vector JavaDoc globalVars = root.getVariablesAndParamsComposed();
799         // Assume this operation is occuring just after the decl has
800
// been added.
801
varRef.setIndex(globalVars.size()-1);
802         varRef.setIsGlobal(true);
803     }
804     owner.setExpression(varRef);
805   }
806
807   /**
808    * Create a psuedo variable reference that will represent the
809    * shared redundent XPath, and add it to the stylesheet.
810    *
811    * @param psuedoVarRecipient The broadest scope of where the variable
812    * should be inserted, usually an xsl:template or xsl:for-each.
813    * @param lpi The LocationPathIterator that the variable should represent.
814    * @param isGlobal true if the paths are global.
815    * @return The new psuedo var element.
816    */

817   protected ElemVariable createPsuedoVarDecl(
818       ElemTemplateElement psuedoVarRecipient,
819       LocPathIterator lpi, boolean isGlobal)
820       throws org.w3c.dom.DOMException JavaDoc
821   {
822     QName uniquePsuedoVarName = new QName (PSUEDOVARNAMESPACE, "#"+m_uniquePsuedoVarID);
823     m_uniquePsuedoVarID++;
824         
825     if(isGlobal)
826     {
827       return createGlobalPsuedoVarDecl(uniquePsuedoVarName,
828                                       (StylesheetRoot)psuedoVarRecipient, lpi);
829     }
830     else
831       return createLocalPsuedoVarDecl(uniquePsuedoVarName, psuedoVarRecipient, lpi);
832   }
833   
834   /**
835    * Create a psuedo variable reference that will represent the
836    * shared redundent XPath, for a local reduction.
837    *
838    * @param uniquePsuedoVarName The name of the new variable.
839    * @param stylesheetRoot The broadest scope of where the variable
840    * should be inserted, which must be a StylesheetRoot element in this case.
841    * @param lpi The LocationPathIterator that the variable should represent.
842    * @return null if the decl was not created, otherwise the new Psuedo var
843    * element.
844    */

845   protected ElemVariable createGlobalPsuedoVarDecl(QName uniquePsuedoVarName,
846                                            StylesheetRoot stylesheetRoot,
847                                            LocPathIterator lpi)
848         throws org.w3c.dom.DOMException JavaDoc
849   {
850     ElemVariable psuedoVar = new ElemVariable();
851     psuedoVar.setIsTopLevel(true);
852     XPath xpath = new XPath(lpi);
853     psuedoVar.setSelect(xpath);
854     psuedoVar.setName(uniquePsuedoVarName);
855     
856     Vector JavaDoc globalVars = stylesheetRoot.getVariablesAndParamsComposed();
857     psuedoVar.setIndex(globalVars.size());
858     globalVars.addElement(psuedoVar);
859     return psuedoVar;
860   }
861
862   
863   
864
865   /**
866    * Create a psuedo variable reference that will represent the
867    * shared redundent XPath, for a local reduction.
868    *
869    * @param uniquePsuedoVarName The name of the new variable.
870    * @param psuedoVarRecipient The broadest scope of where the variable
871    * should be inserted, usually an xsl:template or xsl:for-each.
872    * @param lpi The LocationPathIterator that the variable should represent.
873    * @param addToContext true if the decl should be added to psuedoVarRecipient.
874    * @return null if the decl was not created, otherwise the new Psuedo var
875    * element.
876    */

877   protected ElemVariable createLocalPsuedoVarDecl(QName uniquePsuedoVarName,
878                                            ElemTemplateElement psuedoVarRecipient,
879                                            LocPathIterator lpi)
880         throws org.w3c.dom.DOMException JavaDoc
881   {
882         ElemVariable psuedoVar = new ElemVariablePsuedo();
883         
884         XPath xpath = new XPath(lpi);
885         psuedoVar.setSelect(xpath);
886         psuedoVar.setName(uniquePsuedoVarName);
887
888         ElemVariable var = addVarDeclToElem(psuedoVarRecipient, lpi, psuedoVar);
889         
890         lpi.exprSetParent(var);
891         
892         return var;
893   }
894
895   /**
896    * Add the given variable to the psuedoVarRecipient.
897    */

898   protected ElemVariable addVarDeclToElem(
899     ElemTemplateElement psuedoVarRecipient,
900     LocPathIterator lpi,
901     ElemVariable psuedoVar)
902     throws org.w3c.dom.DOMException JavaDoc
903   {
904     // Create psuedo variable element
905
ElemTemplateElement ete = psuedoVarRecipient.getFirstChildElem();
906
907     lpi.callVisitors(null, m_varNameCollector);
908
909     // If the location path contains variables, we have to insert the
910
// psuedo variable after the reference. (Otherwise, we want to
911
// insert it as close as possible to the top, so we'll be sure
912
// it is in scope for any other vars.
913
if (m_varNameCollector.getVarCount() > 0)
914     {
915       ElemTemplateElement baseElem = getElemFromExpression(lpi);
916       ElemVariable varElem = getPrevVariableElem(baseElem);
917       while (null != varElem)
918       {
919         if (m_varNameCollector.doesOccur(varElem.getName()))
920           {
921           psuedoVarRecipient = varElem.getParentElem();
922           ete = varElem.getNextSiblingElem();
923           break;
924         }
925         varElem = getPrevVariableElem(varElem);
926       }
927     }
928
929     if ((null != ete) && (Constants.ELEMNAME_PARAMVARIABLE == ete.getXSLToken()))
930     {
931       // Can't stick something in front of a param, so abandon! (see variable13.xsl)
932
if(isParam(lpi))
933         return null;
934
935       while (null != ete)
936       {
937         ete = ete.getNextSiblingElem();
938         if ((null != ete) && Constants.ELEMNAME_PARAMVARIABLE != ete.getXSLToken())
939             break;
940       }
941     }
942     psuedoVarRecipient.insertBefore(psuedoVar, ete);
943     m_varNameCollector.reset();
944     return psuedoVar;
945   }
946     
947   /**
948    * Tell if the expr param is contained within an xsl:param.
949    */

950   protected boolean isParam(ExpressionNode expr)
951   {
952     while(null != expr)
953     {
954         if(expr instanceof ElemTemplateElement)
955             break;
956         expr = expr.exprGetParent();
957     }
958     if(null != expr)
959     {
960         ElemTemplateElement ete = (ElemTemplateElement)expr;
961         while(null != ete)
962         {
963             int type = ete.getXSLToken();
964             switch(type)
965             {
966                 case Constants.ELEMNAME_PARAMVARIABLE:
967                     return true;
968                 case Constants.ELEMNAME_TEMPLATE:
969                 case Constants.ELEMNAME_STYLESHEET:
970                     return false;
971             }
972             ete = ete.getParentElem();
973         }
974     }
975     return false;
976     
977   }
978   
979   /**
980    * Find the previous occurance of a xsl:variable. Stop
981    * the search when a xsl:for-each, xsl:template, or xsl:stylesheet is
982    * encountered.
983    *
984    * @param elem Should be non-null template element.
985    * @return The first previous occurance of an xsl:variable or xsl:param,
986    * or null if none is found.
987    */

988   protected ElemVariable getPrevVariableElem(ElemTemplateElement elem)
989   {
990     // This could be somewhat optimized. since getPreviousSiblingElem is a
991
// fairly expensive operation.
992
while(null != (elem = getPrevElementWithinContext(elem)))
993     {
994         int type = elem.getXSLToken();
995             
996         if((Constants.ELEMNAME_VARIABLE == type) ||
997            (Constants.ELEMNAME_PARAMVARIABLE == type))
998         {
999             return (ElemVariable)elem;
1000        }
1001    }
1002    return null;
1003  }
1004  
1005  /**
1006   * Get the previous sibling or parent of the given template, stopping at
1007   * xsl:for-each, xsl:template, or xsl:stylesheet.
1008   *
1009   * @param elem Should be non-null template element.
1010   * @return previous sibling or parent, or null if previous is xsl:for-each,
1011   * xsl:template, or xsl:stylesheet.
1012   */

1013  protected ElemTemplateElement getPrevElementWithinContext(ElemTemplateElement elem)
1014  {
1015    ElemTemplateElement prev = elem.getPreviousSiblingElem();
1016    if(null == prev)
1017        prev = elem.getParentElem();
1018    if(null != prev)
1019    {
1020      int type = prev.getXSLToken();
1021      if((Constants.ELEMNAME_FOREACH == type) ||
1022         (Constants.ELEMNAME_TEMPLATE == type) ||
1023         (Constants.ELEMNAME_STYLESHEET == type))
1024      {
1025        prev = null;
1026      }
1027    }
1028    return prev;
1029  }
1030  
1031  /**
1032   * From an XPath expression component, get the ElemTemplateElement
1033   * owner.
1034   *
1035   * @param expr Should be static expression with proper parentage.
1036   * @return Valid ElemTemplateElement, or throw a runtime exception
1037   * if it is not found.
1038   */

1039  protected ElemTemplateElement getElemFromExpression(Expression expr)
1040  {
1041    ExpressionNode parent = expr.exprGetParent();
1042    while(null != parent)
1043    {
1044        if(parent instanceof ElemTemplateElement)
1045            return (ElemTemplateElement)parent;
1046        parent = parent.exprGetParent();
1047    }
1048    throw new RuntimeException JavaDoc(XSLMessages.createMessage(XSLTErrorResources.ER_ASSERT_NO_TEMPLATE_PARENT, null));
1049    // "Programmer's error! expr has no ElemTemplateElement parent!");
1050
}
1051      
1052  /**
1053   * Tell if the given LocPathIterator is relative to an absolute path, i.e.
1054   * in not dependent on the context.
1055   *
1056   * @return true if the LocPathIterator is not dependent on the context node.
1057   */

1058  public boolean isAbsolute(LocPathIterator path)
1059  {
1060    int analysis = path.getAnalysisBits();
1061    boolean isAbs = (WalkerFactory.isSet(analysis, WalkerFactory.BIT_ROOT) ||
1062           WalkerFactory.isSet(analysis, WalkerFactory.BIT_ANY_DESCENDANT_FROM_ROOT));
1063    if(isAbs)
1064    {
1065        isAbs = m_absPathChecker.checkAbsolute(path);
1066    }
1067    return isAbs;
1068  }
1069
1070
1071  /**
1072   * Visit a LocationPath.
1073   * @param owner The owner of the expression, to which the expression can
1074   * be reset if rewriting takes place.
1075   * @param path The LocationPath object.
1076   * @return true if the sub expressions should be traversed.
1077   */

1078  public boolean visitLocationPath(ExpressionOwner owner, LocPathIterator path)
1079  {
1080    // Don't optimize "." or single step variable paths.
1081
// Both of these cases could use some further optimization by themselves.
1082
if(path instanceof SelfIteratorNoPredicate)
1083    {
1084        return true;
1085    }
1086    else if(path instanceof WalkingIterator)
1087    {
1088        WalkingIterator wi = (WalkingIterator)path;
1089        AxesWalker aw = wi.getFirstWalker();
1090        if((aw instanceof FilterExprWalker) && (null == aw.getNextWalker()))
1091        {
1092            FilterExprWalker few = (FilterExprWalker)aw;
1093            Expression exp = few.getInnerExpression();
1094            if(exp instanceof Variable)
1095                return true;
1096        }
1097    }
1098
1099    if (isAbsolute(path) && (null != m_absPaths))
1100    {
1101      if(DEBUG)
1102        validateNewAddition(m_absPaths, owner, path);
1103      m_absPaths.addElement(owner);
1104    }
1105    else if (m_isSameContext && (null != m_paths))
1106    {
1107      if(DEBUG)
1108        validateNewAddition(m_paths, owner, path);
1109      m_paths.addElement(owner);
1110    }
1111
1112    return true;
1113  }
1114
1115  /**
1116   * Visit a predicate within a location path. Note that there isn't a
1117   * proper unique component for predicates, and that the expression will
1118   * be called also for whatever type Expression is.
1119   *
1120   * @param owner The owner of the expression, to which the expression can
1121   * be reset if rewriting takes place.
1122   * @param pred The predicate object.
1123   * @return true if the sub expressions should be traversed.
1124   */

1125  public boolean visitPredicate(ExpressionOwner owner, Expression pred)
1126  {
1127    boolean savedIsSame = m_isSameContext;
1128    m_isSameContext = false;
1129
1130    // Any further down, just collect the absolute paths.
1131
pred.callVisitors(owner, this);
1132
1133    m_isSameContext = savedIsSame;
1134
1135    // We've already gone down the subtree, so don't go have the caller
1136
// go any further.
1137
return false;
1138  }
1139  
1140  /**
1141   * Visit an XSLT top-level instruction.
1142   *
1143   * @param elem The xsl instruction element object.
1144   * @return true if the sub expressions should be traversed.
1145   */

1146   public boolean visitTopLevelInstruction(ElemTemplateElement elem)
1147   {
1148     int type = elem.getXSLToken();
1149     switch(type)
1150     {
1151       case Constants.ELEMNAME_TEMPLATE :
1152         return visitInstruction(elem);
1153       default:
1154         return true;
1155     }
1156   }
1157
1158
1159  /**
1160   * Visit an XSLT instruction. Any element that isn't called by one
1161   * of the other visit methods, will be called by this method.
1162   *
1163   * @param elem The xsl instruction element object.
1164   * @return true if the sub expressions should be traversed.
1165   */

1166  public boolean visitInstruction(ElemTemplateElement elem)
1167  {
1168    int type = elem.getXSLToken();
1169    switch (type)
1170    {
1171      case Constants.ELEMNAME_CALLTEMPLATE :
1172      case Constants.ELEMNAME_TEMPLATE :
1173      case Constants.ELEMNAME_FOREACH :
1174        {
1175          
1176          // Just get the select value.
1177
if(type == Constants.ELEMNAME_FOREACH)
1178          {
1179            ElemForEach efe = (ElemForEach) elem;
1180            
1181            Expression select = efe.getSelect();
1182            select.callVisitors(efe, this);
1183          }
1184         
1185          Vector JavaDoc savedPaths = m_paths;
1186          m_paths = new Vector JavaDoc();
1187            
1188          // Visit children. Call the superclass callChildVisitors, because
1189
// we don't want to visit the xsl:for-each select attribute, or, for
1190
// that matter, the xsl:template's match attribute.
1191
elem.callChildVisitors(this, false);
1192          eleminateRedundentLocals(elem);
1193            
1194          m_paths = savedPaths;
1195 
1196          // select.callVisitors(efe, this);
1197
return false;
1198        }
1199      case Constants.ELEMNAME_NUMBER :
1200      case Constants.ELEMNAME_SORT :
1201        // Just collect absolute paths until and unless we can fully
1202
// analyze these cases.
1203
boolean savedIsSame = m_isSameContext;
1204        m_isSameContext = false;
1205        elem.callChildVisitors(this);
1206        m_isSameContext = savedIsSame;
1207        return false;
1208        
1209      default :
1210        return true;
1211    }
1212  }
1213  
1214  // ==== DIAGNOSTIC AND DEBUG FUNCTIONS ====
1215

1216  /**
1217   * Print out to std err the number of paths reduced.
1218   */

1219  protected void diagnoseNumPaths(Vector JavaDoc paths, int numPathsEliminated,
1220                                  int numUniquePathsEliminated)
1221  {
1222        if (numPathsEliminated > 0)
1223        {
1224          if(paths == m_paths)
1225          {
1226            System.err.println("Eliminated " + numPathsEliminated + " total paths!");
1227            System.err.println(
1228              "Consolodated " + numUniquePathsEliminated + " redundent paths!");
1229          }
1230          else
1231          {
1232            System.err.println("Eliminated " + numPathsEliminated + " total global paths!");
1233            System.err.println(
1234              "Consolodated " + numUniquePathsEliminated + " redundent global paths!");
1235          }
1236        }
1237  }
1238
1239
1240  /**
1241   * Assert that the expression is a LocPathIterator, and, if
1242   * not, try to give some diagnostic info.
1243   */

1244  private final void assertIsLocPathIterator(Expression expr1, ExpressionOwner eo)
1245    throws RuntimeException JavaDoc
1246  {
1247        if(!(expr1 instanceof LocPathIterator))
1248        {
1249            String JavaDoc errMsg;
1250            if(expr1 instanceof Variable)
1251            {
1252                errMsg = "Programmer's assertion: expr1 not an iterator: "+
1253                          ((Variable)expr1).getQName();
1254            }
1255            else
1256            {
1257                errMsg = "Programmer's assertion: expr1 not an iterator: "+
1258                          expr1.getClass().getName();
1259            }
1260            throw new RuntimeException JavaDoc(errMsg + ", "+
1261                          eo.getClass().getName()+" "+
1262                          expr1.exprGetParent());
1263        }
1264  }
1265
1266
1267  /**
1268   * Validate some assumptions about the new LocPathIterator and it's
1269   * owner and the state of the list.
1270   */

1271  private static void validateNewAddition(Vector JavaDoc paths, ExpressionOwner owner,
1272                                          LocPathIterator path)
1273        throws RuntimeException JavaDoc
1274  {
1275    assertion(owner.getExpression() == path, "owner.getExpression() != path!!!");
1276    int n = paths.size();
1277    // There should never be any duplicates in the list!
1278
for(int i = 0; i < n; i++)
1279    {
1280        ExpressionOwner ew = (ExpressionOwner)paths.elementAt(i);
1281        assertion(ew != owner, "duplicate owner on the list!!!");
1282        assertion(ew.getExpression() != path, "duplicate expression on the list!!!");
1283    }
1284  }
1285  
1286  /**
1287   * Simple assertion.
1288   */

1289  protected static void assertion(boolean b, String JavaDoc msg)
1290  {
1291    if(!b)
1292    {
1293        throw new RuntimeException JavaDoc(XSLMessages.createMessage(XSLTErrorResources.ER_ASSERT_REDUNDENT_EXPR_ELIMINATOR, new Object JavaDoc[]{msg}));
1294        // "Programmer's assertion in RundundentExprEliminator: "+msg);
1295
}
1296  }
1297  
1298  /**
1299   * Since we want to sort multistep expressions by length, use
1300   * a linked list with elements of type MultistepExprHolder.
1301   */

1302  class MultistepExprHolder implements Cloneable JavaDoc
1303  {
1304    ExpressionOwner m_exprOwner; // Will change to null once we have processed this item.
1305
final int m_stepCount;
1306    MultistepExprHolder m_next;
1307    
1308    /**
1309     * Clone this object.
1310     */

1311    public Object JavaDoc clone()
1312        throws CloneNotSupportedException JavaDoc
1313    {
1314        return super.clone();
1315    }
1316    
1317    /**
1318     * Create a MultistepExprHolder.
1319     *
1320     * @param exprOwner the owner of the expression we are holding.
1321     * It must hold a LocationPathIterator.
1322     * @param stepCount The number of steps in the location path.
1323     */

1324    MultistepExprHolder(ExpressionOwner exprOwner, int stepCount, MultistepExprHolder next)
1325    {
1326        m_exprOwner = exprOwner;
1327        assertion(null != m_exprOwner, "exprOwner can not be null!");
1328        m_stepCount = stepCount;
1329        m_next = next;
1330    }
1331    
1332    /**
1333     * Add a new MultistepExprHolder in sorted order in the list.
1334     *
1335     * @param exprOwner the owner of the expression we are holding.
1336     * It must hold a LocationPathIterator.
1337     * @param stepCount The number of steps in the location path.
1338     * @return The new head of the linked list.
1339     */

1340    MultistepExprHolder addInSortedOrder(ExpressionOwner exprOwner, int stepCount)
1341    {
1342        MultistepExprHolder first = this;
1343        MultistepExprHolder next = this;
1344        MultistepExprHolder prev = null;
1345        while(null != next)
1346        {
1347            if(stepCount >= next.m_stepCount)
1348            {
1349                MultistepExprHolder newholder = new MultistepExprHolder(exprOwner, stepCount, next);
1350                if(null == prev)
1351                    first = newholder;
1352                else
1353                    prev.m_next = newholder;
1354                    
1355                return first;
1356            }
1357            prev = next;
1358            next = next.m_next;
1359        }
1360        
1361        prev.m_next = new MultistepExprHolder(exprOwner, stepCount, null);
1362        return first;
1363    }
1364    
1365    /**
1366     * Remove the given element from the list. 'this' should
1367     * be the head of the list. If the item to be removed is not
1368     * found, an assertion will be made.
1369     *
1370     * @param itemToRemove The item to remove from the list.
1371     * @return The head of the list, which may have changed if itemToRemove
1372     * is the same as this element. Null if the item to remove is the
1373     * only item in the list.
1374     */

1375    MultistepExprHolder unlink(MultistepExprHolder itemToRemove)
1376    {
1377        MultistepExprHolder first = this;
1378        MultistepExprHolder next = this;
1379        MultistepExprHolder prev = null;
1380        while(null != next)
1381        {
1382            if(next == itemToRemove)
1383            {
1384                if(null == prev)
1385                    first = next.m_next;
1386                else
1387                    prev.m_next = next.m_next;
1388                
1389                next.m_next = null;
1390                    
1391                return first;
1392            }
1393            prev = next;
1394            next = next.m_next;
1395        }
1396        
1397        assertion(false, "unlink failed!!!");
1398        return null;
1399    }
1400        
1401    /**
1402     * Get the number of linked list items.
1403     */

1404    int getLength()
1405    {
1406        int count = 0;
1407        MultistepExprHolder next = this;
1408        while(null != next)
1409        {
1410            count++;
1411            next = next.m_next;
1412        }
1413        return count;
1414    }
1415    
1416    /**
1417     * Print diagnostics out for the multistep list.
1418     */

1419    protected void diagnose()
1420    {
1421      System.err.print("Found multistep iterators: " + this.getLength() + " ");
1422      MultistepExprHolder next = this;
1423      while (null != next)
1424      {
1425        System.err.print("" + next.m_stepCount);
1426        next = next.m_next;
1427        if (null != next)
1428              System.err.print(", ");
1429      }
1430      System.err.println();
1431    }
1432    
1433  }
1434
1435}
1436
Popular Tags