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