libcore/luni/src/main/java/org/apache/xpath/axes/WalkerFactory.java

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