1 /*
   2  * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
   3  * @LastModified: Oct 2017
   4  */
   5 /*
   6  * Licensed to the Apache Software Foundation (ASF) under one or more
   7  * contributor license agreements.  See the NOTICE file distributed with
   8  * this work for additional information regarding copyright ownership.
   9  * The ASF licenses this file to You under the Apache License, Version 2.0
  10  * (the "License"); you may not use this file except in compliance with
  11  * the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  * Unless required by applicable law or agreed to in writing, software
  16  * distributed under the License is distributed on an "AS IS" BASIS,
  17  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  18  * See the License for the specific language governing permissions and
  19  * limitations under the License.
  20  */
  21 
  22 package com.sun.org.apache.xpath.internal.axes;
  23 
  24 import com.sun.org.apache.xalan.internal.res.XSLMessages;
  25 import com.sun.org.apache.xml.internal.dtm.Axis;
  26 import com.sun.org.apache.xml.internal.dtm.DTMFilter;
  27 import com.sun.org.apache.xml.internal.dtm.DTMIterator;
  28 import com.sun.org.apache.xpath.internal.Expression;
  29 import com.sun.org.apache.xpath.internal.compiler.Compiler;
  30 import com.sun.org.apache.xpath.internal.compiler.FunctionTable;
  31 import com.sun.org.apache.xpath.internal.compiler.OpCodes;
  32 import com.sun.org.apache.xpath.internal.compiler.OpMap;
  33 import com.sun.org.apache.xpath.internal.objects.XNumber;
  34 import com.sun.org.apache.xpath.internal.patterns.ContextMatchStepPattern;
  35 import com.sun.org.apache.xpath.internal.patterns.FunctionPattern;
  36 import com.sun.org.apache.xpath.internal.patterns.NodeTest;
  37 import com.sun.org.apache.xpath.internal.patterns.StepPattern;
  38 import com.sun.org.apache.xpath.internal.res.XPATHErrorResources;
  39 
  40 /**
  41  * This class is both a factory for XPath location path expressions,
  42  * which are built from the opcode map output, and an analysis engine
  43  * for the location path expressions in order to provide optimization hints.


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