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 } 1826
