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