001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one
003     * or more contributor license agreements. See the NOTICE file
004     * distributed with this work for additional information
005     * regarding copyright ownership. The ASF licenses this file
006     * to you under the Apache License, Version 2.0 (the  "License");
007     * you may not use this file except in compliance with the License.
008     * You may obtain a copy of the License at
009     *
010     *     http://www.apache.org/licenses/LICENSE-2.0
011     *
012     * Unless required by applicable law or agreed to in writing, software
013     * distributed under the License is distributed on an "AS IS" BASIS,
014     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015     * See the License for the specific language governing permissions and
016     * limitations under the License.
017     */
018    /*
019     * $Id: WalkerFactory.java 469314 2006-10-30 23:31:59Z minchau $
020     */
021    package org.apache.xpath.axes;
022    
023    import org.apache.xalan.res.XSLMessages;
024    import org.apache.xml.dtm.Axis;
025    import org.apache.xml.dtm.DTMFilter;
026    import org.apache.xml.dtm.DTMIterator;
027    import org.apache.xpath.Expression;
028    import org.apache.xpath.compiler.Compiler;
029    import org.apache.xpath.compiler.FunctionTable;
030    import org.apache.xpath.compiler.OpCodes;
031    import org.apache.xpath.compiler.OpMap;
032    import org.apache.xpath.objects.XNumber;
033    import org.apache.xpath.patterns.ContextMatchStepPattern;
034    import org.apache.xpath.patterns.FunctionPattern;
035    import org.apache.xpath.patterns.NodeTest;
036    import org.apache.xpath.patterns.StepPattern;
037    import org.apache.xpath.res.XPATHErrorResources;
038    
039    /**
040     * This class is both a factory for XPath location path expressions,
041     * which are built from the opcode map output, and an analysis engine
042     * for the location path expressions in order to provide optimization hints.
043     */
044    public class WalkerFactory
045    {
046    
047      /**
048       * This method is for building an array of possible levels
049       * where the target element(s) could be found for a match.
050       * @param lpi The owning location path iterator.
051       * @param compiler non-null reference to compiler object that has processed
052       *                 the XPath operations into an opcode map.
053       * @param stepOpCodePos The opcode position for the step.
054       *
055       * @return non-null AxesWalker derivative.
056       *
057       * @throws javax.xml.transform.TransformerException
058       * @xsl.usage advanced
059       */
060      static AxesWalker loadOneWalker(
061              WalkingIterator lpi, Compiler compiler, int stepOpCodePos)
062                throws javax.xml.transform.TransformerException
063      {
064    
065        AxesWalker firstWalker = null;
066        int stepType = compiler.getOp(stepOpCodePos);
067    
068        if (stepType != OpCodes.ENDOP)
069        {
070    
071          // m_axesWalkers = new AxesWalker[1];
072          // As we unwind from the recursion, create the iterators.
073          firstWalker = createDefaultWalker(compiler, stepType, lpi, 0);
074    
075          firstWalker.init(compiler, stepOpCodePos, stepType);
076        }
077    
078        return firstWalker;
079      }
080    
081      /**
082       * This method is for building an array of possible levels
083       * where the target element(s) could be found for a match.
084       * @param lpi The owning location path iterator object.
085       * @param compiler non-null reference to compiler object that has processed
086       *                 the XPath operations into an opcode map.
087       * @param stepOpCodePos The opcode position for the step.
088       * @param stepIndex The top-level step index withing the iterator.
089       *
090       * @return non-null AxesWalker derivative.
091       *
092       * @throws javax.xml.transform.TransformerException
093       * @xsl.usage advanced
094       */
095      static AxesWalker loadWalkers(
096              WalkingIterator lpi, Compiler compiler, int stepOpCodePos, int stepIndex)
097                throws javax.xml.transform.TransformerException
098      {
099    
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      
134      public static boolean isSet(int analysis, int bits)
135      {
136        return (0 != (analysis & bits));
137      }
138      
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       */
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       */
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         */
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      
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      
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       */
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       */
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       */
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       */
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       */
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       */
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       */
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       */
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      
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      
1367      public static boolean hasPredicate(int analysis)
1368      {
1369        return (0 != (analysis & BIT_PREDICATE));
1370      }
1371    
1372      public static boolean isWild(int analysis)
1373      {
1374        return (0 != (analysis & BIT_NODETEST_ANY));
1375      }
1376    
1377      public static boolean walksAncestors(int analysis)
1378      {
1379        return isSet(analysis, BIT_ANCESTOR | BIT_ANCESTOR_OR_SELF);
1380      }
1381      
1382      public static boolean walksAttributes(int analysis)
1383      {
1384        return (0 != (analysis & BIT_ATTRIBUTE));
1385      }
1386    
1387      public static boolean walksNamespaces(int analysis)
1388      {
1389        return (0 != (analysis & BIT_NAMESPACE));
1390      }  
1391    
1392      public static boolean walksChildren(int analysis)
1393      {
1394        return (0 != (analysis & BIT_CHILD));
1395      }
1396    
1397      public static boolean walksDescendants(int analysis)
1398      {
1399        return isSet(analysis, BIT_DESCENDANT | BIT_DESCENDANT_OR_SELF);
1400      }
1401    
1402      public static boolean walksSubtree(int analysis)
1403      {
1404        return isSet(analysis, BIT_DESCENDANT | BIT_DESCENDANT_OR_SELF | BIT_CHILD);
1405      }
1406      
1407      public static boolean walksSubtreeOnlyMaybeAbsolute(int analysis)
1408      {
1409        return walksSubtree(analysis)
1410               && !walksExtraNodes(analysis) 
1411               && !walksUp(analysis) 
1412               && !walksSideways(analysis) 
1413               ;
1414      }
1415      
1416      public static boolean walksSubtreeOnly(int analysis)
1417      {
1418        return walksSubtreeOnlyMaybeAbsolute(analysis) 
1419               && !isAbsolute(analysis) 
1420               ;
1421      }
1422    
1423      public static boolean walksFilteredList(int analysis)
1424      {
1425        return isSet(analysis, BIT_FILTER);
1426      }
1427      
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    
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      
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      
1456      public static boolean walksUp(int analysis)
1457      {
1458        return isSet(analysis, BIT_PARENT | BIT_ANCESTOR | BIT_ANCESTOR_OR_SELF);
1459      }
1460      
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      
1467      public static boolean walksExtraNodes(int analysis)
1468      {
1469        return isSet(analysis, BIT_NAMESPACE | BIT_ATTRIBUTE);
1470      }
1471    
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    
1483      public static boolean isAbsolute(int analysis)
1484      {
1485        return isSet(analysis, BIT_ROOT | BIT_FILTER);
1486      }
1487      
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      
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      
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      
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      
1531      public static boolean walksUpOnly(int analysis)
1532      {
1533        return !walksSubtree(analysis) 
1534               && walksUp(analysis) 
1535               && !walksSideways(analysis) 
1536               && !isAbsolute(analysis) 
1537               ;
1538      }
1539      
1540      public static boolean walksDownOnly(int analysis)
1541      {
1542        return walksSubtree(analysis) 
1543               && !walksUp(analysis) 
1544               && !walksSideways(analysis) 
1545               && !isAbsolute(analysis) 
1546               ;
1547      }
1548    
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      
1558      public static boolean canSkipSubtrees(int analysis)
1559      {
1560        return isSet(analysis, BIT_CHILD) | walksSideways(analysis);
1561      }
1562      
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       */
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       */
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      
1721      public static boolean isOneStep(int analysis)
1722      {
1723        return (analysis & BITS_COUNT) == 0x00000001;
1724      }
1725    
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    }