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