001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one
003     * or more contributor license agreements. See the NOTICE file
004     * distributed with this work for additional information
005     * regarding copyright ownership. The ASF licenses this file
006     * to you under the Apache License, Version 2.0 (the  "License");
007     * you may not use this file except in compliance with the License.
008     * You may obtain a copy of the License at
009     *
010     *     http://www.apache.org/licenses/LICENSE-2.0
011     *
012     * Unless required by applicable law or agreed to in writing, software
013     * distributed under the License is distributed on an "AS IS" BASIS,
014     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015     * See the License for the specific language governing permissions and
016     * limitations under the License.
017     */
018    /*
019     * $Id: StepPattern.java 468650 2006-10-28 07:03:30Z minchau $
020     */
021    
022    package org.apache.xalan.xsltc.compiler;
023    
024    import java.util.Vector;
025    
026    import org.apache.bcel.classfile.Field;
027    import org.apache.bcel.generic.ALOAD;
028    import org.apache.bcel.generic.ASTORE;
029    import org.apache.bcel.generic.BranchHandle;
030    import org.apache.bcel.generic.ConstantPoolGen;
031    import org.apache.bcel.generic.GETFIELD;
032    import org.apache.bcel.generic.GOTO;
033    import org.apache.bcel.generic.GOTO_W;
034    import org.apache.bcel.generic.IFLT;
035    import org.apache.bcel.generic.IFNE;
036    import org.apache.bcel.generic.IFNONNULL;
037    import org.apache.bcel.generic.IF_ICMPEQ;
038    import org.apache.bcel.generic.IF_ICMPLT;
039    import org.apache.bcel.generic.IF_ICMPNE;
040    import org.apache.bcel.generic.ILOAD;
041    import org.apache.bcel.generic.INVOKEINTERFACE;
042    import org.apache.bcel.generic.INVOKESPECIAL;
043    import org.apache.bcel.generic.ISTORE;
044    import org.apache.bcel.generic.InstructionHandle;
045    import org.apache.bcel.generic.InstructionList;
046    import org.apache.bcel.generic.LocalVariableGen;
047    import org.apache.bcel.generic.NEW;
048    import org.apache.bcel.generic.PUSH;
049    import org.apache.bcel.generic.PUTFIELD;
050    import org.apache.xalan.xsltc.compiler.util.ClassGenerator;
051    import org.apache.xalan.xsltc.compiler.util.MethodGenerator;
052    import org.apache.xalan.xsltc.compiler.util.Type;
053    import org.apache.xalan.xsltc.compiler.util.TypeCheckError;
054    import org.apache.xalan.xsltc.compiler.util.Util;
055    import org.apache.xml.dtm.Axis;
056    import org.apache.xml.dtm.DTM;
057    
058    /**
059     * @author Jacek Ambroziak
060     * @author Santiago Pericas-Geertsen
061     * @author Erwin Bolwidt <ejb@klomp.org>
062     */
063    class StepPattern extends RelativePathPattern {
064    
065        private static final int NO_CONTEXT = 0;
066        private static final int SIMPLE_CONTEXT = 1;
067        private static final int GENERAL_CONTEXT = 2;
068    
069        protected final int _axis;
070        protected final int _nodeType;
071        protected Vector _predicates;
072    
073        private Step    _step = null;
074        private boolean _isEpsilon = false;
075        private int     _contextCase;
076    
077        private double  _priority = Double.MAX_VALUE;
078    
079        public StepPattern(int axis, int nodeType, Vector predicates) {
080            _axis = axis;
081            _nodeType = nodeType;
082            _predicates = predicates;
083        }
084    
085        public void setParser(Parser parser) {
086            super.setParser(parser);
087            if (_predicates != null) {
088                final int n = _predicates.size();
089                for (int i = 0; i < n; i++) {
090                    final Predicate exp = (Predicate)_predicates.elementAt(i);
091                    exp.setParser(parser);
092                    exp.setParent(this);
093                }
094            }
095        }
096    
097        public int getNodeType() {
098            return _nodeType;
099        }
100    
101        public void setPriority(double priority) {
102            _priority = priority;
103        }
104        
105        public StepPattern getKernelPattern() {
106            return this;
107        }
108            
109        public boolean isWildcard() {
110            return _isEpsilon && hasPredicates() == false;
111        }
112    
113        public StepPattern setPredicates(Vector predicates) {
114            _predicates = predicates;
115            return(this);
116        }
117        
118        protected boolean hasPredicates() {
119            return _predicates != null && _predicates.size() > 0;
120        }
121    
122        public double getDefaultPriority() {
123            if (_priority != Double.MAX_VALUE) {
124                return _priority;
125            }
126    
127            if (hasPredicates()) {
128                return 0.5;
129            }
130            else {
131                switch(_nodeType) {
132                case -1:
133                    return -0.5;    // node()
134                case 0:
135                    return 0.0;
136                default:
137                    return (_nodeType >= NodeTest.GTYPE) ? 0.0 : -0.5;
138                }
139            }
140        }
141        
142        public int getAxis() {
143            return _axis;
144        }
145    
146        public void reduceKernelPattern() {
147            _isEpsilon = true;
148        }
149            
150        public String toString() {
151            final StringBuffer buffer = new StringBuffer("stepPattern(\"");
152        buffer.append(Axis.getNames(_axis))
153                .append("\", ")
154                .append(_isEpsilon ? 
155                            ("epsilon{" + Integer.toString(_nodeType) + "}") :
156                             Integer.toString(_nodeType));
157            if (_predicates != null)
158                buffer.append(", ").append(_predicates.toString());
159            return buffer.append(')').toString();
160        }
161        
162        private int analyzeCases() {
163            boolean noContext = true;
164            final int n = _predicates.size();
165    
166            for (int i = 0; i < n && noContext; i++) {
167                Predicate pred = (Predicate) _predicates.elementAt(i);
168                if (pred.isNthPositionFilter() || 
169                    pred.hasPositionCall() || 
170                    pred.hasLastCall()) 
171                {
172                    noContext = false;
173                }
174            }
175    
176            if (noContext) {
177                return NO_CONTEXT;
178            }
179            else if (n == 1) {
180                return SIMPLE_CONTEXT;
181            }
182            return GENERAL_CONTEXT;
183        }
184    
185        private String getNextFieldName() {
186            return  "__step_pattern_iter_" + getXSLTC().nextStepPatternSerial();
187        }
188    
189        public Type typeCheck(SymbolTable stable) throws TypeCheckError {
190            if (hasPredicates()) {
191                // Type check all the predicates (e -> position() = e)
192                final int n = _predicates.size();
193                for (int i = 0; i < n; i++) {
194                    final Predicate pred = (Predicate)_predicates.elementAt(i);
195                    pred.typeCheck(stable);
196                }
197    
198                // Analyze context cases
199                _contextCase = analyzeCases();
200    
201                Step step = null;
202    
203                // Create an instance of Step to do the translation
204                if (_contextCase == SIMPLE_CONTEXT) {
205                    Predicate pred = (Predicate)_predicates.elementAt(0);
206                    if (pred.isNthPositionFilter()) {
207                        _contextCase = GENERAL_CONTEXT;
208                        step = new Step(_axis, _nodeType, _predicates);
209                    } else {
210                        step = new Step(_axis, _nodeType, null);
211                    }
212                } else if (_contextCase == GENERAL_CONTEXT) {
213                    final int len = _predicates.size();
214                    for (int i = 0; i < len; i++) {
215                        ((Predicate)_predicates.elementAt(i)).dontOptimize();
216                    }
217    
218                    step = new Step(_axis, _nodeType, _predicates);
219                }
220                
221                if (step != null) {
222                    step.setParser(getParser());
223                    step.typeCheck(stable);
224                    _step = step;
225                }
226            }
227            return _axis == Axis.CHILD ? Type.Element : Type.Attribute;
228        }
229    
230        private void translateKernel(ClassGenerator classGen, 
231                                     MethodGenerator methodGen) {
232            final ConstantPoolGen cpg = classGen.getConstantPool();
233            final InstructionList il = methodGen.getInstructionList();
234            
235            if (_nodeType == DTM.ELEMENT_NODE) {
236                final int check = cpg.addInterfaceMethodref(DOM_INTF,
237                                                            "isElement", "(I)Z");
238                il.append(methodGen.loadDOM());
239                il.append(SWAP);
240                il.append(new INVOKEINTERFACE(check, 2));
241            
242                // Need to allow for long jumps here
243                final BranchHandle icmp = il.append(new IFNE(null));
244                _falseList.add(il.append(new GOTO_W(null)));
245                icmp.setTarget(il.append(NOP));
246            }
247            else if (_nodeType == DTM.ATTRIBUTE_NODE) {
248                final int check = cpg.addInterfaceMethodref(DOM_INTF,
249                                                            "isAttribute", "(I)Z");
250                il.append(methodGen.loadDOM());
251                il.append(SWAP);
252                il.append(new INVOKEINTERFACE(check, 2));
253            
254                // Need to allow for long jumps here
255                final BranchHandle icmp = il.append(new IFNE(null));
256                _falseList.add(il.append(new GOTO_W(null)));
257                icmp.setTarget(il.append(NOP));
258            }
259            else {
260                // context node is on the stack
261                final int getEType = cpg.addInterfaceMethodref(DOM_INTF,
262                                                              "getExpandedTypeID",
263                                                              "(I)I");
264                il.append(methodGen.loadDOM());
265                il.append(SWAP);
266                il.append(new INVOKEINTERFACE(getEType, 2));
267                il.append(new PUSH(cpg, _nodeType));
268            
269                // Need to allow for long jumps here
270                final BranchHandle icmp = il.append(new IF_ICMPEQ(null));
271                _falseList.add(il.append(new GOTO_W(null)));
272                icmp.setTarget(il.append(NOP));
273            }
274        }
275    
276        private void translateNoContext(ClassGenerator classGen, 
277                                        MethodGenerator methodGen) {
278            final ConstantPoolGen cpg = classGen.getConstantPool();
279            final InstructionList il = methodGen.getInstructionList();
280    
281            // Push current node on the stack
282            il.append(methodGen.loadCurrentNode());
283            il.append(SWAP);
284    
285            // Overwrite current node with matching node
286            il.append(methodGen.storeCurrentNode());
287    
288            // If pattern not reduced then check kernel
289            if (!_isEpsilon) {
290                il.append(methodGen.loadCurrentNode());
291                translateKernel(classGen, methodGen);
292            }
293    
294            // Compile the expressions within the predicates
295            final int n = _predicates.size();
296            for (int i = 0; i < n; i++) {
297                Predicate pred = (Predicate)_predicates.elementAt(i);
298                Expression exp = pred.getExpr();
299                exp.translateDesynthesized(classGen, methodGen);
300                _trueList.append(exp._trueList);
301                _falseList.append(exp._falseList);
302            }
303    
304            // Backpatch true list and restore current iterator/node
305            InstructionHandle restore;
306            restore = il.append(methodGen.storeCurrentNode());
307            backPatchTrueList(restore);
308            BranchHandle skipFalse = il.append(new GOTO(null));
309    
310            // Backpatch false list and restore current iterator/node
311            restore = il.append(methodGen.storeCurrentNode());
312            backPatchFalseList(restore);
313            _falseList.add(il.append(new GOTO(null)));
314    
315            // True list falls through
316            skipFalse.setTarget(il.append(NOP));
317        }
318    
319        private void translateSimpleContext(ClassGenerator classGen, 
320                                            MethodGenerator methodGen) {
321            int index;
322            final ConstantPoolGen cpg = classGen.getConstantPool();
323            final InstructionList il = methodGen.getInstructionList();
324    
325            // Store matching node into a local variable
326            LocalVariableGen match;
327            match = methodGen.addLocalVariable("step_pattern_tmp1", 
328                                               Util.getJCRefType(NODE_SIG),
329                                               null, null);
330            match.setStart(il.append(new ISTORE(match.getIndex())));
331    
332            // If pattern not reduced then check kernel
333            if (!_isEpsilon) {
334                il.append(new ILOAD(match.getIndex()));
335                translateKernel(classGen, methodGen);
336            }
337    
338            // Push current iterator and current node on the stack
339            il.append(methodGen.loadCurrentNode());
340            il.append(methodGen.loadIterator());
341    
342            // Create a new matching iterator using the matching node
343            index = cpg.addMethodref(MATCHING_ITERATOR, "<init>", 
344                                     "(I" + NODE_ITERATOR_SIG + ")V");
345    
346            // Backwards branches are prohibited if an uninitialized object is
347            // on the stack by section 4.9.4 of the JVM Specification, 2nd Ed.
348            // We don't know whether this code might contain backwards branches,
349            // so we mustn't create the new object until after we've created
350            // the suspect arguments to its constructor.  Instead we calculate
351            // the values of the arguments to the constructor first, store them
352            // in temporary variables, create the object and reload the
353            // arguments from the temporaries to avoid the problem.
354    
355            _step.translate(classGen, methodGen);
356            LocalVariableGen stepIteratorTemp =
357                    methodGen.addLocalVariable("step_pattern_tmp2",
358                                               Util.getJCRefType(NODE_ITERATOR_SIG),
359                                               null, null);
360            stepIteratorTemp.setStart(
361                    il.append(new ASTORE(stepIteratorTemp.getIndex())));
362    
363            il.append(new NEW(cpg.addClass(MATCHING_ITERATOR)));
364            il.append(DUP);
365            il.append(new ILOAD(match.getIndex()));
366            stepIteratorTemp.setEnd(
367                    il.append(new ALOAD(stepIteratorTemp.getIndex())));
368            il.append(new INVOKESPECIAL(index));
369    
370            // Get the parent of the matching node
371            il.append(methodGen.loadDOM());
372            il.append(new ILOAD(match.getIndex()));
373            index = cpg.addInterfaceMethodref(DOM_INTF, GET_PARENT, GET_PARENT_SIG);
374            il.append(new INVOKEINTERFACE(index, 2));
375    
376            // Start the iterator with the parent 
377            il.append(methodGen.setStartNode());
378    
379            // Overwrite current iterator and current node
380            il.append(methodGen.storeIterator());
381            match.setEnd(il.append(new ILOAD(match.getIndex())));
382            il.append(methodGen.storeCurrentNode());
383    
384            // Translate the expression of the predicate 
385            Predicate pred = (Predicate) _predicates.elementAt(0);
386            Expression exp = pred.getExpr();
387            exp.translateDesynthesized(classGen, methodGen);
388    
389            // Backpatch true list and restore current iterator/node
390            InstructionHandle restore = il.append(methodGen.storeIterator());
391            il.append(methodGen.storeCurrentNode());
392            exp.backPatchTrueList(restore);
393            BranchHandle skipFalse = il.append(new GOTO(null));
394    
395            // Backpatch false list and restore current iterator/node
396            restore = il.append(methodGen.storeIterator());
397            il.append(methodGen.storeCurrentNode());
398            exp.backPatchFalseList(restore);
399            _falseList.add(il.append(new GOTO(null)));
400    
401            // True list falls through
402            skipFalse.setTarget(il.append(NOP));
403        }
404    
405        private void translateGeneralContext(ClassGenerator classGen, 
406                                             MethodGenerator methodGen) {
407            final ConstantPoolGen cpg = classGen.getConstantPool();
408            final InstructionList il = methodGen.getInstructionList();
409    
410            int iteratorIndex = 0;
411            BranchHandle ifBlock = null;
412            LocalVariableGen iter, node, node2;
413            final String iteratorName = getNextFieldName();
414    
415            // Store node on the stack into a local variable
416            node = methodGen.addLocalVariable("step_pattern_tmp1", 
417                                              Util.getJCRefType(NODE_SIG),
418                                              null, null);
419            node.setStart(il.append(new ISTORE(node.getIndex())));
420    
421            // Create a new local to store the iterator
422            iter = methodGen.addLocalVariable("step_pattern_tmp2", 
423                                              Util.getJCRefType(NODE_ITERATOR_SIG),
424                                              null, null);
425    
426            // Add a new private field if this is the main class
427            if (!classGen.isExternal()) {
428                final Field iterator =
429                    new Field(ACC_PRIVATE, 
430                              cpg.addUtf8(iteratorName),
431                              cpg.addUtf8(NODE_ITERATOR_SIG),
432                              null, cpg.getConstantPool());
433                classGen.addField(iterator);
434                iteratorIndex = cpg.addFieldref(classGen.getClassName(), 
435                                                iteratorName,
436                                                NODE_ITERATOR_SIG);
437    
438                il.append(classGen.loadTranslet());
439                il.append(new GETFIELD(iteratorIndex));
440                il.append(DUP);
441                iter.setStart(il.append(new ASTORE(iter.getIndex())));
442                ifBlock = il.append(new IFNONNULL(null));
443                il.append(classGen.loadTranslet());
444            }       
445    
446            // Compile the step created at type checking time
447            _step.translate(classGen, methodGen);
448            InstructionHandle iterStore = il.append(new ASTORE(iter.getIndex()));
449    
450            // If in the main class update the field too
451            if (!classGen.isExternal()) {
452                il.append(new ALOAD(iter.getIndex()));
453                il.append(new PUTFIELD(iteratorIndex));
454                ifBlock.setTarget(il.append(NOP));
455            } else {
456                // If class is not external, start of range for iter variable was
457                // set above
458                iter.setStart(iterStore);       
459            }
460    
461            // Get the parent of the node on the stack
462            il.append(methodGen.loadDOM());
463            il.append(new ILOAD(node.getIndex()));
464            int index = cpg.addInterfaceMethodref(DOM_INTF,
465                                                  GET_PARENT, GET_PARENT_SIG);
466            il.append(new INVOKEINTERFACE(index, 2));
467    
468            // Initialize the iterator with the parent
469            il.append(new ALOAD(iter.getIndex()));
470            il.append(SWAP);
471            il.append(methodGen.setStartNode());
472    
473            /* 
474             * Inline loop:
475             *
476             * int node2;
477             * while ((node2 = iter.next()) != NodeIterator.END 
478             *                && node2 < node);
479             * return node2 == node; 
480             */
481            BranchHandle skipNext;
482            InstructionHandle begin, next;
483            node2 = methodGen.addLocalVariable("step_pattern_tmp3", 
484                                               Util.getJCRefType(NODE_SIG),
485                                               null, null);
486    
487            skipNext = il.append(new GOTO(null));
488            next = il.append(new ALOAD(iter.getIndex()));
489            node2.setStart(next);
490            begin = il.append(methodGen.nextNode());
491            il.append(DUP);
492            il.append(new ISTORE(node2.getIndex()));
493            _falseList.add(il.append(new IFLT(null)));      // NodeIterator.END
494    
495            il.append(new ILOAD(node2.getIndex()));
496            il.append(new ILOAD(node.getIndex()));
497            iter.setEnd(il.append(new IF_ICMPLT(next)));
498    
499            node2.setEnd(il.append(new ILOAD(node2.getIndex())));
500            node.setEnd(il.append(new ILOAD(node.getIndex())));
501            _falseList.add(il.append(new IF_ICMPNE(null)));
502    
503            skipNext.setTarget(begin);
504        }
505            
506        public void translate(ClassGenerator classGen, MethodGenerator methodGen) {
507            final ConstantPoolGen cpg = classGen.getConstantPool();
508            final InstructionList il = methodGen.getInstructionList();
509    
510            if (hasPredicates()) {
511                switch (_contextCase) {
512                case NO_CONTEXT:
513                    translateNoContext(classGen, methodGen);
514                    break;
515                    
516                case SIMPLE_CONTEXT:
517                    translateSimpleContext(classGen, methodGen);
518                    break;
519                    
520                default:
521                    translateGeneralContext(classGen, methodGen);
522                    break;
523                }
524            }
525            else if (isWildcard()) {
526                il.append(POP);     // true list falls through
527            }
528            else {
529                translateKernel(classGen, methodGen);
530            }
531        }
532    }