1 /*
   2  * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.

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