1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package org.apache.commons.jxpath.ri.axes;
17
18 import java.util.ArrayList;
19 import java.util.Collections;
20 import java.util.List;
21
22 import org.apache.commons.jxpath.JXPathException;
23 import org.apache.commons.jxpath.ri.Compiler;
24 import org.apache.commons.jxpath.ri.EvalContext;
25 import org.apache.commons.jxpath.ri.InfoSetUtil;
26 import org.apache.commons.jxpath.ri.QName;
27 import org.apache.commons.jxpath.ri.compiler.Expression;
28 import org.apache.commons.jxpath.ri.compiler.NameAttributeTest;
29 import org.apache.commons.jxpath.ri.compiler.NodeNameTest;
30 import org.apache.commons.jxpath.ri.compiler.NodeTest;
31 import org.apache.commons.jxpath.ri.compiler.Step;
32 import org.apache.commons.jxpath.ri.model.NodeIterator;
33 import org.apache.commons.jxpath.ri.model.NodePointer;
34 import org.apache.commons.jxpath.ri.model.beans.LangAttributePointer;
35 import org.apache.commons.jxpath.ri.model.beans.NullElementPointer;
36 import org.apache.commons.jxpath.ri.model.beans.NullPropertyPointer;
37 import org.apache.commons.jxpath.ri.model.beans.PropertyOwnerPointer;
38 import org.apache.commons.jxpath.ri.model.beans.PropertyPointer;
39
40 /***
41 * An evaluation mechanism for simple XPaths, which
42 * is much faster than the usual process. It is only used for
43 * xpaths which have no context-dependent parts, consist entirely of
44 * <code>child::name</code> and <code>self::node()</code> steps with
45 * predicates that either integer or have the form <code>[@name = ...]</code>.
46 *
47 * @author Dmitri Plotnikov
48 * @version $Revision: 1.10 $ $Date: 2002/04/24 04:05:40 $
49 */
50 public class SimplePathInterpreter {
51
52
53
54
55
56
57
58 private static final QName QNAME_NAME = new QName(null, "name");
59 private static final int PERFECT_MATCH = 1000;
60
61
62
63
64
65
66 /***
67 * Interpret a simple path that starts with the given root and
68 * follows the given steps. All steps must have the axis "child::"
69 * and a name test. They can also optionally have predicates
70 * of type [@name=expression] or simply [expression] interpreted
71 * as an index.
72 */
73 public static NodePointer interpretSimpleLocationPath(
74 EvalContext context, NodePointer root, Step steps[])
75 {
76
77 NodePointer pointer = doStep(context, root, steps, 0);
78
79 return pointer;
80 }
81
82 /***
83 * Interpret the steps of a simple expression path that
84 * starts with the given root, which is the result of evaluation
85 * of the root expression of the expression path, applies the
86 * given predicates to it and then follows the given steps.
87 * All steps must have the axis "child::" or "attribute::"
88 * and a name test. They can also optionally have predicates
89 * of type [@name=...] or simply [...] interpreted as an index.
90 */
91 public static NodePointer interpretSimpleExpressionPath(
92 EvalContext context, NodePointer root,
93 Expression predicates[], Step[] steps)
94 {
95
96
97 NodePointer pointer =
98 doPredicate(context, root, steps, -1, predicates, 0);
99
100 return pointer;
101 }
102
103 /***
104 * Recursive evaluation of a path. The general plan is:
105 * Look at the current step,
106 * find nodes that match it,
107 * iterate over those nodes and
108 * for each of them call doStep again for subsequent steps.
109 */
110 private static NodePointer doStep(
111 EvalContext context, NodePointer parent,
112 Step steps[], int currentStep)
113 {
114 if (parent == null) {
115 return null;
116 }
117
118 if (currentStep == steps.length) {
119
120 return parent;
121 }
122
123
124 parent = valuePointer(parent);
125
126 Step step = steps[currentStep];
127 Expression predicates[] = step.getPredicates();
128
129
130
131
132
133
134
135
136
137
138
139
140 if (parent instanceof PropertyOwnerPointer) {
141 if (predicates == null || predicates.length == 0) {
142 return doStepNoPredicatesPropertyOwner(
143 context,
144 (PropertyOwnerPointer) parent,
145 steps,
146 currentStep);
147 }
148 else {
149 return doStepPredicatesPropertyOwner(
150 context,
151 (PropertyOwnerPointer) parent,
152 steps,
153 currentStep);
154 }
155 }
156 else {
157 if (predicates == null || predicates.length == 0) {
158 return doStepNoPredicatesStandard(
159 context,
160 parent,
161 steps,
162 currentStep);
163 }
164 else {
165 return doStepPredicatesStandard(
166 context,
167 parent,
168 steps,
169 currentStep);
170 }
171 }
172 }
173
174 /***
175 * We have a step that starts with a property owner (bean, map, etc) and has
176 * no predicates. The name test of the step may map to a scalar property
177 * or to a collection. If it is a collection, we should apply the tail of
178 * the path to each element until we find a match. If we don't find
179 * a perfect match, we should return the "best quality" pointer, which
180 * has the longest chain of steps mapping to existing nodes and the shortes
181 * tail of Null* pointers.
182 */
183 private static NodePointer doStepNoPredicatesPropertyOwner(
184 EvalContext context, PropertyOwnerPointer parentPointer,
185 Step[] steps, int currentStep)
186 {
187 Step step = steps[currentStep];
188 NodePointer childPointer =
189 createChildPointerForStep(parentPointer, step);
190
191 if (!childPointer.isActual()) {
192
193 return createNullPointer(
194 context,
195 parentPointer,
196 steps,
197 currentStep);
198 }
199 else if (currentStep == steps.length - 1) {
200
201 return childPointer;
202 }
203 else if (childPointer.isCollection()) {
204
205
206
207 int bestQuality = 0;
208 childPointer = (NodePointer) childPointer.clone();
209 NodePointer bestMatch = null;
210 int count = childPointer.getLength();
211 for (int i = 0; i < count; i++) {
212 childPointer.setIndex(i);
213 NodePointer pointer =
214 doStep(context, childPointer, steps, currentStep + 1);
215 int quality = computeQuality(pointer);
216 if (quality == PERFECT_MATCH) {
217 return pointer;
218 }
219 else if (quality > bestQuality) {
220 bestQuality = quality;
221 bestMatch = (NodePointer) pointer.clone();
222 }
223 }
224 if (bestMatch != null) {
225 return bestMatch;
226 }
227
228 return createNullPointer(context, childPointer, steps, currentStep);
229 }
230 else {
231
232 return doStep(context, childPointer, steps, currentStep + 1);
233 }
234 }
235
236 /***
237 * A path that starts with a standard InfoSet node (e.g. DOM Node) and
238 * has no predicates. Get a child iterator and apply the tail of
239 * the path to each element until we find a match. If we don't find
240 * a perfect match, we should return the "best quality" pointer, which
241 * has the longest chain of steps mapping to existing nodes and the shortes
242 * tail of Null* pointers.
243 */
244 private static NodePointer doStepNoPredicatesStandard(
245 EvalContext context, NodePointer parentPointer,
246 Step[] steps, int currentStep)
247 {
248 Step step = steps[currentStep];
249
250 if (step.getAxis() == Compiler.AXIS_SELF) {
251 return doStep(context, parentPointer, steps, currentStep + 1);
252 }
253
254 int bestQuality = 0;
255 NodePointer bestMatch = null;
256 NodeIterator it = getNodeIterator(context, parentPointer, step);
257 if (it != null) {
258 for (int i = 1; it.setPosition(i); i++) {
259 NodePointer childPointer = it.getNodePointer();
260 if (steps.length == currentStep + 1) {
261
262 return childPointer;
263 }
264 NodePointer pointer = doStep(
265 context, childPointer, steps, currentStep + 1);
266 int quality = computeQuality(pointer);
267 if (quality == PERFECT_MATCH) {
268 return pointer;
269 }
270 else if (quality > bestQuality) {
271 bestQuality = quality;
272 bestMatch = (NodePointer) pointer.clone();
273 }
274 }
275 }
276
277 if (bestMatch != null) {
278 return bestMatch;
279 }
280
281 return createNullPointer(
282 context, parentPointer, steps, currentStep);
283 }
284
285 /***
286 * A path that starts with a property owner. The method evaluates
287 * the first predicate in a special way and then forwards to
288 * a general predicate processing method.
289 */
290 private static NodePointer doStepPredicatesPropertyOwner(
291 EvalContext context, PropertyOwnerPointer parentPointer,
292 Step[] steps, int currentStep)
293 {
294 Step step = steps[currentStep];
295 Expression predicates[] = step.getPredicates();
296
297 NodePointer childPointer =
298 createChildPointerForStep(parentPointer, step);
299 if (!childPointer.isActual()) {
300
301 return createNullPointer(
302 context,
303 parentPointer,
304 steps,
305 currentStep);
306 }
307
308
309 return doPredicate(
310 context,
311 childPointer,
312 steps,
313 currentStep,
314 predicates,
315 0);
316 }
317
318 private static NodePointer createChildPointerForStep(
319 PropertyOwnerPointer parentPointer, Step step)
320 {
321 int axis = step.getAxis();
322 if (axis == Compiler.AXIS_CHILD || axis == Compiler.AXIS_ATTRIBUTE) {
323 NodePointer childPointer;
324 QName name = ((NodeNameTest) step.getNodeTest()).getNodeName();
325 if (axis == Compiler.AXIS_ATTRIBUTE && isLangAttribute(name)) {
326 childPointer = new LangAttributePointer(parentPointer);
327 }
328 else {
329 childPointer = parentPointer.getPropertyPointer();
330 ((PropertyPointer) childPointer).setPropertyName(
331 name.toString());
332 childPointer.setAttribute(axis == Compiler.AXIS_ATTRIBUTE);
333 }
334 return childPointer;
335 }
336 else {
337 return parentPointer;
338 }
339 }
340
341 /***
342 * A path that starts with a standard InfoSet node, e.g. a DOM Node.
343 * The method evaluates the first predicate in a special way and
344 * then forwards to a general predicate processing method.
345 */
346 private static NodePointer doStepPredicatesStandard(
347 EvalContext context, NodePointer parent,
348 Step[] steps, int currentStep)
349 {
350 Step step = steps[currentStep];
351 Expression predicates[] = step.getPredicates();
352
353 int axis = step.getAxis();
354 if (axis == Compiler.AXIS_SELF) {
355 return doPredicate(
356 context,
357 parent,
358 steps,
359 currentStep,
360 predicates,
361 0);
362 }
363
364 Expression predicate = predicates[0];
365
366
367
368
369
370
371 if (predicates.length == 1) {
372 NodeIterator it = getNodeIterator(context, parent, step);
373 NodePointer pointer = null;
374 if (it != null) {
375 if (predicate instanceof NameAttributeTest) {
376 String key = keyFromPredicate(context, predicate);
377 for (int i = 1; it.setPosition(i); i++) {
378 NodePointer ptr = it.getNodePointer();
379 if (isNameAttributeEqual(ptr, key)) {
380 pointer = ptr;
381 break;
382 }
383 }
384 }
385 else {
386 int index = indexFromPredicate(context, predicate);
387 if (it.setPosition(index + 1)) {
388 pointer = it.getNodePointer();
389 }
390 }
391 }
392 if (pointer != null) {
393 return doStep(context, pointer, steps, currentStep + 1);
394 }
395 }
396 else {
397 NodeIterator it = getNodeIterator(context, parent, step);
398 if (it != null) {
399 List list = new ArrayList();
400 for (int i = 1; it.setPosition(i); i++) {
401 list.add(it.getNodePointer());
402 }
403 NodePointer pointer =
404 doPredicatesStandard(
405 context,
406 list,
407 steps,
408 currentStep,
409 predicates,
410 0);
411 if (pointer != null) {
412 return pointer;
413 }
414 }
415 }
416 return createNullPointer(context, parent, steps, currentStep);
417 }
418
419 /***
420 * Evaluates predicates and proceeds with the subsequent steps
421 * of the path.
422 */
423 private static NodePointer doPredicate(
424 EvalContext context, NodePointer parent,
425 Step[] steps, int currentStep,
426 Expression predicates[], int currentPredicate)
427 {
428 if (currentPredicate == predicates.length) {
429 return doStep(context, parent, steps, currentStep + 1);
430 }
431
432 Expression predicate = predicates[currentPredicate];
433 if (predicate instanceof NameAttributeTest) {
434 return doPredicateName(
435 context,
436 parent,
437 steps,
438 currentStep,
439 predicates,
440 currentPredicate);
441 }
442 else {
443 return doPredicateIndex(
444 context,
445 parent,
446 steps,
447 currentStep,
448 predicates,
449 currentPredicate);
450 }
451 }
452
453 private static NodePointer doPredicateName(
454 EvalContext context, NodePointer parent,
455 Step[] steps, int currentStep,
456 Expression[] predicates, int currentPredicate)
457 {
458 Expression predicate = predicates[currentPredicate];
459 String key = keyFromPredicate(context, predicate);
460 NodePointer child = valuePointer(parent);
461 if (child instanceof PropertyOwnerPointer) {
462 PropertyPointer pointer =
463 ((PropertyOwnerPointer) child).getPropertyPointer();
464 pointer.setPropertyName(key);
465 if (pointer.isActual()) {
466 return doPredicate(
467 context,
468 pointer,
469 steps,
470 currentStep,
471 predicates,
472 currentPredicate + 1);
473 }
474 }
475 else if (child.isCollection()) {
476
477
478
479
480
481
482 NodePointer bestMatch = null;
483 int bestQuality = 0;
484 child = (NodePointer) child.clone();
485 int count = child.getLength();
486 for (int i = 0; i < count; i++) {
487 child.setIndex(i);
488 NodePointer valuePointer = valuePointer(child);
489 NodePointer pointer;
490 if ((valuePointer instanceof PropertyOwnerPointer)
491 || valuePointer.isCollection()) {
492 pointer =
493 doPredicateName(
494 context,
495 valuePointer,
496 steps,
497 currentStep,
498 predicates,
499 currentPredicate);
500 }
501 else if (isNameAttributeEqual(valuePointer, key)) {
502 pointer =
503 doPredicate(
504 context,
505 valuePointer,
506 steps,
507 currentStep,
508 predicates,
509 currentPredicate + 1);
510 }
511 else {
512 pointer = null;
513 }
514 if (pointer != null) {
515 int quality = computeQuality(pointer);
516 if (quality == PERFECT_MATCH) {
517 return pointer;
518 }
519 if (quality > bestQuality) {
520 bestMatch = (NodePointer) pointer.clone();
521 bestQuality = quality;
522 }
523 }
524 }
525 if (bestMatch != null) {
526 return bestMatch;
527 }
528 }
529 else {
530
531
532
533 NodePointer found =
534 doPredicatesStandard(
535 context,
536 Collections.singletonList(child),
537 steps,
538 currentStep,
539 predicates,
540 currentPredicate);
541 if (found != null) {
542 return found;
543 }
544 }
545
546 return createNullPointerForPredicates(
547 context,
548 child,
549 steps,
550 currentStep,
551 predicates,
552 currentPredicate);
553 }
554
555 /***
556 * Called exclusively for standard InfoSet nodes, e.g. DOM nodes
557 * to evaluate predicate sequences like [@name=...][@name=...][index].
558 */
559 private static NodePointer doPredicatesStandard(
560 EvalContext context, List parents,
561 Step[] steps, int currentStep,
562 Expression predicates[], int currentPredicate)
563 {
564 if (parents.size() == 0) {
565 return null;
566 }
567
568
569
570
571 if (currentPredicate == predicates.length) {
572 NodePointer pointer = (NodePointer) parents.get(0);
573 return doStep(context, pointer, steps, currentStep + 1);
574 }
575
576 Expression predicate = predicates[currentPredicate];
577 if (predicate instanceof NameAttributeTest) {
578 String key = keyFromPredicate(context, predicate);
579 List newList = new ArrayList();
580 for (int i = 0; i < parents.size(); i++) {
581 NodePointer pointer = (NodePointer) parents.get(i);
582 if (isNameAttributeEqual(pointer, key)) {
583 newList.add(pointer);
584 }
585 }
586 if (newList.size() == 0) {
587 return null;
588 }
589 return doPredicatesStandard(
590 context,
591 newList,
592 steps,
593 currentStep,
594 predicates,
595 currentPredicate + 1);
596 }
597 else {
598
599
600
601 int index = indexFromPredicate(context, predicate);
602 if (index < 0 || index >= parents.size()) {
603 return null;
604 }
605 NodePointer ptr = (NodePointer) parents.get(index);
606 return doPredicate(
607 context,
608 ptr,
609 steps,
610 currentStep,
611 predicates,
612 currentPredicate + 1);
613 }
614 }
615
616 /***
617 * Evaluate a subscript predicate: see if the node is a collection and
618 * if the index is inside the collection
619 */
620 private static NodePointer doPredicateIndex(
621 EvalContext context, NodePointer parent,
622 Step[] steps, int currentStep,
623 Expression[] predicates, int currentPredicate)
624 {
625 Expression predicate = predicates[currentPredicate];
626 int index = indexFromPredicate(context, predicate);
627 NodePointer pointer = parent;
628 if (isCollectionElement(pointer, index)) {
629 pointer = (NodePointer) pointer.clone();
630 pointer.setIndex(index);
631 return doPredicate(
632 context,
633 pointer,
634 steps,
635 currentStep,
636 predicates,
637 currentPredicate + 1);
638 }
639 return createNullPointerForPredicates(
640 context,
641 parent,
642 steps,
643 currentStep,
644 predicates,
645 currentPredicate);
646 }
647
648 /***
649 * Extract an integer from a subscript predicate. The returned index
650 * starts with 0, even though the subscript starts with 1.
651 */
652 private static int indexFromPredicate(
653 EvalContext context,
654 Expression predicate)
655 {
656 Object value = predicate.computeValue(context);
657 if (value instanceof EvalContext) {
658 value = ((EvalContext) value).getSingleNodePointer();
659 }
660 if (value instanceof NodePointer) {
661 value = ((NodePointer) value).getValue();
662 }
663 if (value == null) {
664 throw new JXPathException("Predicate value is null");
665 }
666
667 if (value instanceof Number) {
668 return (int) (InfoSetUtil.doubleValue(value) + 0.5) - 1;
669 }
670 else if (InfoSetUtil.booleanValue(value)) {
671 return 0;
672 }
673
674 return -1;
675 }
676
677 /***
678 * Extracts the string value of the expression from a predicate like
679 * [@name=expression].
680 */
681 private static String keyFromPredicate(EvalContext context,
682 Expression predicate)
683 {
684 Expression expr =
685 ((NameAttributeTest) predicate).getNameTestExpression();
686 return InfoSetUtil.stringValue(expr.computeValue(context));
687 }
688
689 /***
690 * For a pointer that matches an actual node, returns 0.
691 * For a pointer that does not match an actual node, but whose
692 * parent pointer does returns -1, etc.
693 */
694 private static int computeQuality(NodePointer pointer) {
695 int quality = PERFECT_MATCH;
696 while (pointer != null && !pointer.isActual()) {
697 quality--;
698 pointer = pointer.getImmediateParentPointer();
699 }
700 return quality;
701 }
702
703 /***
704 * Returns true if the pointer has an attribute called "name" and
705 * its value is equal to the supplied string.
706 */
707 private static boolean isNameAttributeEqual(
708 NodePointer pointer,
709 String name)
710 {
711 NodeIterator it = pointer.attributeIterator(QNAME_NAME);
712 return it != null
713 && it.setPosition(1)
714 && name.equals(it.getNodePointer().getValue());
715 }
716
717 /***
718 * Returns true if the pointer is a collection and the index is
719 * withing the bounds of the collection.
720 */
721 private static boolean isCollectionElement(
722 NodePointer pointer,
723 int index)
724 {
725 return pointer.isActual()
726 && (index == 0
727 || (pointer.isCollection()
728 && index >= 0
729 && index < pointer.getLength()));
730 }
731
732 /***
733 * For an intermediate pointer (e.g. PropertyPointer, ContainerPointer)
734 * returns a pointer for the contained value.
735 */
736 private static NodePointer valuePointer(NodePointer pointer) {
737 return pointer == null ? null : pointer.getValuePointer();
738 }
739
740 /***
741 * Creates a "null pointer" that
742 * a) represents the requested path and
743 * b) can be used for creation of missing nodes in the path.
744 */
745 public static NodePointer createNullPointer(
746 EvalContext context, NodePointer parent, Step[] steps,
747 int currentStep)
748 {
749 if (currentStep == steps.length) {
750 return parent;
751 }
752
753 parent = valuePointer(parent);
754
755 Step step = steps[currentStep];
756
757 int axis = step.getAxis();
758 if (axis == Compiler.AXIS_CHILD || axis == Compiler.AXIS_ATTRIBUTE) {
759 NullPropertyPointer pointer = new NullPropertyPointer(parent);
760 QName name = ((NodeNameTest) step.getNodeTest()).getNodeName();
761 pointer.setPropertyName(name.toString());
762 pointer.setAttribute(axis == Compiler.AXIS_ATTRIBUTE);
763 parent = pointer;
764 }
765
766
767 Expression predicates[] = step.getPredicates();
768 return createNullPointerForPredicates(
769 context,
770 parent,
771 steps,
772 currentStep,
773 predicates,
774 0);
775 }
776
777 /***
778 * Creates a "null pointer" that starts with predicates.
779 */
780 private static NodePointer createNullPointerForPredicates(
781 EvalContext context, NodePointer parent,
782 Step[] steps, int currentStep,
783 Expression predicates[], int currentPredicate)
784 {
785 for (int i = currentPredicate; i < predicates.length; i++) {
786 Expression predicate = predicates[i];
787 if (predicate instanceof NameAttributeTest) {
788 String key = keyFromPredicate(context, predicate);
789 parent = valuePointer(parent);
790 NullPropertyPointer pointer = new NullPropertyPointer(parent);
791 pointer.setNameAttributeValue(key);
792 parent = pointer;
793 }
794 else {
795 int index = indexFromPredicate(context, predicate);
796 if (parent instanceof NullPropertyPointer) {
797 parent.setIndex(index);
798 }
799 else {
800 parent = new NullElementPointer(parent, index);
801 }
802 }
803 }
804
805 return createNullPointer(
806 context, parent, steps, currentStep + 1);
807 }
808
809 private static NodeIterator getNodeIterator(
810 EvalContext context,
811 NodePointer pointer,
812 Step step)
813 {
814 if (step.getAxis() == Compiler.AXIS_CHILD) {
815 NodeTest nodeTest = step.getNodeTest();
816 QName qname = ((NodeNameTest) nodeTest).getNodeName();
817 String prefix = qname.getPrefix();
818 if (prefix != null) {
819 String namespaceURI = context.getJXPathContext()
820 .getNamespaceURI(prefix);
821 nodeTest = new NodeNameTest(qname, namespaceURI);
822
823 }
824 return pointer.childIterator(nodeTest, false, null);
825 }
826 else {
827 if (!(step.getNodeTest() instanceof NodeNameTest)) {
828 throw new UnsupportedOperationException(
829 "Not supported node test for attributes: "
830 + step.getNodeTest());
831 }
832 return pointer.attributeIterator(
833 ((NodeNameTest) step.getNodeTest()).getNodeName());
834 }
835 }
836
837 private static boolean isLangAttribute(QName name) {
838 return name.getPrefix() != null
839 && name.getPrefix().equals("xml")
840 && name.getName().equals("lang");
841 }
842 }