001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the "License");
007 * you may not use this file except in compliance with the License.
008 * You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018 /*
019 * $Id: WalkerFactory.java 469314 2006-10-30 23:31:59Z minchau $
020 */
021 package org.apache.xpath.axes;
022
023 import org.apache.xalan.res.XSLMessages;
024 import org.apache.xml.dtm.Axis;
025 import org.apache.xml.dtm.DTMFilter;
026 import org.apache.xml.dtm.DTMIterator;
027 import org.apache.xpath.Expression;
028 import org.apache.xpath.compiler.Compiler;
029 import org.apache.xpath.compiler.FunctionTable;
030 import org.apache.xpath.compiler.OpCodes;
031 import org.apache.xpath.compiler.OpMap;
032 import org.apache.xpath.objects.XNumber;
033 import org.apache.xpath.patterns.ContextMatchStepPattern;
034 import org.apache.xpath.patterns.FunctionPattern;
035 import org.apache.xpath.patterns.NodeTest;
036 import org.apache.xpath.patterns.StepPattern;
037 import org.apache.xpath.res.XPATHErrorResources;
038
039 /**
040 * This class is both a factory for XPath location path expressions,
041 * which are built from the opcode map output, and an analysis engine
042 * for the location path expressions in order to provide optimization hints.
043 */
044 public class WalkerFactory
045 {
046
047 /**
048 * This method is for building an array of possible levels
049 * where the target element(s) could be found for a match.
050 * @param lpi The owning location path iterator.
051 * @param compiler non-null reference to compiler object that has processed
052 * the XPath operations into an opcode map.
053 * @param stepOpCodePos The opcode position for the step.
054 *
055 * @return non-null AxesWalker derivative.
056 *
057 * @throws javax.xml.transform.TransformerException
058 * @xsl.usage advanced
059 */
060 static AxesWalker loadOneWalker(
061 WalkingIterator lpi, Compiler compiler, int stepOpCodePos)
062 throws javax.xml.transform.TransformerException
063 {
064
065 AxesWalker firstWalker = null;
066 int stepType = compiler.getOp(stepOpCodePos);
067
068 if (stepType != OpCodes.ENDOP)
069 {
070
071 // m_axesWalkers = new AxesWalker[1];
072 // As we unwind from the recursion, create the iterators.
073 firstWalker = createDefaultWalker(compiler, stepType, lpi, 0);
074
075 firstWalker.init(compiler, stepOpCodePos, stepType);
076 }
077
078 return firstWalker;
079 }
080
081 /**
082 * This method is for building an array of possible levels
083 * where the target element(s) could be found for a match.
084 * @param lpi The owning location path iterator object.
085 * @param compiler non-null reference to compiler object that has processed
086 * the XPath operations into an opcode map.
087 * @param stepOpCodePos The opcode position for the step.
088 * @param stepIndex The top-level step index withing the iterator.
089 *
090 * @return non-null AxesWalker derivative.
091 *
092 * @throws javax.xml.transform.TransformerException
093 * @xsl.usage advanced
094 */
095 static AxesWalker loadWalkers(
096 WalkingIterator lpi, Compiler compiler, int stepOpCodePos, int stepIndex)
097 throws javax.xml.transform.TransformerException
098 {
099
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 }