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.compiler;
018    
019    import org.apache.commons.jxpath.Pointer;
020    import org.apache.commons.jxpath.ri.Compiler;
021    import org.apache.commons.jxpath.ri.EvalContext;
022    import org.apache.commons.jxpath.ri.QName;
023    import org.apache.commons.jxpath.ri.axes.AncestorContext;
024    import org.apache.commons.jxpath.ri.axes.AttributeContext;
025    import org.apache.commons.jxpath.ri.axes.ChildContext;
026    import org.apache.commons.jxpath.ri.axes.DescendantContext;
027    import org.apache.commons.jxpath.ri.axes.InitialContext;
028    import org.apache.commons.jxpath.ri.axes.NamespaceContext;
029    import org.apache.commons.jxpath.ri.axes.ParentContext;
030    import org.apache.commons.jxpath.ri.axes.PrecedingOrFollowingContext;
031    import org.apache.commons.jxpath.ri.axes.PredicateContext;
032    import org.apache.commons.jxpath.ri.axes.SelfContext;
033    import org.apache.commons.jxpath.ri.axes.SimplePathInterpreter;
034    import org.apache.commons.jxpath.ri.axes.UnionContext;
035    import org.apache.commons.jxpath.ri.model.NodePointer;
036    
037    /**
038     * @author Dmitri Plotnikov
039     * @version $Revision: 681111 $ $Date: 2008-07-30 11:30:29 -0500 (Wed, 30 Jul 2008) $
040     */
041    public abstract class Path extends Expression {
042    
043        private Step[] steps;
044        private boolean basicKnown = false;
045        private boolean basic;
046    
047        /**
048         * Create a new Path.
049         * @param steps that compose the Path
050         */
051        public Path(Step[] steps) {
052            this.steps = steps;
053        }
054    
055        /**
056         * Get the steps.
057         * @return Step[]
058         */
059        public Step[] getSteps() {
060            return steps;
061        }
062    
063        public boolean computeContextDependent() {
064            if (steps != null) {
065                for (int i = 0; i < steps.length; i++) {
066                    if (steps[i].isContextDependent()) {
067                        return true;
068                    }
069                }
070            }
071            return false;
072        }
073    
074        /**
075         * Recognizes paths formatted as <code>foo/bar[3]/baz[@name = 'biz']</code>.
076         * The evaluation of such "simple" paths is optimized and
077         * streamlined.
078         * @return <code>true</code> if this path is simple
079         */
080        public synchronized boolean isSimplePath() {
081            if (!basicKnown) {
082                basicKnown = true;
083                basic = true;
084                Step[] steps = getSteps();
085                for (int i = 0; i < steps.length; i++) {
086                    if (!isSimpleStep(steps[i])) {
087                        basic = false;
088                        break;
089                    }
090                }
091            }
092            return basic;
093        }
094    
095        /**
096         * A Step is "simple" if it takes one of these forms: ".", "/foo",
097         * "@bar", "/foo[3]". If there are predicates, they should be
098         * context independent for the step to still be considered simple.
099         * @param step the step to check
100         * @return boolean
101         */
102        protected boolean isSimpleStep(Step step) {
103            if (step.getAxis() == Compiler.AXIS_SELF) {
104                NodeTest nodeTest = step.getNodeTest();
105                if (!(nodeTest instanceof NodeTypeTest)) {
106                    return false;
107                }
108                int nodeType = ((NodeTypeTest) nodeTest).getNodeType();
109                if (nodeType != Compiler.NODE_TYPE_NODE) {
110                    return false;
111                }
112                return areBasicPredicates(step.getPredicates());
113            }
114            if (step.getAxis() == Compiler.AXIS_CHILD
115                    || step.getAxis() == Compiler.AXIS_ATTRIBUTE) {
116                NodeTest nodeTest = step.getNodeTest();
117                if (!(nodeTest instanceof NodeNameTest)) {
118                    return false;
119                }
120                if (((NodeNameTest) nodeTest).isWildcard()) {
121                    return false;
122                }
123                return areBasicPredicates(step.getPredicates());
124            }
125            return false;
126        }
127    
128        /**
129         * Learn whether the elements of the specified array are "basic" predicates.
130         * @param predicates the Expression[] to check
131         * @return boolean
132         */
133        protected boolean areBasicPredicates(Expression[] predicates) {
134            if (predicates != null && predicates.length != 0) {
135                boolean firstIndex = true;
136                for (int i = 0; i < predicates.length; i++) {
137                    if (predicates[i] instanceof NameAttributeTest) {
138                        if (((NameAttributeTest) predicates[i])
139                            .getNameTestExpression()
140                            .isContextDependent()) {
141                            return false;
142                        }
143                    }
144                    else if (predicates[i].isContextDependent()) {
145                        return false;
146                    }
147                    else {
148                        if (!firstIndex) {
149                            return false;
150                        }
151                        firstIndex = false;
152                    }
153                }
154            }
155            return true;
156        }
157    
158        /**
159         * Given a root context, walks a path therefrom and finds the
160         * pointer to the first element matching the path.
161         * @param context evaluation context
162         * @return Pointer
163         */
164        protected Pointer getSingleNodePointerForSteps(EvalContext context) {
165            if (steps.length == 0) {
166                return context.getSingleNodePointer();
167            }
168    
169            if (isSimplePath()) {
170                NodePointer ptr = (NodePointer) context.getSingleNodePointer();
171                return SimplePathInterpreter.interpretSimpleLocationPath(
172                    context,
173                    ptr,
174                    steps);
175            }
176            return searchForPath(context);
177        }
178    
179        /**
180         * The idea here is to return a NullPointer rather than null if that's at
181         * all possible. Take for example this path: "//map/key". Let's say, "map"
182         * is an existing node, but "key" is not there. We will create a
183         * NullPointer that can be used to set/create the "key" property.
184         * <p>
185         * However, a path like "//key" would still produce null, because we have
186         * no way of knowing where "key" would be if it existed.
187         * </p>
188         * <p>
189         * To accomplish this, we first try the path itself. If it does not find
190         * anything, we chop off last step of the path, as long as it is a simple
191         * one like child:: or attribute:: and try to evaluate the truncated path.
192         * If it finds exactly one node - create a NullPointer and return. If it
193         * fails, chop off another step and repeat. If it finds more than one
194         * location - return null.
195         * </p>
196         * @param context evaluation context
197         * @return Pointer
198         */
199        protected Pointer searchForPath(EvalContext context) {
200            EvalContext ctx = buildContextChain(context, steps.length, true);
201            Pointer pointer = ctx.getSingleNodePointer();
202    
203            if (pointer != null) {
204                return pointer;
205            }
206    
207            for (int i = steps.length; --i > 0;) {
208                if (!isSimpleStep(steps[i])) {
209                    return null;
210                }
211                ctx = buildContextChain(context, i, true);
212                if (ctx.hasNext()) {
213                    Pointer partial = (Pointer) ctx.next();
214                    if (ctx.hasNext()) {
215                        // If we find another location - the search is
216                        // ambiguous, so we report failure
217                        return null;
218                    }
219                    if (partial instanceof NodePointer) {
220                        return SimplePathInterpreter.createNullPointer(
221                                context,
222                                (NodePointer) partial,
223                                steps,
224                                i);
225                    }
226                }
227            }
228            return null;
229        }
230    
231        /**
232         * Given a root context, walks a path therefrom and builds a context
233         * that contains all nodes matching the path.
234         * @param context evaluation context
235         * @return EvaluationContext
236         */
237        protected EvalContext evalSteps(EvalContext context) {
238            return buildContextChain(context, steps.length, false);
239        }
240    
241        /**
242         * Build a context from a chain of contexts.
243         * @param context evaluation context
244         * @param stepCount number of steps to descend
245         * @param createInitialContext whether to create the initial context
246         * @return created context
247         */
248        protected EvalContext buildContextChain(
249                EvalContext context,
250                int stepCount,
251                boolean createInitialContext) {
252            if (createInitialContext) {
253                context = new InitialContext(context);
254            }
255            if (steps.length == 0) {
256                return context;
257            }
258            for (int i = 0; i < stepCount; i++) {
259                context =
260                    createContextForStep(
261                        context,
262                        steps[i].getAxis(),
263                        steps[i].getNodeTest());
264                Expression[] predicates = steps[i].getPredicates();
265                if (predicates != null) {
266                    for (int j = 0; j < predicates.length; j++) {
267                        if (j != 0) {
268                            context = new UnionContext(context, new EvalContext[]{context});
269                        }
270                        context = new PredicateContext(context, predicates[j]);
271                    }
272                }
273            }
274            return context;
275        }
276    
277        /**
278         * Different axes are serviced by different contexts. This method
279         * allocates the right context for the supplied step.
280         * @param context evaluation context
281         * @param axis code
282         * @param nodeTest node test
283         * @return EvalContext
284         */
285        protected EvalContext createContextForStep(
286            EvalContext context,
287            int axis,
288            NodeTest nodeTest) {
289            if (nodeTest instanceof NodeNameTest) {
290                QName qname = ((NodeNameTest) nodeTest).getNodeName();
291                String prefix = qname.getPrefix();
292                if (prefix != null) {
293                    String namespaceURI = context.getJXPathContext()
294                            .getNamespaceURI(prefix);
295                    nodeTest = new NodeNameTest(qname, namespaceURI);
296                }
297            }
298    
299            switch (axis) {
300            case Compiler.AXIS_ANCESTOR :
301                return new AncestorContext(context, false, nodeTest);
302            case Compiler.AXIS_ANCESTOR_OR_SELF :
303                return new AncestorContext(context, true, nodeTest);
304            case Compiler.AXIS_ATTRIBUTE :
305                return new AttributeContext(context, nodeTest);
306            case Compiler.AXIS_CHILD :
307                return new ChildContext(context, nodeTest, false, false);
308            case Compiler.AXIS_DESCENDANT :
309                return new DescendantContext(context, false, nodeTest);
310            case Compiler.AXIS_DESCENDANT_OR_SELF :
311                return new DescendantContext(context, true, nodeTest);
312            case Compiler.AXIS_FOLLOWING :
313                return new PrecedingOrFollowingContext(context, nodeTest, false);
314            case Compiler.AXIS_FOLLOWING_SIBLING :
315                return new ChildContext(context, nodeTest, true, false);
316            case Compiler.AXIS_NAMESPACE :
317                return new NamespaceContext(context, nodeTest);
318            case Compiler.AXIS_PARENT :
319                return new ParentContext(context, nodeTest);
320            case Compiler.AXIS_PRECEDING :
321                return new PrecedingOrFollowingContext(context, nodeTest, true);
322            case Compiler.AXIS_PRECEDING_SIBLING :
323                return new ChildContext(context, nodeTest, true, true);
324            case Compiler.AXIS_SELF :
325                return new SelfContext(context, nodeTest);
326            default:
327                return null; // Never happens
328            }
329        }
330    }