WalkerFactory


1   /*
2    * Copyright 1999-2004 The Apache Software Foundation.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *     http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  /*
17   * $Id: WalkerFactory.java,v 1.28 2004/02/17 04:32:08 minchau Exp $
18   */
19  package com.sun.org.apache.xpath.internal.axes;
20  
21  import com.sun.org.apache.xalan.internal.res.XSLMessages;
22  import com.sun.org.apache.xml.internal.dtm.Axis;
23  import com.sun.org.apache.xml.internal.dtm.DTMFilter;
24  import com.sun.org.apache.xml.internal.dtm.DTMIterator;
25  import com.sun.org.apache.xpath.internal.Expression;
26  import com.sun.org.apache.xpath.internal.compiler.Compiler;
27  import com.sun.org.apache.xpath.internal.compiler.FunctionTable;
28  import com.sun.org.apache.xpath.internal.compiler.OpCodes;
29  import com.sun.org.apache.xpath.internal.objects.XNumber;
30  import com.sun.org.apache.xpath.internal.patterns.ContextMatchStepPattern;
31  import com.sun.org.apache.xpath.internal.patterns.FunctionPattern;
32  import com.sun.org.apache.xpath.internal.patterns.NodeTest;
33  import com.sun.org.apache.xpath.internal.patterns.StepPattern;
34  import com.sun.org.apache.xpath.internal.res.XPATHErrorResources;
35  
36  /**
37   * This class is both a factory for XPath location path expressions,
38   * which are built from the opcode map output, and an analysis engine
39   * for the location path expressions in order to provide optimization hints.
40   */
41  public class WalkerFactory
42  {
43  
44    /**
45     * This method is for building an array of possible levels
46     * where the target element(s) could be found for a match.
47     * @param xpath The xpath that is executing.
48     * @param context The current source tree context node.
49     *
50     * @param lpi The owning location path iterator.
51     * @param compiler non-null reference to compiler object that has processed
52     *                 the XPath operations into an opcode map.
53     * @param stepOpCodePos The opcode position for the step.
54     *
55     * @return non-null AxesWalker derivative.
56     *
57     * @throws javax.xml.transform.TransformerException
58     * @xsl.usage advanced
59     */
60    static AxesWalker loadOneWalker(
61            WalkingIterator lpi, Compiler   compiler, int stepOpCodePos)
62              throws javax.xml.transform.TransformerException  
63    {
64  
65      AxesWalker firstWalker = null;
66      int stepType = compiler.getOp(stepOpCodePos);
67  
68      if (stepType != OpCodes.ENDOP)
69      {
70  
71        // m_axesWalkers = new AxesWalker[1];
72        // As we unwind from the recursion, create the iterators.
73        firstWalker = createDefaultWalker(compiler, stepType, lpi, 0);
74  
75        firstWalker.init(compiler, stepOpCodePos, stepType);
76      }
77  
78      return firstWalker;
79    }
80  
81    /**
82     * This method is for building an array of possible levels
83     * where the target element(s) could be found for a match.
84     * @param xpath The xpath that is executing.
85     * @param context The current source tree context node.
86     *
87     * @param lpi The owning location path iterator object.
88     * @param compiler non-null reference to compiler object that has processed
89     *                 the XPath operations into an opcode map.
90     * @param stepOpCodePos The opcode position for the step.
91     * @param stepIndex The top-level step index withing the iterator.
92     *
93     * @return non-null AxesWalker derivative.
94     *
95     * @throws javax.xml.transform.TransformerException
96     * @xsl.usage advanced
97     */
98    static AxesWalker loadWalkers(
99            WalkingIterator lpi, Compiler   compiler, int stepOpCodePos, int stepIndex)
100             throws javax.xml.transform.TransformerException  
101   {
102 
103     int stepType;
104     AxesWalker firstWalker = null;
105     AxesWalker walker, prevWalker = null;
106 
107     int analysis = analyze(compiler, stepOpCodePos, stepIndex);
108 
109     while (OpCodes.ENDOP != (stepType = compiler.getOp(stepOpCodePos)))
110     {
111       walker = createDefaultWalker(compiler, stepOpCodePos, lpi, analysis);
112 
113       walker.init(compiler, stepOpCodePos, stepType);
114       walker.exprSetParent(lpi);
115 
116       // walker.setAnalysis(analysis);
117       if (null == firstWalker)
118       {
119         firstWalker = walker;
120       }
121       else
122       {
123         prevWalker.setNextWalker(walker);
124         walker.setPrevWalker(prevWalker);
125       }
126 
127       prevWalker = walker;
128       stepOpCodePos = compiler.getNextStepPos(stepOpCodePos);
129 
130       if (stepOpCodePos < 0)
131         break;
132     }
133 
134     return firstWalker;
135   }
136   
137   public static boolean isSet(int analysis, int bits)
138   {
139     return (0 != (analysis & bits));
140   }
141   
142   public static void diagnoseIterator(String   name, int analysis, Compiler   compiler)
143   {
144     System.out.println(compiler.toString()+", "+name+", "
145                              + Integer.toBinaryString(analysis) + ", "
146                              + getAnalysisString(analysis));
147   }
148 
149   /**
150    * Create a new LocPathIterator iterator.  The exact type of iterator
151    * returned is based on an analysis of the XPath operations.
152    *
153    * @param compiler non-null reference to compiler object that has processed
154    *                 the XPath operations into an opcode map.
155    * @param opPos The position of the operation code for this itterator.
156    *
157    * @return non-null reference to a LocPathIterator or derivative.
158    *
159    * @throws javax.xml.transform.TransformerException
160    */
161   public static DTMIterator newDTMIterator(
162           Compiler   compiler, int opPos,
163           boolean isTopLevel)
164             throws javax.xml.transform.TransformerException  
165   {
166 
167     int firstStepPos = compiler.getFirstChildPos(opPos);
168     int analysis = analyze(compiler, firstStepPos, 0);
169     boolean isOneStep = isOneStep(analysis);
170     DTMIterator iter;
171 
172     // Is the iteration a one-step attribute pattern (i.e. select="@foo")?
173     if (isOneStep && walksSelfOnly(analysis) && 
174         isWild(analysis) && !hasPredicate(analysis))
175     {
176       if (DEBUG_ITERATOR_CREATION)
177         diagnoseIterator("SelfIteratorNoPredicate", analysis, compiler);
178 
179       // Then use a simple iteration of the attributes, with node test 
180       // and predicate testing.
181       iter = new SelfIteratorNoPredicate(compiler, opPos, analysis);
182     }
183     // Is the iteration exactly one child step?
184     else if (walksChildrenOnly(analysis) && isOneStep)
185     {
186 
187       // Does the pattern specify *any* child with no predicate? (i.e. select="child::node()".
188       if (isWild(analysis) && !hasPredicate(analysis))
189       {
190         if (DEBUG_ITERATOR_CREATION)
191           diagnoseIterator("ChildIterator", analysis, compiler);
192 
193         // Use simple child iteration without any test.
194         iter = new ChildIterator(compiler, opPos, analysis);
195       }
196       else
197       {
198         if (DEBUG_ITERATOR_CREATION)
199           diagnoseIterator("ChildTestIterator", analysis, compiler);
200 
201         // Else use simple node test iteration with predicate test.
202         iter = new ChildTestIterator(compiler, opPos, analysis);
203       }
204     }
205     // Is the iteration a one-step attribute pattern (i.e. select="@foo")?
206     else if (isOneStep && walksAttributes(analysis))
207     {
208       if (DEBUG_ITERATOR_CREATION)
209         diagnoseIterator("AttributeIterator", analysis, compiler);
210 
211       // Then use a simple iteration of the attributes, with node test 
212       // and predicate testing.
213       iter = new AttributeIterator(compiler, opPos, analysis);
214     }
215     else if(isOneStep && !walksFilteredList(analysis))
216     {
217       if( !walksNamespaces(analysis) 
218       && (walksInDocOrder(analysis) || isSet(analysis, BIT_PARENT)))
219       {
220         if (false || DEBUG_ITERATOR_CREATION)
221           diagnoseIterator("OneStepIteratorForward", analysis, compiler);
222   
223         // Then use a simple iteration of the attributes, with node test 
224         // and predicate testing.
225         iter = new OneStepIteratorForward(compiler, opPos, analysis);
226       }
227       else
228       {
229         if (false || DEBUG_ITERATOR_CREATION)
230           diagnoseIterator("OneStepIterator", analysis, compiler);
231   
232         // Then use a simple iteration of the attributes, with node test 
233         // and predicate testing.
234         iter = new OneStepIterator(compiler, opPos, analysis);
235       }
236     }
237 
238     // Analysis of "//center":
239     // bits: 1001000000001010000000000000011
240     // count: 3
241     // root
242     // child:node()
243     // BIT_DESCENDANT_OR_SELF
244     // It's highly possible that we should have a seperate bit set for 
245     // "//foo" patterns.
246     // For at least the time being, we can't optimize patterns like 
247     // "//table[3]", because this has to be analyzed as 
248     // "/descendant-or-self::node()/table[3]" in order for the indexes 
249     // to work right.
250     else if (isOptimizableForDescendantIterator(compiler, firstStepPos, 0)
251               // && getStepCount(analysis) <= 3 
252               // && walksDescendants(analysis) 
253               // && walksSubtreeOnlyFromRootOrContext(analysis)
254              )
255     {
256       if (DEBUG_ITERATOR_CREATION)
257         diagnoseIterator("DescendantIterator", analysis, compiler);
258 
259       iter = new DescendantIterator(compiler, opPos, analysis);
260     }
261     else
262     { 
263       if(isNaturalDocOrder(compiler, firstStepPos, 0, analysis))
264       {
265         if (false || DEBUG_ITERATOR_CREATION)
266         {
267           diagnoseIterator("WalkingIterator", analysis, compiler);
268         }
269   
270         iter = new WalkingIterator(compiler, opPos, analysis, true);
271       }
272       else
273       {
274 //        if (DEBUG_ITERATOR_CREATION)
275 //          diagnoseIterator("MatchPatternIterator", analysis, compiler);
276 //
277 //        return new MatchPatternIterator(compiler, opPos, analysis);
278         if (DEBUG_ITERATOR_CREATION)
279           diagnoseIterator("WalkingIteratorSorted", analysis, compiler);
280 
281         iter = new WalkingIteratorSorted(compiler, opPos, analysis, true);
282       }
283     }
284     if(iter instanceof LocPathIterator)
285       ((LocPathIterator)iter).setIsTopLevel(isTopLevel);
286       
287     return iter;
288   }
289   
290   /**
291    * Special purpose function to see if we can optimize the pattern for 
292    * a DescendantIterator.
293    *
294    * @param compiler non-null reference to compiler object that has processed
295    *                 the XPath operations into an opcode map.
296    * @param stepOpCodePos The opcode position for the step.
297    * @param stepIndex The top-level step index withing the iterator.
298    *
299    * @return 32 bits as an integer that give information about the location
300    * path as a whole.
301    *
302    * @throws javax.xml.transform.TransformerException
303    */
304   public static int getAxisFromStep(
305           Compiler   compiler, int stepOpCodePos)
306             throws javax.xml.transform.TransformerException  
307   {
308 
309     int stepType = compiler.getOp(stepOpCodePos);
310 
311     switch (stepType)
312     {
313     case OpCodes.FROM_FOLLOWING :
314       return Axis.FOLLOWING;
315     case OpCodes.FROM_FOLLOWING_SIBLINGS :
316       return Axis.FOLLOWINGSIBLING;
317     case OpCodes.FROM_PRECEDING :
318       return Axis.PRECEDING;
319     case OpCodes.FROM_PRECEDING_SIBLINGS :
320       return Axis.PRECEDINGSIBLING;
321     case OpCodes.FROM_PARENT :
322       return Axis.PARENT;
323     case OpCodes.FROM_NAMESPACE :
324       return Axis.NAMESPACE;
325     case OpCodes.FROM_ANCESTORS :
326       return Axis.ANCESTOR;
327     case OpCodes.FROM_ANCESTORS_OR_SELF :
328       return Axis.ANCESTORORSELF;
329     case OpCodes.FROM_ATTRIBUTES :
330       return Axis.ATTRIBUTE;
331     case OpCodes.FROM_ROOT :
332       return Axis.ROOT;
333     case OpCodes.FROM_CHILDREN :
334       return Axis.CHILD;
335     case OpCodes.FROM_DESCENDANTS_OR_SELF :
336       return Axis.DESCENDANTORSELF;
337     case OpCodes.FROM_DESCENDANTS :
338       return Axis.DESCENDANT;
339     case OpCodes.FROM_SELF :
340       return Axis.SELF;
341     case OpCodes.OP_EXTFUNCTION :
342     case OpCodes.OP_FUNCTION :
343     case OpCodes.OP_GROUP :
344     case OpCodes.OP_VARIABLE :
345       return Axis.FILTEREDLIST;
346     }
347 
348     throw new RuntimeException  (XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NULL_ERROR_HANDLER, new Object  []{Integer.toString(stepType)})); //"Programmer's assertion: unknown opcode: "
349                                //+ stepType);
350    }
351     
352     /**
353      * Get a corresponding BIT_XXX from an axis.
354      * @param axis One of Axis.ANCESTOR, etc.
355      * @return One of BIT_ANCESTOR, etc.
356      */
357     static public int getAnalysisBitFromAxes(int axis)
358     {
359       switch (axis) // Generate new traverser
360         {
361         case Axis.ANCESTOR :
362           return BIT_ANCESTOR;
363         case Axis.ANCESTORORSELF :
364           return BIT_ANCESTOR_OR_SELF;
365         case Axis.ATTRIBUTE :
366           return BIT_ATTRIBUTE;
367         case Axis.CHILD :
368           return BIT_CHILD;
369         case Axis.DESCENDANT :
370           return BIT_DESCENDANT;
371         case Axis.DESCENDANTORSELF :
372           return BIT_DESCENDANT_OR_SELF;
373         case Axis.FOLLOWING :
374           return BIT_FOLLOWING;
375         case Axis.FOLLOWINGSIBLING :
376           return BIT_FOLLOWING_SIBLING;
377         case Axis.NAMESPACE :
378         case Axis.NAMESPACEDECLS :
379           return BIT_NAMESPACE;
380         case Axis.PARENT :
381           return BIT_PARENT;
382         case Axis.PRECEDING :
383           return BIT_PRECEDING;
384         case Axis.PRECEDINGSIBLING :
385           return BIT_PRECEDING_SIBLING;
386         case Axis.SELF :
387           return BIT_SELF;
388         case Axis.ALLFROMNODE :
389           return BIT_DESCENDANT_OR_SELF;
390           // case Axis.PRECEDINGANDANCESTOR :
391         case Axis.DESCENDANTSFROMROOT :
392         case Axis.ALL :
393         case Axis.DESCENDANTSORSELFFROMROOT :
394           return BIT_ANY_DESCENDANT_FROM_ROOT;
395         case Axis.ROOT :
396           return BIT_ROOT;
397         case Axis.FILTEREDLIST :
398           return BIT_FILTER;
399         default :
400           return BIT_FILTER;
401       }
402     }
403   
404   static boolean functionProximateOrContainsProximate(Compiler   compiler, 
405                                                       int opPos)
406   {
407     int endFunc = opPos + compiler.getOp(opPos + 1) - 1;
408     opPos = compiler.getFirstChildPos(opPos);
409     int funcID = compiler.getOp(opPos);
410     //  System.out.println("funcID: "+funcID);
411     //  System.out.println("opPos: "+opPos);
412     //  System.out.println("endFunc: "+endFunc);
413     switch(funcID)
414     {
415       case FunctionTable.FUNC_LAST:
416       case FunctionTable.FUNC_POSITION:
417         return true;
418       default:
419         opPos++;
420         int i = 0;
421         for (int p = opPos; p < endFunc; p = compiler.getNextOpPos(p), i++)
422         {
423           int innerExprOpPos = p+2;
424           int argOp = compiler.getOp(innerExprOpPos);
425           boolean prox = isProximateInnerExpr(compiler, innerExprOpPos);
426           if(prox)
427             return true;
428         }
429 
430     }
431     return false;
432   }
433   
434   static boolean isProximateInnerExpr(Compiler   compiler, int opPos)
435   {
436     int op = compiler.getOp(opPos);
437     int innerExprOpPos = opPos+2;
438     switch(op)
439     {
440       case OpCodes.OP_ARGUMENT:
441         if(isProximateInnerExpr(compiler, innerExprOpPos))
442           return true;
443         break;
444       case OpCodes.OP_VARIABLE:
445       case OpCodes.OP_NUMBERLIT:
446       case OpCodes.OP_LITERAL:
447       case OpCodes.OP_LOCATIONPATH:
448         break; // OK
449       case OpCodes.OP_FUNCTION:
450         boolean isProx = functionProximateOrContainsProximate(compiler, opPos);
451         if(isProx)
452           return true;
453         break;
454       case OpCodes.OP_GT:
455       case OpCodes.OP_GTE:
456       case OpCodes.OP_LT:
457       case OpCodes.OP_LTE:
458       case OpCodes.OP_EQUALS:
459         int leftPos = compiler.getFirstChildPos(op);
460         int rightPos = compiler.getNextOpPos(leftPos);
461         isProx = isProximateInnerExpr(compiler, leftPos);
462         if(isProx)
463           return true;
464         isProx = isProximateInnerExpr(compiler, rightPos);
465         if(isProx)
466           return true;
467         break;
468       default:
469         return true; // be conservative...
470     }
471     return false;
472   }
473     
474   /**
475    * Tell if the predicates need to have proximity knowledge.
476    */
477   public static boolean mightBeProximate(Compiler   compiler, int opPos, int stepType)
478           throws javax.xml.transform.TransformerException  
479   {
480 
481     boolean mightBeProximate = false;
482     int argLen;
483 
484     switch (stepType)
485     {
486     case OpCodes.OP_VARIABLE :
487     case OpCodes.OP_EXTFUNCTION :
488     case OpCodes.OP_FUNCTION :
489     case OpCodes.OP_GROUP :
490       argLen = compiler.getArgLength(opPos);
491       break;
492     default :
493       argLen = compiler.getArgLengthOfStep(opPos);
494     }
495 
496     int predPos = compiler.getFirstPredicateOpPos(opPos);
497     int count = 0;
498 
499     while (OpCodes.OP_PREDICATE == compiler.getOp(predPos))
500     {
501       count++;
502       
503       int innerExprOpPos = predPos+2;
504       int predOp = compiler.getOp(innerExprOpPos);
505 
506       switch(predOp)
507       {
508         case OpCodes.OP_VARIABLE:
509             return true; // Would need more smarts to tell if this could be a number or not!
510         case OpCodes.OP_LOCATIONPATH:
511           // OK.
512           break;
513         case OpCodes.OP_NUMBER:
514         case OpCodes.OP_NUMBERLIT:
515           return true; // that's all she wrote!
516         case OpCodes.OP_FUNCTION:
517           boolean isProx 
518             = functionProximateOrContainsProximate(compiler, innerExprOpPos);
519           if(isProx)
520             return true;
521           break;
522         case OpCodes.OP_GT:
523         case OpCodes.OP_GTE:
524         case OpCodes.OP_LT:
525         case OpCodes.OP_LTE:
526         case OpCodes.OP_EQUALS:
527           int leftPos = compiler.getFirstChildPos(innerExprOpPos);
528           int rightPos = compiler.getNextOpPos(leftPos);
529           isProx = isProximateInnerExpr(compiler, leftPos);
530           if(isProx)
531             return true;
532           isProx = isProximateInnerExpr(compiler, rightPos);
533           if(isProx)
534             return true;
535           break;
536         default:
537           return true; // be conservative...
538       }
539 
540       predPos = compiler.getNextOpPos(predPos);
541     }
542 
543     return mightBeProximate;
544   }
545   
546   /**
547    * Special purpose function to see if we can optimize the pattern for 
548    * a DescendantIterator.
549    *
550    * @param compiler non-null reference to compiler object that has processed
551    *                 the XPath operations into an opcode map.
552    * @param stepOpCodePos The opcode position for the step.
553    * @param stepIndex The top-level step index withing the iterator.
554    *
555    * @return 32 bits as an integer that give information about the location
556    * path as a whole.
557    *
558    * @throws javax.xml.transform.TransformerException
559    */
560   private static boolean isOptimizableForDescendantIterator(
561           Compiler   compiler, int stepOpCodePos, int stepIndex)
562             throws javax.xml.transform.TransformerException  
563   {
564 
565     int stepType;
566     int stepCount = 0;
567     boolean foundDorDS = false;
568     boolean foundSelf = false;
569     boolean foundDS = false;
570     
571     int nodeTestType = OpCodes.NODETYPE_NODE;
572     
573     while (OpCodes.ENDOP != (stepType = compiler.getOp(stepOpCodePos)))
574     {
575       // The DescendantIterator can only do one node test.  If there's more 
576       // than one, use another iterator.
577       if(nodeTestType != OpCodes.NODETYPE_NODE && nodeTestType != OpCodes.NODETYPE_ROOT)
578         return false;
579         
580       stepCount++;
581       if(stepCount > 3)
582         return false;
583         
584       boolean mightBeProximate = mightBeProximate(compiler, stepOpCodePos, stepType);
585       if(mightBeProximate)
586         return false;
587 
588       switch (stepType)
589       {
590       case OpCodes.FROM_FOLLOWING :
591       case OpCodes.FROM_FOLLOWING_SIBLINGS :
592       case OpCodes.FROM_PRECEDING :
593       case OpCodes.FROM_PRECEDING_SIBLINGS :
594       case OpCodes.FROM_PARENT :
595       case OpCodes.OP_VARIABLE :
596       case OpCodes.OP_EXTFUNCTION :
597       case OpCodes.OP_FUNCTION :
598       case OpCodes.OP_GROUP :
599       case OpCodes.FROM_NAMESPACE :
600       case OpCodes.FROM_ANCESTORS :
601       case OpCodes.FROM_ANCESTORS_OR_SELF :
602       case OpCodes.FROM_ATTRIBUTES :
603       case OpCodes.MATCH_ATTRIBUTE :
604       case OpCodes.MATCH_ANY_ANCESTOR :
605       case OpCodes.MATCH_IMMEDIATE_ANCESTOR :
606         return false;
607       case OpCodes.FROM_ROOT :
608         if(1 != stepCount)
609           return false;
610         break;
611       case OpCodes.FROM_CHILDREN :
612         if(!foundDS && !(foundDorDS && foundSelf))
613           return false;
614         break;
615       case OpCodes.FROM_DESCENDANTS_OR_SELF :
616         foundDS = true;
617       case OpCodes.FROM_DESCENDANTS :
618         if(3 == stepCount)
619           return false;
620         foundDorDS = true;
621         break;
622       case OpCodes.FROM_SELF :
623         if(1 != stepCount)
624           return false;
625         foundSelf = true;
626         break;
627       default :
628         throw new RuntimeException  (XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NULL_ERROR_HANDLER, new Object  []{Integer.toString(stepType)})); //"Programmer's assertion: unknown opcode: "
629                                   // + stepType);
630       }
631       
632       nodeTestType = compiler.getStepTestType(stepOpCodePos);
633 
634       int nextStepOpCodePos = compiler.getNextStepPos(stepOpCodePos);
635 
636       if (nextStepOpCodePos < 0)
637         break;
638         
639       if(OpCodes.ENDOP != compiler.getOp(nextStepOpCodePos))
640       {
641         if(compiler.countPredicates(stepOpCodePos) > 0)
642         {
643           return false;
644         }
645       }
646       
647       stepOpCodePos = nextStepOpCodePos;
648     }
649 
650     return true;
651   }
652 
653   /**
654    * Analyze the location path and return 32 bits that give information about
655    * the location path as a whole.  See the BIT_XXX constants for meaning about
656    * each of the bits.
657    *
658    * @param compiler non-null reference to compiler object that has processed
659    *                 the XPath operations into an opcode map.
660    * @param stepOpCodePos The opcode position for the step.
661    * @param stepIndex The top-level step index withing the iterator.
662    *
663    * @return 32 bits as an integer that give information about the location
664    * path as a whole.
665    *
666    * @throws javax.xml.transform.TransformerException
667    */
668   private static int analyze(
669           Compiler   compiler, int stepOpCodePos, int stepIndex)
670             throws javax.xml.transform.TransformerException  
671   {
672 
673     int stepType;
674     int stepCount = 0;
675     int analysisResult = 0x00000000;  // 32 bits of analysis
676 
677     while (OpCodes.ENDOP != (stepType = compiler.getOp(stepOpCodePos)))
678     {
679       stepCount++;
680 
681       // String namespace = compiler.getStepNS(stepOpCodePos);
682       // boolean isNSWild = (null != namespace) 
683       //                   ? namespace.equals(NodeTest.WILD) : false;
684       // String localname = compiler.getStepLocalName(stepOpCodePos);
685       // boolean isWild = (null != localname) ? localname.equals(NodeTest.WILD) : false;
686       boolean predAnalysis = analyzePredicate(compiler, stepOpCodePos,
687                                               stepType);
688 
689       if (predAnalysis)
690         analysisResult |= BIT_PREDICATE;
691 
692       switch (stepType)
693       {
694       case OpCodes.OP_VARIABLE :
695       case OpCodes.OP_EXTFUNCTION :
696       case OpCodes.OP_FUNCTION :
697       case OpCodes.OP_GROUP :
698         analysisResult |= BIT_FILTER;
699         break;
700       case OpCodes.FROM_ROOT :
701         analysisResult |= BIT_ROOT;
702         break;
703       case OpCodes.FROM_ANCESTORS :
704         analysisResult |= BIT_ANCESTOR;
705         break;
706       case OpCodes.FROM_ANCESTORS_OR_SELF :
707         analysisResult |= BIT_ANCESTOR_OR_SELF;
708         break;
709       case OpCodes.FROM_ATTRIBUTES :
710         analysisResult |= BIT_ATTRIBUTE;
711         break;
712       case OpCodes.FROM_NAMESPACE :
713         analysisResult |= BIT_NAMESPACE;
714         break;
715       case OpCodes.FROM_CHILDREN :
716         analysisResult |= BIT_CHILD;
717         break;
718       case OpCodes.FROM_DESCENDANTS :
719         analysisResult |= BIT_DESCENDANT;
720         break;
721       case OpCodes.FROM_DESCENDANTS_OR_SELF :
722 
723         // Use a special bit to to make sure we get the right analysis of "//foo".
724         if (2 == stepCount && BIT_ROOT == analysisResult)
725         {
726           analysisResult |= BIT_ANY_DESCENDANT_FROM_ROOT;
727         }
728 
729         analysisResult |= BIT_DESCENDANT_OR_SELF;
730         break;
731       case OpCodes.FROM_FOLLOWING :
732         analysisResult |= BIT_FOLLOWING;
733         break;
734       case OpCodes.FROM_FOLLOWING_SIBLINGS :
735         analysisResult |= BIT_FOLLOWING_SIBLING;
736         break;
737       case OpCodes.FROM_PRECEDING :
738         analysisResult |= BIT_PRECEDING;
739         break;
740       case OpCodes.FROM_PRECEDING_SIBLINGS :
741         analysisResult |= BIT_PRECEDING_SIBLING;
742         break;
743       case OpCodes.FROM_PARENT :
744         analysisResult |= BIT_PARENT;
745         break;
746       case OpCodes.FROM_SELF :
747         analysisResult |= BIT_SELF;
748         break;
749       case OpCodes.MATCH_ATTRIBUTE :
750         analysisResult |= (BIT_MATCH_PATTERN | BIT_ATTRIBUTE);
751         break;
752       case OpCodes.MATCH_ANY_ANCESTOR :
753         analysisResult |= (BIT_MATCH_PATTERN | BIT_ANCESTOR);
754         break;
755       case OpCodes.MATCH_IMMEDIATE_ANCESTOR :
756         analysisResult |= (BIT_MATCH_PATTERN | BIT_PARENT);
757         break;
758       default :
759         throw new RuntimeException  (XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NULL_ERROR_HANDLER, new Object  []{Integer.toString(stepType)})); //"Programmer's assertion: unknown opcode: "
760                                    //+ stepType);
761       }
762 
763       if (OpCodes.NODETYPE_NODE == compiler.getOp(stepOpCodePos + 3))  // child::node()
764       {
765         analysisResult |= BIT_NODETEST_ANY;
766       }
767 
768       stepOpCodePos = compiler.getNextStepPos(stepOpCodePos);
769 
770       if (stepOpCodePos < 0)
771         break;
772     }
773 
774     analysisResult |= (stepCount & BITS_COUNT);
775 
776     return analysisResult;
777   }
778   
779   /**
780    * Tell if the given axis goes downword.  Bogus name, if you can think of 
781    * a better one, please do tell.  This really has to do with inverting 
782    * attribute axis.
783    * @param axis One of Axis.XXX.
784    * @return true if the axis is not a child axis and does not go up from 
785    * the axis root.
786    */
787   public static boolean isDownwardAxisOfMany(int axis)
788   {
789     return ((Axis.DESCENDANTORSELF == axis) ||
790           (Axis.DESCENDANT == axis) 
791           || (Axis.FOLLOWING == axis) 
792 //          || (Axis.FOLLOWINGSIBLING == axis) 
793           || (Axis.PRECEDING == axis) 
794 //          || (Axis.PRECEDINGSIBLING == axis)
795           );
796   }
797 
798   /**
799    * Read a <a HREF="http://www.w3.org/TR/xpath#location-paths">LocationPath</a>
800    * as a generalized match pattern.  What this means is that the LocationPath
801    * is read backwards, as a test on a given node, to see if it matches the
802    * criteria of the selection, and ends up at the context node.  Essentially,
803    * this is a backwards query from a given node, to find the context node.
804    * <p>So, the selection "foo/daz[2]" is, in non-abreviated expanded syntax,
805    * "self::node()/following-sibling::foo/child::daz[position()=2]".
806    * Taking this as a match pattern for a probable node, it works out to
807    * "self::daz/parent::foo[child::daz[position()=2 and isPrevStepNode()]
808    * precedingSibling::node()[isContextNodeOfLocationPath()]", adding magic
809    * isPrevStepNode and isContextNodeOfLocationPath operations.  Predicates in
810    * the location path have to be executed by the following step,
811    * because they have to know the context of their execution.
812    *
813    * @param mpi The MatchPatternIterator to which the steps will be attached.
814    * @param compiler The compiler that holds the syntax tree/op map to
815    * construct from.
816    * @param stepOpCodePos The current op code position within the opmap.
817    * @param stepIndex The top-level step index withing the iterator.
818    *
819    * @return A StepPattern object, which may contain relative StepPatterns.
820    *
821    * @throws javax.xml.transform.TransformerException
822    */
823   static StepPattern loadSteps(
824           MatchPatternIterator mpi, Compiler   compiler, int stepOpCodePos, 
825                                                        int stepIndex)
826             throws javax.xml.transform.TransformerException  
827   {
828     if (DEBUG_PATTERN_CREATION)
829     {
830       System.out.println("================");
831       System.out.println("loadSteps for: "+compiler.getPatternString());
832     }
833     int stepType;
834     StepPattern step = null;
835     StepPattern firstStep = null, prevStep = null;
836     int analysis = analyze(compiler, stepOpCodePos, stepIndex);
837 
838     while (OpCodes.ENDOP != (stepType = compiler.getOp(stepOpCodePos)))
839     {
840       step = createDefaultStepPattern(compiler, stepOpCodePos, mpi, analysis,
841                                       firstStep, prevStep);
842 
843       if (null == firstStep)
844       {
845         firstStep = step;
846       }
847       else
848       {
849 
850         //prevStep.setNextWalker(step);
851         step.setRelativePathPattern(prevStep);
852       }
853 
854       prevStep = step;
855       stepOpCodePos = compiler.getNextStepPos(stepOpCodePos);
856 
857       if (stepOpCodePos < 0)
858         break;
859     }
860     
861     int axis = Axis.SELF;
862     int paxis = Axis.SELF;
863     StepPattern tail = step;
864     for (StepPattern pat = step; null != pat; 
865          pat = pat.getRelativePathPattern()) 
866     {
867       int nextAxis = pat.getAxis();
868       //int nextPaxis = pat.getPredicateAxis();
869       pat.setAxis(axis);
870       
871       // The predicate axis can't be moved!!!  Test Axes103
872       // pat.setPredicateAxis(paxis);
873       
874       // If we have an attribute or namespace axis that went up, then 
875       // it won't find the attribute in the inverse, since the select-to-match
876       // axes are not invertable (an element is a parent of an attribute, but 
877       // and attribute is not a child of an element).
878       // If we don't do the magic below, then "@*/ancestor-or-self::*" gets
879       // inverted for match to "self::*/descendant-or-self::@*/parent::node()",
880       // which obviously won't work.
881       // So we will rewrite this as:
882       // "self::*/descendant-or-self::*/attribute::*/parent::node()"
883       // Child has to be rewritten a little differently:
884       // select: "@*/parent::*"
885       // inverted match: "self::*/child::@*/parent::node()"
886       // rewrite: "self::*/attribute::*/parent::node()"
887       // Axes that go down in the select, do not have to have special treatment 
888       // in the rewrite. The following inverted match will still not select 
889       // anything.
890       // select: "@*/child::*"
891       // inverted match: "self::*/parent::@*/parent::node()"
892       // Lovely business, this.
893       // -sb
894       int whatToShow = pat.getWhatToShow();
895       if(whatToShow == DTMFilter.SHOW_ATTRIBUTE || 
896          whatToShow == DTMFilter.SHOW_NAMESPACE)
897       {
898         int newAxis = (whatToShow == DTMFilter.SHOW_ATTRIBUTE) ? 
899                        Axis.ATTRIBUTE : Axis.NAMESPACE;
900         if(isDownwardAxisOfMany(axis))
901         {
902           StepPattern attrPat = new StepPattern(whatToShow, 
903                                     pat.getNamespace(),
904                                     pat.getLocalName(),
905                                 //newAxis, pat.getPredicateAxis);
906                                                 newAxis, 0); // don't care about the predicate axis
907           XNumber score = pat.getStaticScore();
908           pat.setNamespace(null);
909           pat.setLocalName(NodeTest.WILD);
910           attrPat.setPredicates(pat.getPredicates());
911           pat.setPredicates(null);
912           pat.setWhatToShow(DTMFilter.SHOW_ELEMENT);
913           StepPattern rel = pat.getRelativePathPattern();
914           pat.setRelativePathPattern(attrPat);
915           attrPat.setRelativePathPattern(rel);
916           attrPat.setStaticScore(score);
917           
918           // This is needed to inverse a following pattern, because of the 
919           // wacky Xalan rules for following from an attribute.  See axes108.
920           // By these rules, following from an attribute is not strictly 
921           // inverseable.
922           if(Axis.PRECEDING == pat.getAxis())
923             pat.setAxis(Axis.PRECEDINGANDANCESTOR);
924             
925           else if(Axis.DESCENDANT == pat.getAxis())
926             pat.setAxis(Axis.DESCENDANTORSELF);
927           
928           pat = attrPat;
929         }
930         else if(Axis.CHILD == pat.getAxis())
931         {
932           // In this case just change the axis.
933           // pat.setWhatToShow(whatToShow);
934           pat.setAxis(Axis.ATTRIBUTE);
935         }
936       }
937       axis = nextAxis;
938       //paxis = nextPaxis;
939       tail = pat;
940     }
941     
942     if(axis < Axis.ALL)
943     {
944       StepPattern selfPattern = new ContextMatchStepPattern(axis, paxis);
945       // We need to keep the new nodetest from affecting the score...
946       XNumber score = tail.getStaticScore();
947       tail.setRelativePathPattern(selfPattern);
948       tail.setStaticScore(score);
949       selfPattern.setStaticScore(score);
950     }        
951 
952     if (DEBUG_PATTERN_CREATION)
953     {
954       System.out.println("Done loading steps: "+step.toString());
955             
956       System.out.println("");
957     }
958     return step;  // start from last pattern?? //firstStep;
959   }
960 
961   /**
962    * Create a StepPattern that is contained within a LocationPath.
963    *
964    *
965    * @param compiler The compiler that holds the syntax tree/op map to
966    * construct from.
967    * @param stepOpCodePos The current op code position within the opmap.
968    * @param mpi The MatchPatternIterator to which the steps will be attached.
969    * @param analysis 32 bits of analysis, from which the type of AxesWalker
970    *                 may be influenced.
971    * @param tail The step that is the first step analyzed, but the last 
972    *                  step in the relative match linked list, i.e. the tail.
973    *                  May be null.
974    * @param head The step that is the current head of the relative 
975    *                 match step linked list.
976    *                 May be null.
977    *
978    * @return the head of the list.
979    *
980    * @throws javax.xml.transform.TransformerException
981    */
982   private static StepPattern createDefaultStepPattern(
983           Compiler   compiler, int opPos, MatchPatternIterator mpi, 
984           int analysis, StepPattern tail, StepPattern head)
985             throws javax.xml.transform.TransformerException  
986   {
987 
988     int stepType = compiler.getOp(opPos);
989     boolean simpleInit = false;
990     int totalNumberWalkers = (analysis & BITS_COUNT);
991     boolean prevIsOneStepDown = true;
992     int firstStepPos = compiler.getFirstChildPos(opPos);
993     
994     int whatToShow = compiler.getWhatToShow(opPos);
995     StepPattern ai = null;
996     int axis, predicateAxis;
997     
998     switch (stepType)
999     {
1000    case OpCodes.OP_VARIABLE :
1001    case OpCodes.OP_EXTFUNCTION :
1002    case OpCodes.OP_FUNCTION :
1003    case OpCodes.OP_GROUP :
1004      prevIsOneStepDown = false;
1005
1006      Expression expr;
1007
1008      switch (stepType)
1009      {
1010      case OpCodes.OP_VARIABLE :
1011      case OpCodes.OP_EXTFUNCTION :
1012      case OpCodes.OP_FUNCTION :
1013      case OpCodes.OP_GROUP :
1014        expr = compiler.compile(opPos);
1015        break;
1016      default :
1017        expr = compiler.compile(opPos + 2);
1018      }
1019
1020      axis = Axis.FILTEREDLIST;
1021      predicateAxis = Axis.FILTEREDLIST;
1022      ai = new FunctionPattern(expr, axis, predicateAxis);
1023      simpleInit = true;
1024      break;
1025    case OpCodes.FROM_ROOT :
1026      whatToShow = DTMFilter.SHOW_DOCUMENT
1027                   | DTMFilter.SHOW_DOCUMENT_FRAGMENT;
1028
1029      axis = Axis.ROOT;
1030      predicateAxis = Axis.ROOT;
1031      ai = new StepPattern(DTMFilter.SHOW_DOCUMENT | 
1032                                DTMFilter.SHOW_DOCUMENT_FRAGMENT,
1033                                axis, predicateAxis);
1034      break;
1035    case OpCodes.FROM_ATTRIBUTES :
1036      whatToShow = DTMFilter.SHOW_ATTRIBUTE;
1037      axis = Axis.PARENT;
1038      predicateAxis = Axis.ATTRIBUTE;
1039      // ai = new StepPattern(whatToShow, Axis.SELF, Axis.SELF);
1040      break;
1041    case OpCodes.FROM_NAMESPACE :
1042      whatToShow = DTMFilter.SHOW_NAMESPACE;
1043      axis = Axis.PARENT;
1044      predicateAxis = Axis.NAMESPACE;
1045      // ai = new StepPattern(whatToShow, axis, predicateAxis);
1046      break;
1047    case OpCodes.FROM_ANCESTORS :
1048      axis = Axis.DESCENDANT;
1049      predicateAxis = Axis.ANCESTOR;
1050      break;
1051    case OpCodes.FROM_CHILDREN :
1052      axis = Axis.PARENT;
1053      predicateAxis = Axis.CHILD;
1054      break;
1055    case OpCodes.FROM_ANCESTORS_OR_SELF :
1056      axis = Axis.DESCENDANTORSELF;
1057      predicateAxis = Axis.ANCESTORORSELF;
1058      break;
1059    case OpCodes.FROM_SELF :
1060      axis = Axis.SELF;
1061      predicateAxis = Axis.SELF;
1062      break;
1063    case OpCodes.FROM_PARENT :
1064      axis = Axis.CHILD;
1065      predicateAxis = Axis.PARENT;
1066      break;
1067    case OpCodes.FROM_PRECEDING_SIBLINGS :
1068      axis = Axis.FOLLOWINGSIBLING;
1069      predicateAxis = Axis.PRECEDINGSIBLING;
1070      break;
1071    case OpCodes.FROM_PRECEDING :
1072      axis = Axis.FOLLOWING;
1073      predicateAxis = Axis.PRECEDING;
1074      break;
1075    case OpCodes.FROM_FOLLOWING_SIBLINGS :
1076      axis = Axis.PRECEDINGSIBLING;
1077      predicateAxis = Axis.FOLLOWINGSIBLING;
1078      break;
1079    case OpCodes.FROM_FOLLOWING :
1080      axis = Axis.PRECEDING;
1081      predicateAxis = Axis.FOLLOWING;
1082      break;
1083    case OpCodes.FROM_DESCENDANTS_OR_SELF :
1084      axis = Axis.ANCESTORORSELF;
1085      predicateAxis = Axis.DESCENDANTORSELF;
1086      break;
1087    case OpCodes.FROM_DESCENDANTS :
1088      axis = Axis.ANCESTOR;
1089      predicateAxis = Axis.DESCENDANT;
1090      break;
1091    default :
1092      throw new RuntimeException  (XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NULL_ERROR_HANDLER, new Object  []{Integer.toString(stepType)})); //"Programmer's assertion: unknown opcode: "
1093                                 //+ stepType);
1094    }
1095    if(null == ai)
1096    {
1097      whatToShow = compiler.getWhatToShow(opPos); // %REVIEW%
1098      ai = new StepPattern(whatToShow, compiler.getStepNS(opPos),
1099                                compiler.getStepLocalName(opPos),
1100                                axis, predicateAxis);
1101    }
1102   
1103    if (false || DEBUG_PATTERN_CREATION)
1104    {
1105      System.out.print("new step: "+ ai);
1106      System.out.print(", axis: " + Axis.names[ai.getAxis()]);
1107      System.out.print(", predAxis: " + Axis.names[ai.getAxis()]);
1108      System.out.print(", what: ");
1109      System.out.print("    ");
1110      ai.debugWhatToShow(ai.getWhatToShow());
1111    }
1112
1113    int argLen = compiler.getFirstPredicateOpPos(opPos);
1114
1115    ai.setPredicates(compiler.getCompiledPredicates(argLen));
1116
1117    return ai;
1118  }
1119
1120  /**
1121   * Analyze a step and give information about it's predicates.  Right now this
1122   * just returns true or false if the step has a predicate.
1123   *
1124   * @param compiler non-null reference to compiler object that has processed
1125   *                 the XPath operations into an opcode map.
1126   * @param opPos The opcode position for the step.
1127   * @param stepType The type of step, one of OP_GROUP, etc.
1128   *
1129   * @return true if step has a predicate.
1130   *
1131   * @throws javax.xml.transform.TransformerException
1132   */
1133  static boolean analyzePredicate(Compiler   compiler, int opPos, int stepType)
1134          throws javax.xml.transform.TransformerException  
1135  {
1136
1137    int argLen;
1138
1139    switch (stepType)
1140    {
1141    case OpCodes.OP_VARIABLE :
1142    case OpCodes.OP_EXTFUNCTION :
1143    case OpCodes.OP_FUNCTION :
1144    case OpCodes.OP_GROUP :
1145      argLen = compiler.getArgLength(opPos);
1146      break;
1147    default :
1148      argLen = compiler.getArgLengthOfStep(opPos);
1149    }
1150
1151    int pos = compiler.getFirstPredicateOpPos(opPos);
1152    int nPredicates = compiler.countPredicates(pos);
1153
1154    return (nPredicates > 0) ? true : false;
1155  }
1156
1157  /**
1158   * Create the proper Walker from the axes type.
1159   *
1160   * @param compiler non-null reference to compiler object that has processed
1161   *                 the XPath operations into an opcode map.
1162   * @param opPos The opcode position for the step.
1163   * @param lpi The owning location path iterator.
1164   * @param analysis 32 bits of analysis, from which the type of AxesWalker
1165   *                 may be influenced.
1166   *
1167   * @return non-null reference to AxesWalker derivative.
1168   * @throws RuntimeException if the input is bad.
1169   */
1170  private static AxesWalker createDefaultWalker(Compiler   compiler, int opPos,
1171          WalkingIterator lpi, int analysis)
1172  {
1173
1174    AxesWalker ai = null;
1175    int stepType = compiler.getOp(opPos);
1176
1177    /*
1178    System.out.println("0: "+compiler.getOp(opPos));
1179    System.out.println("1: "+compiler.getOp(opPos+1));
1180    System.out.println("2: "+compiler.getOp(opPos+2));
1181    System.out.println("3: "+compiler.getOp(opPos+3));
1182    System.out.println("4: "+compiler.getOp(opPos+4));
1183    System.out.println("5: "+compiler.getOp(opPos+5));
1184    */
1185    boolean simpleInit = false;
1186    int totalNumberWalkers = (analysis & BITS_COUNT);
1187    boolean prevIsOneStepDown = true;
1188
1189    switch (stepType)
1190    {
1191    case OpCodes.OP_VARIABLE :
1192    case OpCodes.OP_EXTFUNCTION :
1193    case OpCodes.OP_FUNCTION :
1194    case OpCodes.OP_GROUP :
1195      prevIsOneStepDown = false;
1196
1197      if (DEBUG_WALKER_CREATION)
1198        System.out.println("new walker:  FilterExprWalker: " + analysis
1199                           + ", " + compiler.toString());
1200
1201      ai = new FilterExprWalker(lpi);
1202      simpleInit = true;
1203      break;
1204    case OpCodes.FROM_ROOT :
1205      ai = new AxesWalker(lpi, Axis.ROOT);
1206      break;
1207    case OpCodes.FROM_ANCESTORS :
1208      prevIsOneStepDown = false;
1209      ai = new ReverseAxesWalker(lpi, Axis.ANCESTOR);
1210      break;
1211    case OpCodes.FROM_ANCESTORS_OR_SELF :
1212      prevIsOneStepDown = false;
1213      ai = new ReverseAxesWalker(lpi, Axis.ANCESTORORSELF);
1214      break;
1215    case OpCodes.FROM_ATTRIBUTES :
1216      ai = new AxesWalker(lpi, Axis.ATTRIBUTE);
1217      break;
1218    case OpCodes.FROM_NAMESPACE :
1219      ai = new AxesWalker(lpi, Axis.NAMESPACE);
1220      break;
1221    case OpCodes.FROM_CHILDREN :
1222      ai = new AxesWalker(lpi, Axis.CHILD);
1223      break;
1224    case OpCodes.FROM_DESCENDANTS :
1225      prevIsOneStepDown = false;
1226      ai = new AxesWalker(lpi, Axis.DESCENDANT);
1227      break;
1228    case OpCodes.FROM_DESCENDANTS_OR_SELF :
1229      prevIsOneStepDown = false;
1230      ai = new AxesWalker(lpi, Axis.DESCENDANTORSELF);
1231      break;
1232    case OpCodes.FROM_FOLLOWING :
1233      prevIsOneStepDown = false;
1234      ai = new AxesWalker(lpi, Axis.FOLLOWING);
1235      break;
1236    case OpCodes.FROM_FOLLOWING_SIBLINGS :
1237      prevIsOneStepDown = false;
1238      ai = new AxesWalker(lpi, Axis.FOLLOWINGSIBLING);
1239      break;
1240    case OpCodes.FROM_PRECEDING :
1241      prevIsOneStepDown = false;
1242      ai = new ReverseAxesWalker(lpi, Axis.PRECEDING);
1243      break;
1244    case OpCodes.FROM_PRECEDING_SIBLINGS :
1245      prevIsOneStepDown = false;
1246      ai = new ReverseAxesWalker(lpi, Axis.PRECEDINGSIBLING);
1247      break;
1248    case OpCodes.FROM_PARENT :
1249      prevIsOneStepDown = false;
1250      ai = new ReverseAxesWalker(lpi, Axis.PARENT);
1251      break;
1252    case OpCodes.FROM_SELF :
1253      ai = new AxesWalker(lpi, Axis.SELF);
1254      break;
1255    default :
1256      throw new RuntimeException  (XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NULL_ERROR_HANDLER, new Object  []{Integer.toString(stepType)})); //"Programmer's assertion: unknown opcode: "
1257                                 //+ stepType);
1258    }
1259
1260    if (simpleInit)
1261    {
1262      ai.initNodeTest(DTMFilter.SHOW_ALL);
1263    }
1264    else
1265    {
1266      int whatToShow = compiler.getWhatToShow(opPos);
1267
1268      /*
1269      System.out.print("construct: ");
1270      NodeTest.debugWhatToShow(whatToShow);
1271      System.out.println("or stuff: "+(whatToShow & (DTMFilter.SHOW_ATTRIBUTE
1272                             | DTMFilter.SHOW_ELEMENT
1273                             | DTMFilter.SHOW_PROCESSING_INSTRUCTION)));
1274      */
1275      if ((0 == (whatToShow
1276                 & (DTMFilter.SHOW_ATTRIBUTE | DTMFilter.SHOW_NAMESPACE | DTMFilter.SHOW_ELEMENT
1277                    | DTMFilter.SHOW_PROCESSING_INSTRUCTION))) || (whatToShow == DTMFilter.SHOW_ALL))
1278        ai.initNodeTest(whatToShow);
1279      else
1280      {
1281        ai.initNodeTest(whatToShow, compiler.getStepNS(opPos),
1282                        compiler.getStepLocalName(opPos));
1283      }
1284    }
1285
1286    return ai;
1287  }
1288  
1289  public static String   getAnalysisString(int analysis)
1290  {
1291    StringBuffer   buf = new StringBuffer  ();
1292    buf.append("count: "+getStepCount(analysis)+" ");
1293    if((analysis & BIT_NODETEST_ANY) != 0)
1294    {
1295      buf.append("NTANY|");
1296    }
1297    if((analysis & BIT_PREDICATE) != 0)
1298    {
1299      buf.append("PRED|");
1300    }
1301    if((analysis & BIT_ANCESTOR) != 0)
1302    {
1303      buf.append("ANC|");
1304    }
1305    if((analysis & BIT_ANCESTOR_OR_SELF) != 0)
1306    {
1307      buf.append("ANCOS|");
1308    }
1309    if((analysis & BIT_ATTRIBUTE) != 0)
1310    {
1311      buf.append("ATTR|");
1312    }
1313    if((analysis & BIT_CHILD) != 0)
1314    {
1315      buf.append("CH|");
1316    }
1317    if((analysis & BIT_DESCENDANT) != 0)
1318    {
1319      buf.append("DESC|");
1320    }
1321    if((analysis & BIT_DESCENDANT_OR_SELF) != 0)
1322    {
1323      buf.append("DESCOS|");
1324    }
1325    if((analysis & BIT_FOLLOWING) != 0)
1326    {
1327      buf.append("FOL|");
1328    }
1329    if((analysis & BIT_FOLLOWING_SIBLING) != 0)
1330    {
1331      buf.append("FOLS|");
1332    }
1333    if((analysis & BIT_NAMESPACE) != 0)
1334    {
1335      buf.append("NS|");
1336    }
1337    if((analysis & BIT_PARENT) != 0)
1338    {
1339      buf.append("P|");
1340    }
1341    if((analysis & BIT_PRECEDING) != 0)
1342    {
1343      buf.append("PREC|");
1344    }
1345    if((analysis & BIT_PRECEDING_SIBLING) != 0)
1346    {
1347      buf.append("PRECS|");
1348    }
1349    if((analysis & BIT_SELF) != 0)
1350    {
1351      buf.append(".|");
1352    }
1353    if((analysis & BIT_FILTER) != 0)
1354    {
1355      buf.append("FLT|");
1356    }
1357    if((analysis & BIT_ROOT) != 0)
1358    {
1359      buf.append("R|");
1360    }
1361    return buf.toString();
1362  }
1363
1364  /** Set to true for diagnostics about walker creation */
1365  static final boolean DEBUG_PATTERN_CREATION = false;
1366
1367  /** Set to true for diagnostics about walker creation */
1368  static final boolean DEBUG_WALKER_CREATION = false;
1369
1370  /** Set to true for diagnostics about iterator creation */
1371  static final boolean DEBUG_ITERATOR_CREATION = false;
1372  
1373  public static boolean hasPredicate(int analysis)
1374  {
1375    return (0 != (analysis & BIT_PREDICATE));
1376  }
1377
1378  public static boolean isWild(int analysis)
1379  {
1380    return (0 != (analysis & BIT_NODETEST_ANY));
1381  }
1382
1383  public static boolean walksAncestors(int analysis)
1384  {
1385    return isSet(analysis, BIT_ANCESTOR | BIT_ANCESTOR_OR_SELF);
1386  }
1387  
1388  public static boolean walksAttributes(int analysis)
1389  {
1390    return (0 != (analysis & BIT_ATTRIBUTE));
1391  }
1392
1393  public static boolean walksNamespaces(int analysis)
1394  {
1395    return (0 != (analysis & BIT_NAMESPACE));
1396  }  
1397
1398  public static boolean walksChildren(int analysis)
1399  {
1400    return (0 != (analysis & BIT_CHILD));
1401  }
1402
1403  public static boolean walksDescendants(int analysis)
1404  {
1405    return isSet(analysis, BIT_DESCENDANT | BIT_DESCENDANT_OR_SELF);
1406  }
1407
1408  public static boolean walksSubtree(int analysis)
1409  {
1410    return isSet(analysis, BIT_DESCENDANT | BIT_DESCENDANT_OR_SELF | BIT_CHILD);
1411  }
1412  
1413  public static boolean walksSubtreeOnlyMaybeAbsolute(int analysis)
1414  {
1415    return walksSubtree(analysis)
1416           && !walksExtraNodes(analysis) 
1417           && !walksUp(analysis) 
1418           && !walksSideways(analysis) 
1419           ;
1420  }
1421  
1422  public static boolean walksSubtreeOnly(int analysis)
1423  {
1424    return walksSubtreeOnlyMaybeAbsolute(analysis) 
1425           && !isAbsolute(analysis) 
1426           ;
1427  }
1428
1429  public static boolean walksFilteredList(int analysis)
1430  {
1431    return isSet(analysis, BIT_FILTER);
1432  }
1433  
1434  public static boolean walksSubtreeOnlyFromRootOrContext(int analysis)
1435  {
1436    return walksSubtree(analysis)
1437           && !walksExtraNodes(analysis) 
1438           && !walksUp(analysis) 
1439           && !walksSideways(analysis) 
1440           && !isSet(analysis, BIT_FILTER) 
1441           ;
1442  }
1443
1444  public static boolean walksInDocOrder(int analysis)
1445  {
1446    return (walksSubtreeOnlyMaybeAbsolute(analysis)
1447           || walksExtraNodesOnly(analysis)
1448           || walksFollowingOnlyMaybeAbsolute(analysis)) 
1449           && !isSet(analysis, BIT_FILTER) 
1450           ;
1451  }
1452  
1453  public static boolean walksFollowingOnlyMaybeAbsolute(int analysis)
1454  {
1455    return isSet(analysis, BIT_SELF | BIT_FOLLOWING_SIBLING | BIT_FOLLOWING)
1456           && !walksSubtree(analysis) 
1457           && !walksUp(analysis) 
1458           && !walksSideways(analysis) 
1459           ;
1460  }
1461  
1462  public static boolean walksUp(int analysis)
1463  {
1464    return isSet(analysis, BIT_PARENT | BIT_ANCESTOR | BIT_ANCESTOR_OR_SELF);
1465  }
1466  
1467  public static boolean walksSideways(int analysis)
1468  {
1469    return isSet(analysis, BIT_FOLLOWING | BIT_FOLLOWING_SIBLING | 
1470                           BIT_PRECEDING | BIT_PRECEDING_SIBLING);
1471  }
1472  
1473  public static boolean walksExtraNodes(int analysis)
1474  {
1475    return isSet(analysis, BIT_NAMESPACE | BIT_ATTRIBUTE);
1476  }
1477
1478  public static boolean walksExtraNodesOnly(int analysis)
1479  {
1480    return walksExtraNodes(analysis)
1481           && !isSet(analysis, BIT_SELF) 
1482           && !walksSubtree(analysis) 
1483           && !walksUp(analysis) 
1484           && !walksSideways(analysis) 
1485           && !isAbsolute(analysis) 
1486           ;
1487  }
1488
1489  public static boolean isAbsolute(int analysis)
1490  {
1491    return isSet(analysis, BIT_ROOT | BIT_FILTER);
1492  }
1493  
1494  public static boolean walksChildrenOnly(int analysis)
1495  {
1496    return walksChildren(analysis)
1497           && !isSet(analysis, BIT_SELF)
1498           && !walksExtraNodes(analysis)
1499           && !walksDescendants(analysis) 
1500           && !walksUp(analysis) 
1501           && !walksSideways(analysis) 
1502           && (!isAbsolute(analysis) || isSet(analysis, BIT_ROOT))
1503           ;
1504  }
1505  
1506  public static boolean walksChildrenAndExtraAndSelfOnly(int analysis)
1507  {
1508    return walksChildren(analysis)
1509           && !walksDescendants(analysis) 
1510           && !walksUp(analysis) 
1511           && !walksSideways(analysis) 
1512           && (!isAbsolute(analysis) || isSet(analysis, BIT_ROOT))
1513           ;
1514  }
1515  
1516  public static boolean walksDescendantsAndExtraAndSelfOnly(int analysis)
1517  {
1518    return !walksChildren(analysis)
1519           && walksDescendants(analysis) 
1520           && !walksUp(analysis) 
1521           && !walksSideways(analysis) 
1522           && (!isAbsolute(analysis) || isSet(analysis, BIT_ROOT))
1523           ;
1524  }
1525  
1526  public static boolean walksSelfOnly(int analysis)
1527  {
1528    return isSet(analysis, BIT_SELF) 
1529           && !walksSubtree(analysis) 
1530           && !walksUp(analysis) 
1531           && !walksSideways(analysis) 
1532           && !isAbsolute(analysis) 
1533           ;
1534  }
1535
1536  
1537  public static boolean walksUpOnly(int analysis)
1538  {
1539    return !walksSubtree(analysis) 
1540           && walksUp(analysis) 
1541           && !walksSideways(analysis) 
1542           && !isAbsolute(analysis) 
1543           ;
1544  }
1545  
1546  public static boolean walksDownOnly(int analysis)
1547  {
1548    return walksSubtree(analysis) 
1549           && !walksUp(analysis) 
1550           && !walksSideways(analysis) 
1551           && !isAbsolute(analysis) 
1552           ;
1553  }
1554
1555  public static boolean walksDownExtraOnly(int analysis)
1556  {
1557    return walksSubtree(analysis) &&  walksExtraNodes(analysis)
1558           && !walksUp(analysis) 
1559           && !walksSideways(analysis) 
1560           && !isAbsolute(analysis) 
1561           ;
1562  }
1563  
1564  public static boolean canSkipSubtrees(int analysis)
1565  {
1566    return isSet(analysis, BIT_CHILD) | walksSideways(analysis);
1567  }
1568  
1569  public static boolean canCrissCross(int analysis)
1570  {
1571    // This could be done faster.  Coded for clarity.
1572    if(walksSelfOnly(analysis))
1573      return false;
1574    else if(walksDownOnly(analysis) && !canSkipSubtrees(analysis))
1575      return false;
1576    else if(walksChildrenAndExtraAndSelfOnly(analysis))
1577      return false;
1578    else if(walksDescendantsAndExtraAndSelfOnly(analysis))
1579      return false;
1580    else if(walksUpOnly(analysis))
1581      return false;
1582    else if(walksExtraNodesOnly(analysis))
1583      return false;
1584    else if(walksSubtree(analysis) 
1585           && (walksSideways(analysis) 
1586            || walksUp(analysis) 
1587            || canSkipSubtrees(analysis)))
1588      return true;
1589    else
1590      return false;
1591  }
1592  
1593  /**
1594   * Tell if the pattern can be 'walked' with the iteration steps in natural 
1595   * document order, without duplicates.
1596   *
1597   * @param analysis The general analysis of the pattern.
1598   *
1599   * @return true if the walk can be done in natural order.
1600   *
1601   * @throws javax.xml.transform.TransformerException
1602   */
1603  static public boolean isNaturalDocOrder(int analysis)
1604  {
1605    if(canCrissCross(analysis) || isSet(analysis, BIT_NAMESPACE) ||
1606       walksFilteredList(analysis))
1607      return false;
1608      
1609    if(walksInDocOrder(analysis))
1610      return true;
1611      
1612    return false;
1613  }
1614  
1615  /**
1616   * Tell if the pattern can be 'walked' with the iteration steps in natural 
1617   * document order, without duplicates.
1618   *
1619   * @param compiler non-null reference to compiler object that has processed
1620   *                 the XPath operations into an opcode map.
1621   * @param stepOpCodePos The opcode position for the step.
1622   * @param stepIndex The top-level step index withing the iterator.
1623   * @param analysis The general analysis of the pattern.
1624   *
1625   * @return true if the walk can be done in natural order.
1626   *
1627   * @throws javax.xml.transform.TransformerException
1628   */
1629  private static boolean isNaturalDocOrder(
1630          Compiler   compiler, int stepOpCodePos, int stepIndex, int analysis)
1631            throws javax.xml.transform.TransformerException  
1632  {
1633    if(canCrissCross(analysis))
1634      return false;
1635      
1636    // Namespaces can present some problems, so just punt if we're looking for 
1637    // these.
1638    if(isSet(analysis, BIT_NAMESPACE))
1639      return false;
1640      
1641    // The following, preceding, following-sibling, and preceding sibling can 
1642    // be found in doc order if we get to this point, but if they occur 
1643    // together, they produce 
1644    // duplicates, so it's better for us to eliminate this case so we don't 
1645    // have to check for duplicates during runtime if we're using a 
1646    // WalkingIterator.
1647    if(isSet(analysis, BIT_FOLLOWING | BIT_FOLLOWING_SIBLING) && 
1648       isSet(analysis, BIT_PRECEDING | BIT_PRECEDING_SIBLING))
1649      return  false;
1650      
1651    // OK, now we have to check for select="@*/axis::*" patterns, which 
1652    // can also cause duplicates to happen.  But select="axis*/@::*" patterns 
1653    // are OK, as are select="@foo/axis::*" patterns.
1654    // Unfortunately, we can't do this just via the analysis bits.
1655    
1656    int stepType;
1657    int stepCount = 0;
1658    boolean foundWildAttribute = false;
1659    
1660    // Steps that can traverse anything other than down a 
1661    // subtree or that can produce duplicates when used in 
1662    // combonation are counted with this variable.
1663    int potentialDuplicateMakingStepCount = 0;
1664    
1665    while (OpCodes.ENDOP != (stepType = compiler.getOp(stepOpCodePos)))
1666    {        
1667      stepCount++;
1668        
1669      switch (stepType)
1670      {
1671      case OpCodes.FROM_ATTRIBUTES :
1672      case OpCodes.MATCH_ATTRIBUTE :
1673        if(foundWildAttribute) // Maybe not needed, but be safe.
1674          return false;
1675        
1676        // This doesn't seem to work as a test for wild card.  Hmph.
1677        // int nodeTestType = compiler.getStepTestType(stepOpCodePos);  
1678        
1679        String   localName = compiler.getStepLocalName(stepOpCodePos);
1680        // System.err.println("localName: "+localName);
1681        if(localName.equals("*"))
1682        {
1683          foundWildAttribute = true;
1684        }
1685        break;
1686      case OpCodes.FROM_FOLLOWING :
1687      case OpCodes.FROM_FOLLOWING_SIBLINGS :
1688      case OpCodes.FROM_PRECEDING :
1689      case OpCodes.FROM_PRECEDING_SIBLINGS :
1690      case OpCodes.FROM_PARENT :
1691      case OpCodes.OP_VARIABLE :
1692      case OpCodes.OP_EXTFUNCTION :
1693      case OpCodes.OP_FUNCTION :
1694      case OpCodes.OP_GROUP :
1695      case OpCodes.FROM_NAMESPACE :
1696      case OpCodes.FROM_ANCESTORS :
1697      case OpCodes.FROM_ANCESTORS_OR_SELF :      
1698      case OpCodes.MATCH_ANY_ANCESTOR :
1699      case OpCodes.MATCH_IMMEDIATE_ANCESTOR :
1700      case OpCodes.FROM_DESCENDANTS_OR_SELF :
1701      case OpCodes.FROM_DESCENDANTS :
1702        if(potentialDuplicateMakingStepCount > 0)
1703            return false;
1704        potentialDuplicateMakingStepCount++;
1705      case OpCodes.FROM_ROOT :
1706      case OpCodes.FROM_CHILDREN :
1707      case OpCodes.FROM_SELF :
1708        if(foundWildAttribute)
1709          return false;
1710        break;
1711      default :
1712        throw new RuntimeException  (XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NULL_ERROR_HANDLER, new Object  []{Integer.toString(stepType)})); //"Programmer's assertion: unknown opcode: "
1713                                  // + stepType);
1714      }
1715
1716      int nextStepOpCodePos = compiler.getNextStepPos(stepOpCodePos);
1717
1718      if (nextStepOpCodePos < 0)
1719        break;
1720              
1721      stepOpCodePos = nextStepOpCodePos;
1722    }
1723
1724    return true;
1725  }
1726  
1727  public static boolean isOneStep(int analysis)
1728  {
1729    return (analysis & BITS_COUNT) == 0x00000001;
1730  }
1731
1732  public static int getStepCount(int analysis)
1733  {
1734    return (analysis & BITS_COUNT);
1735  }
1736
1737  /**
1738   * First 8 bits are the number of top-level location steps.  Hopefully
1739   *  there will never be more that 255 location steps!!!
1740   */
1741  public static final int BITS_COUNT = 0x000000FF;
1742
1743  /** 4 bits are reserved for future use. */
1744  public static final int BITS_RESERVED = 0x00000F00;
1745
1746  /** Bit is on if the expression contains a top-level predicate. */
1747  public static final int BIT_PREDICATE = (0x00001000);
1748
1749  /** Bit is on if any of the walkers contain an ancestor step. */
1750  public static final int BIT_ANCESTOR = (0x00001000 << 1);
1751
1752  /** Bit is on if any of the walkers contain an ancestor-or-self step. */
1753  public static final int BIT_ANCESTOR_OR_SELF = (0x00001000 << 2);
1754
1755  /** Bit is on if any of the walkers contain an attribute step. */
1756  public static final int BIT_ATTRIBUTE = (0x00001000 << 3);
1757
1758  /** Bit is on if any of the walkers contain a child step. */
1759  public static final int BIT_CHILD = (0x00001000 << 4);
1760
1761  /** Bit is on if any of the walkers contain a descendant step. */
1762  public static final int BIT_DESCENDANT = (0x00001000 << 5);
1763
1764  /** Bit is on if any of the walkers contain a descendant-or-self step. */
1765  public static final int BIT_DESCENDANT_OR_SELF = (0x00001000 << 6);
1766
1767  /** Bit is on if any of the walkers contain a following step. */
1768  public static final int BIT_FOLLOWING = (0x00001000 << 7);
1769
1770  /** Bit is on if any of the walkers contain a following-sibiling step. */
1771  public static final int BIT_FOLLOWING_SIBLING = (0x00001000 << 8);
1772
1773  /** Bit is on if any of the walkers contain a namespace step. */
1774  public static final int BIT_NAMESPACE = (0x00001000 << 9);
1775
1776  /** Bit is on if any of the walkers contain a parent step. */
1777  public static final int BIT_PARENT = (0x00001000 << 10);
1778
1779  /** Bit is on if any of the walkers contain a preceding step. */
1780  public static final int BIT_PRECEDING = (0x00001000 << 11);
1781
1782  /** Bit is on if any of the walkers contain a preceding-sibling step. */
1783  public static final int BIT_PRECEDING_SIBLING = (0x00001000 << 12);
1784
1785  /** Bit is on if any of the walkers contain a self step. */
1786  public static final int BIT_SELF = (0x00001000 << 13);
1787
1788  /**
1789   * Bit is on if any of the walkers contain a filter (i.e. id(), extension
1790   *  function, etc.) step.
1791   */
1792  public static final int BIT_FILTER = (0x00001000 << 14);
1793
1794  /** Bit is on if any of the walkers contain a root step. */
1795  public static final int BIT_ROOT = (0x00001000 << 15);
1796
1797  /**
1798   * If any of these bits are on, the expression may likely traverse outside
1799   *  the given subtree.
1800   */
1801  public static final int BITMASK_TRAVERSES_OUTSIDE_SUBTREE = (BIT_NAMESPACE  // ??
1802                                                                | BIT_PRECEDING_SIBLING
1803                                                                | BIT_PRECEDING
1804                                                                | BIT_FOLLOWING_SIBLING
1805                                                                | BIT_FOLLOWING
1806                                                                | BIT_PARENT  // except parent of attrs.
1807                                                                | BIT_ANCESTOR_OR_SELF
1808                                                                | BIT_ANCESTOR
1809                                                                | BIT_FILTER
1810                                                                | BIT_ROOT);
1811
1812  /**
1813   * Bit is on if any of the walkers can go backwards in document
1814   *  order from the context node.
1815   */
1816  public static final int BIT_BACKWARDS_SELF = (0x00001000 << 16);
1817
1818  /** Found "//foo" pattern */
1819  public static final int BIT_ANY_DESCENDANT_FROM_ROOT = (0x00001000 << 17);
1820
1821  /**
1822   * Bit is on if any of the walkers contain an node() test.  This is
1823   *  really only useful if the count is 1.
1824   */
1825  public static final int BIT_NODETEST_ANY = (0x00001000 << 18);
1826
1827  // can't go higher than 18!
1828
1829  /** Bit is on if the expression is a match pattern. */
1830  public static final int BIT_MATCH_PATTERN = (0x00001000 << 19);
1831}
1832
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags