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    }