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 */ loadOneWalker( WalkingIterator lpi, Compiler compiler, int stepOpCodePos)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 */ loadWalkers( WalkingIterator lpi, Compiler compiler, int stepOpCodePos, int stepIndex)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 isSet(int analysis, int bits)134 public static boolean isSet(int analysis, int bits) 135 { 136 return (0 != (analysis & bits)); 137 } 138 diagnoseIterator(String name, int analysis, Compiler compiler)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 */ newDTMIterator( Compiler compiler, int opPos, boolean isTopLevel)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 */ getAxisFromStep( Compiler compiler, int stepOpCodePos)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 */ getAnalysisBitFromAxes(int axis)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 functionProximateOrContainsProximate(Compiler compiler, int opPos)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 isProximateInnerExpr(Compiler compiler, int opPos)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 */ mightBeProximate(Compiler compiler, int opPos, int stepType)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 */ isOptimizableForDescendantIterator( Compiler compiler, int stepOpCodePos, int stepIndex)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 */ analyze( Compiler compiler, int stepOpCodePos, int stepIndex)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 */ isDownwardAxisOfMany(int axis)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 */ loadSteps( MatchPatternIterator mpi, Compiler compiler, int stepOpCodePos, int stepIndex)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 */ createDefaultStepPattern( Compiler compiler, int opPos, MatchPatternIterator mpi, int analysis, StepPattern tail, StepPattern head)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 */ analyzePredicate(Compiler compiler, int opPos, int stepType)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 */ createDefaultWalker(Compiler compiler, int opPos, WalkingIterator lpi, int analysis)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 getAnalysisString(int analysis)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 hasPredicate(int analysis)1367 public static boolean hasPredicate(int analysis) 1368 { 1369 return (0 != (analysis & BIT_PREDICATE)); 1370 } 1371 isWild(int analysis)1372 public static boolean isWild(int analysis) 1373 { 1374 return (0 != (analysis & BIT_NODETEST_ANY)); 1375 } 1376 walksAncestors(int analysis)1377 public static boolean walksAncestors(int analysis) 1378 { 1379 return isSet(analysis, BIT_ANCESTOR | BIT_ANCESTOR_OR_SELF); 1380 } 1381 walksAttributes(int analysis)1382 public static boolean walksAttributes(int analysis) 1383 { 1384 return (0 != (analysis & BIT_ATTRIBUTE)); 1385 } 1386 walksNamespaces(int analysis)1387 public static boolean walksNamespaces(int analysis) 1388 { 1389 return (0 != (analysis & BIT_NAMESPACE)); 1390 } 1391 walksChildren(int analysis)1392 public static boolean walksChildren(int analysis) 1393 { 1394 return (0 != (analysis & BIT_CHILD)); 1395 } 1396 walksDescendants(int analysis)1397 public static boolean walksDescendants(int analysis) 1398 { 1399 return isSet(analysis, BIT_DESCENDANT | BIT_DESCENDANT_OR_SELF); 1400 } 1401 walksSubtree(int analysis)1402 public static boolean walksSubtree(int analysis) 1403 { 1404 return isSet(analysis, BIT_DESCENDANT | BIT_DESCENDANT_OR_SELF | BIT_CHILD); 1405 } 1406 walksSubtreeOnlyMaybeAbsolute(int analysis)1407 public static boolean walksSubtreeOnlyMaybeAbsolute(int analysis) 1408 { 1409 return walksSubtree(analysis) 1410 && !walksExtraNodes(analysis) 1411 && !walksUp(analysis) 1412 && !walksSideways(analysis) 1413 ; 1414 } 1415 walksSubtreeOnly(int analysis)1416 public static boolean walksSubtreeOnly(int analysis) 1417 { 1418 return walksSubtreeOnlyMaybeAbsolute(analysis) 1419 && !isAbsolute(analysis) 1420 ; 1421 } 1422 walksFilteredList(int analysis)1423 public static boolean walksFilteredList(int analysis) 1424 { 1425 return isSet(analysis, BIT_FILTER); 1426 } 1427 walksSubtreeOnlyFromRootOrContext(int analysis)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 walksInDocOrder(int analysis)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 walksFollowingOnlyMaybeAbsolute(int analysis)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 walksUp(int analysis)1456 public static boolean walksUp(int analysis) 1457 { 1458 return isSet(analysis, BIT_PARENT | BIT_ANCESTOR | BIT_ANCESTOR_OR_SELF); 1459 } 1460 walksSideways(int analysis)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 walksExtraNodes(int analysis)1467 public static boolean walksExtraNodes(int analysis) 1468 { 1469 return isSet(analysis, BIT_NAMESPACE | BIT_ATTRIBUTE); 1470 } 1471 walksExtraNodesOnly(int analysis)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 isAbsolute(int analysis)1483 public static boolean isAbsolute(int analysis) 1484 { 1485 return isSet(analysis, BIT_ROOT | BIT_FILTER); 1486 } 1487 walksChildrenOnly(int analysis)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 walksChildrenAndExtraAndSelfOnly(int analysis)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 walksDescendantsAndExtraAndSelfOnly(int analysis)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 walksSelfOnly(int analysis)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 walksUpOnly(int analysis)1531 public static boolean walksUpOnly(int analysis) 1532 { 1533 return !walksSubtree(analysis) 1534 && walksUp(analysis) 1535 && !walksSideways(analysis) 1536 && !isAbsolute(analysis) 1537 ; 1538 } 1539 walksDownOnly(int analysis)1540 public static boolean walksDownOnly(int analysis) 1541 { 1542 return walksSubtree(analysis) 1543 && !walksUp(analysis) 1544 && !walksSideways(analysis) 1545 && !isAbsolute(analysis) 1546 ; 1547 } 1548 walksDownExtraOnly(int analysis)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 canSkipSubtrees(int analysis)1558 public static boolean canSkipSubtrees(int analysis) 1559 { 1560 return isSet(analysis, BIT_CHILD) | walksSideways(analysis); 1561 } 1562 canCrissCross(int analysis)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 */ isNaturalDocOrder(int analysis)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 */ isNaturalDocOrder( Compiler compiler, int stepOpCodePos, int stepIndex, int analysis)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 isOneStep(int analysis)1721 public static boolean isOneStep(int analysis) 1722 { 1723 return (analysis & BITS_COUNT) == 0x00000001; 1724 } 1725 getStepCount(int analysis)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