001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *     http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    package org.apache.commons.jxpath.ri.axes;
018    
019    import java.util.ArrayList;
020    import java.util.Collections;
021    import java.util.List;
022    
023    import org.apache.commons.jxpath.JXPathException;
024    import org.apache.commons.jxpath.ri.Compiler;
025    import org.apache.commons.jxpath.ri.EvalContext;
026    import org.apache.commons.jxpath.ri.InfoSetUtil;
027    import org.apache.commons.jxpath.ri.QName;
028    import org.apache.commons.jxpath.ri.compiler.Expression;
029    import org.apache.commons.jxpath.ri.compiler.NameAttributeTest;
030    import org.apache.commons.jxpath.ri.compiler.NodeNameTest;
031    import org.apache.commons.jxpath.ri.compiler.NodeTest;
032    import org.apache.commons.jxpath.ri.compiler.Step;
033    import org.apache.commons.jxpath.ri.model.NodeIterator;
034    import org.apache.commons.jxpath.ri.model.NodePointer;
035    import org.apache.commons.jxpath.ri.model.beans.LangAttributePointer;
036    import org.apache.commons.jxpath.ri.model.beans.NullElementPointer;
037    import org.apache.commons.jxpath.ri.model.beans.NullPropertyPointer;
038    import org.apache.commons.jxpath.ri.model.beans.PropertyOwnerPointer;
039    import org.apache.commons.jxpath.ri.model.beans.PropertyPointer;
040    
041    /**
042     * An evaluation mechanism for simple XPaths, which
043     * is much faster than the usual process. It is only used for
044     * xpaths which have no context-dependent parts, consist entirely of
045     * <code>child::name</code> and <code>self::node()</code> steps with
046     * predicates that either integer or have the form <code>[@name = ...]</code>.
047     *
048     * @author Dmitri Plotnikov
049     * @version $Revision: 652845 $ $Date: 2008-05-02 12:46:46 -0500 (Fri, 02 May 2008) $
050     */
051    public class SimplePathInterpreter {
052    
053        // Because of the complexity caused by the variety of situations
054        // that need to be addressed by this class, we attempt to break up
055        // the class into individual methods addressing those situations
056        // individually.  The names of the methods are supposed to
057        // give brief descriptions of those situations.
058    
059        private static final QName QNAME_NAME = new QName(null, "name");
060        private static final int PERFECT_MATCH = 1000;
061    
062        // Uncomment this variable and the PATH = ... lines in
063        // the two following methods in order to be able to print the
064        // currently evaluated path for debugging of this class
065    //    private static String PATH;       // Debugging
066    
067        /**
068         * Interpret a simple path that starts with the given root and
069         * follows the given steps. All steps must have the axis "child::"
070         * and a name test.  They can also optionally have predicates
071         * of type [@name=expression] or simply [expression] interpreted
072         * as an index.
073         * @param context evaluation context
074         * @param root root pointer
075         * @param steps path steps
076         * @return NodePointer
077         */
078        public static NodePointer interpretSimpleLocationPath(
079                EvalContext context, NodePointer root, Step[] steps) {
080    //        PATH = createNullPointer(context, root, steps, 0).toString();  // Dbg
081            NodePointer pointer = doStep(context, root, steps, 0);
082    //        return valuePointer(pointer);
083            return pointer;
084        }
085    
086        /**
087         * Interpret the steps of a simple expression path that
088         * starts with the given root, which is the result of evaluation
089         * of the root expression of the expression path, applies the
090         * given predicates to it and then follows the given steps.
091         * All steps must have the axis "child::" or "attribute::"
092         * and a name test.  They can also optionally have predicates
093         * of type [@name=...] or simply [...] interpreted as an index.
094         * @param context evaluation context
095         * @param root root pointer
096         * @param predicates predicates corresponding to <code>steps</code>
097         * @param steps path steps
098         * @return NodePointer
099         */
100        public static NodePointer interpretSimpleExpressionPath(
101                    EvalContext context, NodePointer root,
102                    Expression[] predicates, Step[] steps) {
103    //        PATH = createNullPointerForPredicates(context, root,
104    //                    steps, -1, predicates, 0).toString();  // Debugging
105            NodePointer pointer =
106                doPredicate(context, root, steps, -1, predicates, 0);
107    //        return valuePointer(pointer);
108            return pointer;
109        }
110    
111        /**
112         * Recursive evaluation of a path. The general plan is:
113         * Look at the current step,
114         * find nodes that match it,
115         * iterate over those nodes and
116         * for each of them call doStep again for subsequent steps.
117         * @param context evaluation context
118         * @param parent parent pointer
119         * @param steps path steps
120         * @param currentStep step number
121         * @return NodePointer
122         */
123        private static NodePointer doStep(
124                EvalContext context, NodePointer parent,
125                Step[] steps, int currentStep) {
126            if (parent == null) {
127                return null;
128            }
129    
130            if (currentStep == steps.length) {
131                // We have reached the end of the list of steps
132                return parent;
133            }
134    
135            // Open all containers
136            parent = valuePointer(parent);
137    
138            Step step = steps[currentStep];
139            Expression[] predicates = step.getPredicates();
140    
141            // Divide and conquer: the process is broken out into
142            // four major use cases.
143            // 1. Current step has no predicates and
144            //    the root is a property owner (e.g. bean or map)
145            // 2. Current step has predicates and
146            //    the root is a property owner (e.g. bean or map)
147            // 3. Current step has no predicates and
148            //    the root is an InfoSet standard node (e.g. DOM Node)
149            // 4. Current step has predicates and
150            //    the root is an InfoSet standard node (e.g. DOM Node)
151    
152            if (parent instanceof PropertyOwnerPointer) {
153                if (predicates == null || predicates.length == 0) {
154                    return doStepNoPredicatesPropertyOwner(
155                        context,
156                        (PropertyOwnerPointer) parent,
157                        steps,
158                        currentStep);
159                }
160                return doStepPredicatesPropertyOwner(
161                    context,
162                    (PropertyOwnerPointer) parent,
163                    steps,
164                    currentStep);
165            }
166            if (predicates == null || predicates.length == 0) {
167                return doStepNoPredicatesStandard(
168                    context,
169                    parent,
170                    steps,
171                    currentStep);
172            }
173            return doStepPredicatesStandard(
174                context,
175                parent,
176                steps,
177                currentStep);
178        }
179    
180        /**
181         * We have a step that starts with a property owner (bean, map, etc) and has
182         * no predicates.  The name test of the step may map to a scalar property
183         * or to a collection.  If it is a collection, we should apply the tail of
184         * the path to each element until we find a match. If we don't find
185         * a perfect match, we should return the "best quality" pointer, which
186         * has the longest chain of steps mapping to existing nodes and the shortes
187         * tail of Null* pointers.
188         * @param context evaluation context
189         * @param parentPointer property owner pointer
190         * @param steps path steps
191         * @param currentStep step number
192         * @return NodePointer
193         */
194        private static NodePointer doStepNoPredicatesPropertyOwner(
195                    EvalContext context, PropertyOwnerPointer parentPointer,
196                    Step[] steps, int currentStep) {
197            Step step = steps[currentStep];
198            NodePointer childPointer =
199                createChildPointerForStep(parentPointer, step);
200    
201            if (childPointer == null) {
202                return null;
203            }
204            if (!childPointer.isActual()) {
205                // The property does not exist - create a null pointer.
206                return createNullPointer(
207                    context,
208                    parentPointer,
209                    steps,
210                    currentStep);
211            }
212            if (currentStep == steps.length - 1) {
213                // If this is the last step - we are done, we found it
214                return childPointer;
215            }
216            if (childPointer.isCollection()) {
217                // Iterate over all values and
218                // execute remaining steps for each node,
219                // looking for the best quality match
220                int bestQuality = 0;
221                childPointer = (NodePointer) childPointer.clone();
222                NodePointer bestMatch = null;
223                int count = childPointer.getLength();
224                for (int i = 0; i < count; i++) {
225                    childPointer.setIndex(i);
226                    NodePointer pointer =
227                        doStep(context, childPointer, steps, currentStep + 1);
228                    int quality = computeQuality(pointer);
229                    if (quality == PERFECT_MATCH) {
230                        return pointer;
231                    }
232                    else if (quality > bestQuality) {
233                        bestQuality = quality;
234                        bestMatch = (NodePointer) pointer.clone();
235                    }
236                }
237                if (bestMatch != null) {
238                    return bestMatch;
239                }
240                // This step did not find anything - return a null pointer
241                return createNullPointer(context, childPointer, steps, currentStep);
242            }
243            // Evaluate subsequent steps
244            return doStep(context, childPointer, steps, currentStep + 1);
245        }
246    
247        /**
248         * A path that starts with a standard InfoSet node (e.g. DOM Node) and
249         * has no predicates.  Get a child iterator and apply the tail of
250         * the path to each element until we find a match. If we don't find
251         * a perfect match, we should return the "best quality" pointer, which
252         * has the longest chain of steps mapping to existing nodes and the shortes
253         * tail of Null* pointers.
254         * @param context evaluation context
255         * @param parentPointer parent pointer
256         * @param steps path steps
257         * @param currentStep step number
258         * @return NodePointer
259         */
260        private static NodePointer doStepNoPredicatesStandard(
261                    EvalContext context, NodePointer parentPointer,
262                    Step[] steps, int currentStep) {
263            Step step = steps[currentStep];
264    
265            if (step.getAxis() == Compiler.AXIS_SELF) {
266                return doStep(context, parentPointer, steps, currentStep + 1);
267            }
268    
269            int bestQuality = 0;
270            NodePointer bestMatch = null;
271            NodeIterator it = getNodeIterator(context, parentPointer, step);
272            if (it != null) {
273                for (int i = 1; it.setPosition(i); i++) {
274                    NodePointer childPointer = it.getNodePointer();
275                    if (steps.length == currentStep + 1) {
276                        // If this is the last step - we are done, we found it
277                        return childPointer;
278                    }
279                    NodePointer pointer = doStep(
280                            context, childPointer, steps, currentStep + 1);
281                    int quality = computeQuality(pointer);
282                    if (quality == PERFECT_MATCH) {
283                        return pointer;
284                    }
285                    if (quality > bestQuality) {
286                        bestQuality = quality;
287                        bestMatch = (NodePointer) pointer.clone();
288                    }
289                }
290            }
291            return bestMatch != null ? bestMatch
292                    : createNullPointer(context, parentPointer, steps, currentStep);
293        }
294    
295        /**
296         * A path that starts with a property owner. The method evaluates
297         * the first predicate in a special way and then forwards to
298         * a general predicate processing method.
299         * @param context evaluation context
300         * @param parentPointer parent pointer
301         * @param steps path steps
302         * @param currentStep step number
303         * @return NodePointer
304         */
305        private static NodePointer doStepPredicatesPropertyOwner(
306                EvalContext context, PropertyOwnerPointer parentPointer,
307                Step[] steps, int currentStep) {
308            Step step = steps[currentStep];
309            Expression[] predicates = step.getPredicates();
310    
311            NodePointer childPointer =
312                createChildPointerForStep(parentPointer, step);
313            if (!childPointer.isActual()) {
314                // Property does not exist - return a null pointer
315                return createNullPointer(
316                    context,
317                    parentPointer,
318                    steps,
319                    currentStep);
320            }
321    
322            // Evaluate predicates
323            return doPredicate(
324                context,
325                childPointer,
326                steps,
327                currentStep,
328                predicates,
329                0);
330        }
331    
332        /**
333         * Create the child pointer for a given step.
334         * @param parentPointer parent pointer
335         * @param step associated step
336         * @return NodePointer
337         */
338        private static NodePointer createChildPointerForStep(
339                    PropertyOwnerPointer parentPointer, Step step) {
340            int axis = step.getAxis();
341            if (axis == Compiler.AXIS_CHILD || axis == Compiler.AXIS_ATTRIBUTE) {
342                QName name = ((NodeNameTest) step.getNodeTest()).getNodeName();
343                if (axis == Compiler.AXIS_ATTRIBUTE && isLangAttribute(name)) {
344                    return new LangAttributePointer(parentPointer);
345                }
346                if (parentPointer.isValidProperty(name)) {
347                    NodePointer childPointer = parentPointer.getPropertyPointer();
348                    ((PropertyPointer) childPointer).setPropertyName(
349                            name.toString());
350                    childPointer.setAttribute(axis == Compiler.AXIS_ATTRIBUTE);
351                    return childPointer;
352                }
353                //invalid property gets nothing, not even a NullPointer
354                return null;
355            }
356            return parentPointer;
357        }
358    
359        /**
360         * A path that starts with a standard InfoSet node, e.g. a DOM Node.
361         * The method evaluates the first predicate in a special way and
362         * then forwards to a general predicate processing method.
363         * @param context evaluation context
364         * @param parent parent pointer
365         * @param steps path steps
366         * @param currentStep step number
367         * @return NodePointer
368         */
369        private static NodePointer doStepPredicatesStandard(
370                EvalContext context, NodePointer parent,
371                Step[] steps, int currentStep) {
372            Step step = steps[currentStep];
373            Expression[] predicates = step.getPredicates();
374    
375            int axis = step.getAxis();
376            if (axis == Compiler.AXIS_SELF) {
377                return doPredicate(
378                    context,
379                    parent,
380                    steps,
381                    currentStep,
382                    predicates,
383                    0);
384            }
385    
386            Expression predicate = predicates[0];
387    
388            // Optimize for a single predicate to avoid building a list
389            // and to allow the direct access to the index'th element
390            // in the case of a simple subscript predecate
391            // It is a very common use case, so it deserves individual
392            // attention
393            if (predicates.length == 1) {
394                NodeIterator it = getNodeIterator(context, parent, step);
395                NodePointer pointer = null;
396                if (it != null) {
397                    if (predicate instanceof NameAttributeTest) { // [@name = key]
398                        String key = keyFromPredicate(context, predicate);
399                        for (int i = 1; it.setPosition(i); i++) {
400                            NodePointer ptr = it.getNodePointer();
401                            if (isNameAttributeEqual(ptr, key)) {
402                                pointer = ptr;
403                                break;
404                            }
405                        }
406                    }
407                    else {
408                        int index = indexFromPredicate(context, predicate);
409                        if (it.setPosition(index + 1)) {
410                            pointer = it.getNodePointer();
411                        }
412                    }
413                }
414                if (pointer != null) {
415                    return doStep(context, pointer, steps, currentStep + 1);
416                }
417            }
418            else {
419                NodeIterator it = getNodeIterator(context, parent, step);
420                if (it != null) {
421                    List list = new ArrayList();
422                    for (int i = 1; it.setPosition(i); i++) {
423                        list.add(it.getNodePointer());
424                    }
425                    NodePointer pointer =
426                        doPredicatesStandard(
427                            context,
428                            list,
429                            steps,
430                            currentStep,
431                            predicates,
432                            0);
433                    if (pointer != null) {
434                        return pointer;
435                    }
436                }
437            }
438            return createNullPointer(context, parent, steps, currentStep);
439        }
440    
441        /**
442         * Evaluates predicates and proceeds with the subsequent steps
443         * of the path.
444         * @param context evaluation context
445         * @param parent parent pointer
446         * @param steps path steps
447         * @param currentStep step number
448         * @param predicates predicate expressions
449         * @param currentPredicate int predicate number
450         * @return NodePointer
451         */
452        private static NodePointer doPredicate(
453                    EvalContext context, NodePointer parent,
454                    Step[] steps, int currentStep,
455                    Expression[] predicates, int currentPredicate) {
456            if (currentPredicate == predicates.length) {
457                return doStep(context, parent, steps, currentStep + 1);
458            }
459    
460            Expression predicate = predicates[currentPredicate];
461            if (predicate instanceof NameAttributeTest) { // [@name = key1]
462                return doPredicateName(
463                    context,
464                    parent,
465                    steps,
466                    currentStep,
467                    predicates,
468                    currentPredicate);
469            }
470            // else [index]
471            return doPredicateIndex(
472                context,
473                parent,
474                steps,
475                currentStep,
476                predicates,
477                currentPredicate);
478        }
479    
480        /**
481         * Execute a NameAttributeTest predicate
482         * @param context evaluation context
483         * @param parent parent pointer
484         * @param steps path steps
485         * @param currentStep int step number
486         * @param predicates predicates
487         * @param currentPredicate int predicate number
488         * @return NodePointer
489         */
490        private static NodePointer doPredicateName(
491                EvalContext context, NodePointer parent,
492                Step[] steps, int currentStep,
493                Expression[] predicates, int currentPredicate) {
494            Expression predicate = predicates[currentPredicate];
495            String key = keyFromPredicate(context, predicate);
496            NodePointer child = valuePointer(parent);
497            if (child instanceof PropertyOwnerPointer) {
498                PropertyPointer pointer =
499                    ((PropertyOwnerPointer) child).getPropertyPointer();
500                pointer.setPropertyName(key);
501                if (pointer.isActual()) {
502                    return doPredicate(
503                        context,
504                        pointer,
505                        steps,
506                        currentStep,
507                        predicates,
508                        currentPredicate + 1);
509                }
510            }
511            else if (child.isCollection()) {
512                // For each node in the collection, perform the following:
513                // if the node is a property owner, apply this predicate to it;
514                // if the node is a collection, apply this predicate to each elem.;
515                // if the node is not a prop owner or a collection,
516                //  see if it has the attribute "name" with the right value,
517                //  if so - proceed to the next predicate
518                NodePointer bestMatch = null;
519                int bestQuality = 0;
520                child = (NodePointer) child.clone();
521                int count = child.getLength();
522                for (int i = 0; i < count; i++) {
523                    child.setIndex(i);
524                    NodePointer valuePointer = valuePointer(child);
525                    NodePointer pointer;
526                    if ((valuePointer instanceof PropertyOwnerPointer)
527                        || valuePointer.isCollection()) {
528                        pointer =
529                            doPredicateName(
530                                context,
531                                valuePointer,
532                                steps,
533                                currentStep,
534                                predicates,
535                                currentPredicate);
536                    }
537                    else if (isNameAttributeEqual(valuePointer, key)) {
538                        pointer =
539                            doPredicate(
540                                context,
541                                valuePointer,
542                                steps,
543                                currentStep,
544                                predicates,
545                                currentPredicate + 1);
546                    }
547                    else {
548                        pointer = null;
549                    }
550                    if (pointer != null) {
551                        int quality = computeQuality(pointer);
552                        if (quality == PERFECT_MATCH) {
553                            return pointer;
554                        }
555                        if (quality > bestQuality) {
556                            bestMatch = (NodePointer) pointer.clone();
557                            bestQuality = quality;
558                        }
559                    }
560                }
561                if (bestMatch != null) {
562                    return bestMatch;
563                }
564            }
565            else {
566                // If the node is a standard InfoSet node (e.g. DOM Node),
567                // employ doPredicates_standard, which will iterate through
568                // the node's children and apply all predicates
569                NodePointer found =
570                    doPredicatesStandard(
571                        context,
572                        Collections.singletonList(child),
573                        steps,
574                        currentStep,
575                        predicates,
576                        currentPredicate);
577                if (found != null) {
578                    return found;
579                }
580            }
581            // If nothing worked - return a null pointer
582            return createNullPointerForPredicates(
583                context,
584                child,
585                steps,
586                currentStep,
587                predicates,
588                currentPredicate);
589        }
590    
591        /**
592         * Called exclusively for standard InfoSet nodes, e.g. DOM nodes
593         * to evaluate predicate sequences like [@name=...][@name=...][index].
594         * @param context evaluation context
595         * @param parents List of parent pointers
596         * @param steps path steps
597         * @param currentStep step number
598         * @param predicates predicates
599         * @param currentPredicate int predicate number
600         * @return NodePointer
601         */
602        private static NodePointer doPredicatesStandard(
603                    EvalContext context, List parents,
604                    Step[] steps, int currentStep,
605                    Expression[] predicates, int currentPredicate) {
606            if (parents.size() == 0) {
607                return null;
608            }
609    
610            // If all predicates have been processed, take the first
611            // element from the list of results and proceed to the
612            // remaining steps with that element.
613            if (currentPredicate == predicates.length) {
614                NodePointer pointer = (NodePointer) parents.get(0);
615                return doStep(context, pointer, steps, currentStep + 1);
616            }
617    
618            Expression predicate = predicates[currentPredicate];
619            if (predicate instanceof NameAttributeTest) {
620                String key = keyFromPredicate(context, predicate);
621                List newList = new ArrayList();
622                for (int i = 0; i < parents.size(); i++) {
623                    NodePointer pointer = (NodePointer) parents.get(i);
624                    if (isNameAttributeEqual(pointer, key)) {
625                        newList.add(pointer);
626                    }
627                }
628                if (newList.size() == 0) {
629                    return null;
630                }
631                return doPredicatesStandard(
632                    context,
633                    newList,
634                    steps,
635                    currentStep,
636                    predicates,
637                    currentPredicate + 1);
638            }
639            else {
640                // For a subscript, simply take the corresponding
641                // element from the list of results and
642                // proceed to the remaining predicates with that element
643                int index = indexFromPredicate(context, predicate);
644                if (index < 0 || index >= parents.size()) {
645                    return null;
646                }
647                NodePointer ptr = (NodePointer) parents.get(index);
648                return doPredicate(
649                    context,
650                    ptr,
651                    steps,
652                    currentStep,
653                    predicates,
654                    currentPredicate + 1);
655            }
656        }
657    
658        /**
659         * Evaluate a subscript predicate: see if the node is a collection and
660         * if the index is inside the collection.
661         * @param context evaluation context
662         * @param parent parent pointer
663         * @param steps path steps
664         * @param currentStep step number
665         * @param predicates predicates
666         * @param currentPredicate int predicate number
667         * @return NodePointer
668         */
669        private static NodePointer doPredicateIndex(
670                EvalContext context, NodePointer parent,
671                Step[] steps, int currentStep,
672                Expression[] predicates, int currentPredicate) {
673            Expression predicate = predicates[currentPredicate];
674            int index = indexFromPredicate(context, predicate);
675            NodePointer pointer = parent;
676            if (isCollectionElement(pointer, index)) {
677                pointer = (NodePointer) pointer.clone();
678                pointer.setIndex(index);
679                return doPredicate(
680                    context,
681                    pointer,
682                    steps,
683                    currentStep,
684                    predicates,
685                    currentPredicate + 1);
686            }
687            return createNullPointerForPredicates(
688                context,
689                parent,
690                steps,
691                currentStep,
692                predicates,
693                currentPredicate);
694        }
695    
696        /**
697         * Extract an integer from a subscript predicate. The returned index
698         * starts with 0, even though the subscript starts with 1.
699         * @param context evaluation context
700         * @param predicate to evaluate
701         * @return calculated index
702         */
703        private static int indexFromPredicate(
704            EvalContext context,
705            Expression predicate) {
706            Object value = predicate.computeValue(context);
707            if (value instanceof EvalContext) {
708                value = ((EvalContext) value).getSingleNodePointer();
709            }
710            if (value instanceof NodePointer) {
711                value = ((NodePointer) value).getValue();
712            }
713            if (value == null) {
714                throw new JXPathException("Predicate value is null: " + predicate);
715            }
716    
717            if (value instanceof Number) {
718                final double round = 0.5;
719                return (int) (InfoSetUtil.doubleValue(value) + round) - 1;
720            }
721            return InfoSetUtil.booleanValue(value) ? 0 : -1;
722        }
723    
724        /**
725         * Extracts the string value of the expression from a predicate like
726         * [@name=expression].
727         * @param context evaluation context
728         * @param predicate predicate to evaluate
729         * @return String key extracted
730         */
731        private static String keyFromPredicate(EvalContext context,
732                    Expression predicate) {
733            Expression expr =
734                ((NameAttributeTest) predicate).getNameTestExpression();
735            return InfoSetUtil.stringValue(expr.computeValue(context));
736        }
737    
738        /**
739         * For a pointer that matches an actual node, returns 0.
740         * For a pointer that does not match an actual node, but whose
741         * parent pointer does returns -1, etc.
742         * @param pointer input pointer
743         * @return int match quality code
744         */
745        private static int computeQuality(NodePointer pointer) {
746            int quality = PERFECT_MATCH;
747            while (pointer != null && !pointer.isActual()) {
748                quality--;
749                pointer = pointer.getImmediateParentPointer();
750            }
751            return quality;
752        }
753    
754        /**
755         * Returns true if the pointer has an attribute called "name" and
756         * its value is equal to the supplied string.
757         * @param pointer input pointer
758         * @param name name to check
759         * @return boolean
760         */
761        private static boolean isNameAttributeEqual(
762            NodePointer pointer,
763            String name) {
764            NodeIterator it = pointer.attributeIterator(QNAME_NAME);
765            return it != null
766                && it.setPosition(1)
767                && name.equals(it.getNodePointer().getValue());
768        }
769    
770        /**
771         * Returns true if the pointer is a collection and the index is
772         * withing the bounds of the collection.
773         * @param pointer input pointer
774         * @param index to check
775         * @return boolean
776         */
777        private static boolean isCollectionElement(
778            NodePointer pointer,
779            int index) {
780            return pointer.isActual()
781                && (index == 0
782                    || (pointer.isCollection()
783                        && index >= 0
784                        && index < pointer.getLength()));
785        }
786    
787        /**
788         * For an intermediate pointer (e.g. PropertyPointer, ContainerPointer)
789         * returns a pointer for the contained value.
790         * @param pointer input pointer
791         * @return NodePointer
792         */
793        private static NodePointer valuePointer(NodePointer pointer) {
794            return pointer == null ? null : pointer.getValuePointer();
795        }
796    
797        /**
798         * Creates a "null pointer" that
799         * a) represents the requested path and
800         * b) can be used for creation of missing nodes in the path.
801         * @param context evaluation context
802         * @param parent parent pointer
803         * @param steps path steps
804         * @param currentStep step number
805         * @return NodePointer
806         */
807        public static NodePointer createNullPointer(
808                EvalContext context, NodePointer parent, Step[] steps,
809                int currentStep) {
810            if (currentStep == steps.length) {
811                return parent;
812            }
813    
814            parent = valuePointer(parent);
815    
816            Step step = steps[currentStep];
817    
818            int axis = step.getAxis();
819            if (axis == Compiler.AXIS_CHILD || axis == Compiler.AXIS_ATTRIBUTE) {
820                NullPropertyPointer pointer = new NullPropertyPointer(parent);
821                QName name = ((NodeNameTest) step.getNodeTest()).getNodeName();
822                pointer.setPropertyName(name.toString());
823                pointer.setAttribute(axis == Compiler.AXIS_ATTRIBUTE);
824                parent = pointer;
825            }
826            // else { it is self::node() }
827    
828            Expression[] predicates = step.getPredicates();
829            return createNullPointerForPredicates(
830                context,
831                parent,
832                steps,
833                currentStep,
834                predicates,
835                0);
836        }
837    
838        /**
839         * Creates a "null pointer" that starts with predicates.
840         * @param context evaluation context
841         * @param parent parent pointer
842         * @param steps path steps
843         * @param currentStep step number
844         * @param predicates predicates
845         * @param currentPredicate int predicate number
846         * @return NodePointer
847         */
848        private static NodePointer createNullPointerForPredicates(
849                EvalContext context, NodePointer parent,
850                Step[] steps, int currentStep,
851                Expression[] predicates, int currentPredicate) {
852            for (int i = currentPredicate; i < predicates.length; i++) {
853                Expression predicate = predicates[i];
854                if (predicate instanceof NameAttributeTest) {
855                    String key = keyFromPredicate(context, predicate);
856                    parent = valuePointer(parent);
857                    NullPropertyPointer pointer = new NullPropertyPointer(parent);
858                    pointer.setNameAttributeValue(key);
859                    parent = pointer;
860                }
861                else {
862                    int index = indexFromPredicate(context, predicate);
863                    if (parent instanceof NullPropertyPointer) {
864                        parent.setIndex(index);
865                    }
866                    else {
867                        parent = new NullElementPointer(parent, index);
868                    }
869                }
870            }
871            // Proceed with the remaining steps
872            return createNullPointer(
873                        context, parent, steps, currentStep + 1);
874        }
875    
876        /**
877         * Get a NodeIterator.
878         * @param context evaluation context
879         * @param pointer owning pointer
880         * @param step triggering step
881         * @return NodeIterator
882         */
883        private static NodeIterator getNodeIterator(
884            EvalContext context,
885            NodePointer pointer,
886            Step step) {
887            if (step.getAxis() == Compiler.AXIS_CHILD) {
888                NodeTest nodeTest = step.getNodeTest();
889                QName qname = ((NodeNameTest) nodeTest).getNodeName();
890                String prefix = qname.getPrefix();
891                if (prefix != null) {
892                    String namespaceURI = context.getJXPathContext()
893                            .getNamespaceURI(prefix);
894                    nodeTest = new NodeNameTest(qname, namespaceURI);
895                }
896                return pointer.childIterator(nodeTest, false, null);
897            }
898            // else Compiler.AXIS_ATTRIBUTE
899            if (!(step.getNodeTest() instanceof NodeNameTest)) {
900                throw new UnsupportedOperationException(
901                    "Not supported node test for attributes: "
902                        + step.getNodeTest());
903            }
904            return pointer.attributeIterator(
905                ((NodeNameTest) step.getNodeTest()).getNodeName());
906        }
907    
908        /**
909         * Learn whether <code>name</code> is a lang attribute.
910         * @param name to compare
911         * @return boolean
912         */
913        private static boolean isLangAttribute(QName name) {
914            return name.getPrefix() != null
915                && name.getPrefix().equals("xml")
916                && name.getName().equals("lang");
917        }
918    }