← Back to branch summary

~vcs-imports/xena/trunk

« back to all changes in this revision

Viewing changes to ext/src/xalan-j_2_7_1/src/org/apache/xalan/templates/RedundentExprEliminator.java

  • Committer: matthewoliver
  • Date: 2009-12-10 03:18:07 UTC
  • Revision ID: vcs-imports@canonical.com-20091210031807-l086qguzdlljtkl9
Merged Xena Testing into Xena Stable for the Xena 5 release.

Show diffs side-by-side

added added

removed removed

Lines of Context:
ext/src/xalan-j_2_7_1/src/org/apache/xalan/templates/RedundentExprEliminator.java
 
1
/*
 
2
 * Licensed to the Apache Software Foundation (ASF) under one
 
3
 * or more contributor license agreements. See the NOTICE file
 
4
 * distributed with this work for additional information
 
5
 * regarding copyright ownership. The ASF licenses this file
 
6
 * to you under the Apache License, Version 2.0 (the  "License");
 
7
 * you may not use this file except in compliance with the License.
 
8
 * You may obtain a copy of the License at
 
9
 *
 
10
 *     http://www.apache.org/licenses/LICENSE-2.0
 
11
 *
 
12
 * Unless required by applicable law or agreed to in writing, software
 
13
 * distributed under the License is distributed on an "AS IS" BASIS,
 
14
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 
15
 * See the License for the specific language governing permissions and
 
16
 * limitations under the License.
 
17
 */
 
18
/*
 
19
 * $Id: RedundentExprEliminator.java,v 1.2 2009/12/10 03:18:29 matthewoliver Exp $
 
20
 */
 
21
package org.apache.xalan.templates;
 
22
 
 
23
import java.util.Vector;
 
24
 
 
25
import org.apache.xalan.res.XSLMessages;
 
26
import org.apache.xalan.res.XSLTErrorResources;
 
27
import org.apache.xml.utils.QName;
 
28
import org.apache.xml.utils.WrappedRuntimeException;
 
29
import org.apache.xpath.Expression;
 
30
import org.apache.xpath.ExpressionNode;
 
31
import org.apache.xpath.ExpressionOwner;
 
32
import org.apache.xpath.XPath;
 
33
import org.apache.xpath.axes.AxesWalker;
 
34
import org.apache.xpath.axes.FilterExprIteratorSimple;
 
35
import org.apache.xpath.axes.FilterExprWalker;
 
36
import org.apache.xpath.axes.LocPathIterator;
 
37
import org.apache.xpath.axes.SelfIteratorNoPredicate;
 
38
import org.apache.xpath.axes.WalkerFactory;
 
39
import org.apache.xpath.axes.WalkingIterator;
 
40
import org.apache.xpath.operations.Variable;
 
41
import org.apache.xpath.operations.VariableSafeAbsRef;
 
42
 
 
43
/**
 
44
 * This class eleminates redundent XPaths from a given subtree, 
 
45
 * and also collects all absolute paths within the subtree.  First 
 
46
 * it must be called as a visitor to the subtree, and then 
 
47
 * eleminateRedundent must be called.
 
48
 */
 
49
public class RedundentExprEliminator extends XSLTVisitor
 
50
{
 
51
  Vector m_paths;
 
52
  Vector m_absPaths;
 
53
  boolean m_isSameContext;
 
54
  AbsPathChecker m_absPathChecker = new AbsPathChecker();
 
55
  
 
56
  private static int m_uniquePseudoVarID = 1;
 
57
  static final String PSUEDOVARNAMESPACE = Constants.S_VENDORURL+"/xalan/psuedovar";
 
58
 
 
59
  public static final boolean DEBUG = false;
 
60
  public static final boolean DIAGNOSE_NUM_PATHS_REDUCED = false;
 
61
  public static final boolean DIAGNOSE_MULTISTEPLIST = false;
 
62
 
 
63
  /**
 
64
   * So we can reuse it over and over again.
 
65
   */
 
66
  VarNameCollector m_varNameCollector = new VarNameCollector();
 
67
 
 
68
  /**
 
69
   * Construct a RedundentExprEliminator.
 
70
   */
 
71
  public RedundentExprEliminator()
 
72
  {
 
73
    m_isSameContext = true;
 
74
    m_absPaths = new Vector();
 
75
    m_paths = null;
 
76
  }
 
77
  
 
78
  
 
79
  /**
 
80
   * Method to be called after the all expressions within an  
 
81
   * node context have been visited.  It eliminates redundent 
 
82
   * expressions by creating a variable in the psuedoVarRecipient 
 
83
   * for each redundent expression, and then rewriting the redundent 
 
84
   * expression to be a variable reference.
 
85
   * 
 
86
   * @param psuedoVarRecipient The recipient of the psuedo vars.  The 
 
87
   * variables will be inserted as first children of the element, before 
 
88
   * any existing variables.
 
89
   */
 
90
  public void eleminateRedundentLocals(ElemTemplateElement psuedoVarRecipient)
 
91
  {
 
92
    eleminateRedundent(psuedoVarRecipient, m_paths);
 
93
  }
 
94
  
 
95
  /**
 
96
   * Method to be called after the all global expressions within a stylesheet 
 
97
   * have been collected.  It eliminates redundent 
 
98
   * expressions by creating a variable in the psuedoVarRecipient 
 
99
   * 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
}