View Javadoc
1   /*
2    * reserved comment block
3    * DO NOT REMOVE OR ALTER!
4    */
5   /*
6    * Copyright 2001-2004 The Apache Software Foundation.
7    *
8    * Licensed under the Apache License, Version 2.0 (the "License");
9    * you may not use this file except in compliance with the License.
10   * You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  /*
21   * $Id: StepPattern.java,v 1.2.4.1 2005/09/12 11:13:19 pvedula Exp $
22   */
23  
24  package com.sun.org.apache.xalan.internal.xsltc.compiler;
25  
26  import java.util.Vector;
27  
28  import com.sun.org.apache.bcel.internal.classfile.Field;
29  import com.sun.org.apache.bcel.internal.generic.ALOAD;
30  import com.sun.org.apache.bcel.internal.generic.ASTORE;
31  import com.sun.org.apache.bcel.internal.generic.BranchHandle;
32  import com.sun.org.apache.bcel.internal.generic.ConstantPoolGen;
33  import com.sun.org.apache.bcel.internal.generic.GETFIELD;
34  import com.sun.org.apache.bcel.internal.generic.GOTO;
35  import com.sun.org.apache.bcel.internal.generic.GOTO_W;
36  import com.sun.org.apache.bcel.internal.generic.IFLT;
37  import com.sun.org.apache.bcel.internal.generic.IFNE;
38  import com.sun.org.apache.bcel.internal.generic.IFNONNULL;
39  import com.sun.org.apache.bcel.internal.generic.IF_ICMPEQ;
40  import com.sun.org.apache.bcel.internal.generic.IF_ICMPLT;
41  import com.sun.org.apache.bcel.internal.generic.IF_ICMPNE;
42  import com.sun.org.apache.bcel.internal.generic.ILOAD;
43  import com.sun.org.apache.bcel.internal.generic.INVOKEINTERFACE;
44  import com.sun.org.apache.bcel.internal.generic.INVOKESPECIAL;
45  import com.sun.org.apache.bcel.internal.generic.ISTORE;
46  import com.sun.org.apache.bcel.internal.generic.InstructionHandle;
47  import com.sun.org.apache.bcel.internal.generic.InstructionList;
48  import com.sun.org.apache.bcel.internal.generic.LocalVariableGen;
49  import com.sun.org.apache.bcel.internal.generic.NEW;
50  import com.sun.org.apache.bcel.internal.generic.PUSH;
51  import com.sun.org.apache.bcel.internal.generic.PUTFIELD;
52  import com.sun.org.apache.xalan.internal.xsltc.compiler.util.ClassGenerator;
53  import com.sun.org.apache.xalan.internal.xsltc.compiler.util.MethodGenerator;
54  import com.sun.org.apache.xalan.internal.xsltc.compiler.util.Type;
55  import com.sun.org.apache.xalan.internal.xsltc.compiler.util.TypeCheckError;
56  import com.sun.org.apache.xalan.internal.xsltc.compiler.util.Util;
57  import com.sun.org.apache.xml.internal.dtm.Axis;
58  import com.sun.org.apache.xml.internal.dtm.DTM;
59  
60  /**
61   * @author Jacek Ambroziak
62   * @author Santiago Pericas-Geertsen
63   * @author Erwin Bolwidt <ejb@klomp.org>
64   */
65  class StepPattern extends RelativePathPattern {
66  
67      private static final int NO_CONTEXT = 0;
68      private static final int SIMPLE_CONTEXT = 1;
69      private static final int GENERAL_CONTEXT = 2;
70  
71      protected final int _axis;
72      protected final int _nodeType;
73      protected Vector _predicates;
74  
75      private Step    _step = null;
76      private boolean _isEpsilon = false;
77      private int     _contextCase;
78  
79      private double  _priority = Double.MAX_VALUE;
80  
81      public StepPattern(int axis, int nodeType, Vector predicates) {
82          _axis = axis;
83          _nodeType = nodeType;
84          _predicates = predicates;
85      }
86  
87      public void setParser(Parser parser) {
88          super.setParser(parser);
89          if (_predicates != null) {
90              final int n = _predicates.size();
91              for (int i = 0; i < n; i++) {
92                  final Predicate exp = (Predicate)_predicates.elementAt(i);
93                  exp.setParser(parser);
94                  exp.setParent(this);
95              }
96          }
97      }
98  
99      public int getNodeType() {
100         return _nodeType;
101     }
102 
103     public void setPriority(double priority) {
104         _priority = priority;
105     }
106 
107     public StepPattern getKernelPattern() {
108         return this;
109     }
110 
111     public boolean isWildcard() {
112         return _isEpsilon && hasPredicates() == false;
113     }
114 
115     public StepPattern setPredicates(Vector predicates) {
116         _predicates = predicates;
117         return(this);
118     }
119 
120     protected boolean hasPredicates() {
121         return _predicates != null && _predicates.size() > 0;
122     }
123 
124     public double getDefaultPriority() {
125         if (_priority != Double.MAX_VALUE) {
126             return _priority;
127         }
128 
129         if (hasPredicates()) {
130             return 0.5;
131         }
132         else {
133             switch(_nodeType) {
134             case -1:
135                 return -0.5;    // node()
136             case 0:
137                 return 0.0;
138             default:
139                 return (_nodeType >= NodeTest.GTYPE) ? 0.0 : -0.5;
140             }
141         }
142     }
143 
144     public int getAxis() {
145         return _axis;
146     }
147 
148     public void reduceKernelPattern() {
149         _isEpsilon = true;
150     }
151 
152     public String toString() {
153         final StringBuffer buffer = new StringBuffer("stepPattern(\"");
154     buffer.append(Axis.getNames(_axis))
155             .append("\", ")
156             .append(_isEpsilon ?
157                         ("epsilon{" + Integer.toString(_nodeType) + "}") :
158                          Integer.toString(_nodeType));
159         if (_predicates != null)
160             buffer.append(", ").append(_predicates.toString());
161         return buffer.append(')').toString();
162     }
163 
164     private int analyzeCases() {
165         boolean noContext = true;
166         final int n = _predicates.size();
167 
168         for (int i = 0; i < n && noContext; i++) {
169             Predicate pred = (Predicate) _predicates.elementAt(i);
170             if (pred.isNthPositionFilter() ||
171                 pred.hasPositionCall() ||
172                 pred.hasLastCall())
173             {
174                 noContext = false;
175             }
176         }
177 
178         if (noContext) {
179             return NO_CONTEXT;
180         }
181         else if (n == 1) {
182             return SIMPLE_CONTEXT;
183         }
184         return GENERAL_CONTEXT;
185     }
186 
187     private String getNextFieldName() {
188         return  "__step_pattern_iter_" + getXSLTC().nextStepPatternSerial();
189     }
190 
191     public Type typeCheck(SymbolTable stable) throws TypeCheckError {
192         if (hasPredicates()) {
193             // Type check all the predicates (e -> position() = e)
194             final int n = _predicates.size();
195             for (int i = 0; i < n; i++) {
196                 final Predicate pred = (Predicate)_predicates.elementAt(i);
197                 pred.typeCheck(stable);
198             }
199 
200             // Analyze context cases
201             _contextCase = analyzeCases();
202 
203             Step step = null;
204 
205             // Create an instance of Step to do the translation
206             if (_contextCase == SIMPLE_CONTEXT) {
207                 Predicate pred = (Predicate)_predicates.elementAt(0);
208                 if (pred.isNthPositionFilter()) {
209                     _contextCase = GENERAL_CONTEXT;
210                     step = new Step(_axis, _nodeType, _predicates);
211                 } else {
212                     step = new Step(_axis, _nodeType, null);
213                 }
214             } else if (_contextCase == GENERAL_CONTEXT) {
215                 final int len = _predicates.size();
216                 for (int i = 0; i < len; i++) {
217                     ((Predicate)_predicates.elementAt(i)).dontOptimize();
218                 }
219 
220                 step = new Step(_axis, _nodeType, _predicates);
221             }
222 
223             if (step != null) {
224                 step.setParser(getParser());
225                 step.typeCheck(stable);
226                 _step = step;
227             }
228         }
229         return _axis == Axis.CHILD ? Type.Element : Type.Attribute;
230     }
231 
232     private void translateKernel(ClassGenerator classGen,
233                                  MethodGenerator methodGen) {
234         final ConstantPoolGen cpg = classGen.getConstantPool();
235         final InstructionList il = methodGen.getInstructionList();
236 
237         if (_nodeType == DTM.ELEMENT_NODE) {
238             final int check = cpg.addInterfaceMethodref(DOM_INTF,
239                                                         "isElement", "(I)Z");
240             il.append(methodGen.loadDOM());
241             il.append(SWAP);
242             il.append(new INVOKEINTERFACE(check, 2));
243 
244             // Need to allow for long jumps here
245             final BranchHandle icmp = il.append(new IFNE(null));
246             _falseList.add(il.append(new GOTO_W(null)));
247             icmp.setTarget(il.append(NOP));
248         }
249         else if (_nodeType == DTM.ATTRIBUTE_NODE) {
250             final int check = cpg.addInterfaceMethodref(DOM_INTF,
251                                                         "isAttribute", "(I)Z");
252             il.append(methodGen.loadDOM());
253             il.append(SWAP);
254             il.append(new INVOKEINTERFACE(check, 2));
255 
256             // Need to allow for long jumps here
257             final BranchHandle icmp = il.append(new IFNE(null));
258             _falseList.add(il.append(new GOTO_W(null)));
259             icmp.setTarget(il.append(NOP));
260         }
261         else {
262             // context node is on the stack
263             final int getEType = cpg.addInterfaceMethodref(DOM_INTF,
264                                                           "getExpandedTypeID",
265                                                           "(I)I");
266             il.append(methodGen.loadDOM());
267             il.append(SWAP);
268             il.append(new INVOKEINTERFACE(getEType, 2));
269             il.append(new PUSH(cpg, _nodeType));
270 
271             // Need to allow for long jumps here
272             final BranchHandle icmp = il.append(new IF_ICMPEQ(null));
273             _falseList.add(il.append(new GOTO_W(null)));
274             icmp.setTarget(il.append(NOP));
275         }
276     }
277 
278     private void translateNoContext(ClassGenerator classGen,
279                                     MethodGenerator methodGen) {
280         final ConstantPoolGen cpg = classGen.getConstantPool();
281         final InstructionList il = methodGen.getInstructionList();
282 
283         // Push current node on the stack
284         il.append(methodGen.loadCurrentNode());
285         il.append(SWAP);
286 
287         // Overwrite current node with matching node
288         il.append(methodGen.storeCurrentNode());
289 
290         // If pattern not reduced then check kernel
291         if (!_isEpsilon) {
292             il.append(methodGen.loadCurrentNode());
293             translateKernel(classGen, methodGen);
294         }
295 
296         // Compile the expressions within the predicates
297         final int n = _predicates.size();
298         for (int i = 0; i < n; i++) {
299             Predicate pred = (Predicate)_predicates.elementAt(i);
300             Expression exp = pred.getExpr();
301             exp.translateDesynthesized(classGen, methodGen);
302             _trueList.append(exp._trueList);
303             _falseList.append(exp._falseList);
304         }
305 
306         // Backpatch true list and restore current iterator/node
307         InstructionHandle restore;
308         restore = il.append(methodGen.storeCurrentNode());
309         backPatchTrueList(restore);
310         BranchHandle skipFalse = il.append(new GOTO(null));
311 
312         // Backpatch false list and restore current iterator/node
313         restore = il.append(methodGen.storeCurrentNode());
314         backPatchFalseList(restore);
315         _falseList.add(il.append(new GOTO(null)));
316 
317         // True list falls through
318         skipFalse.setTarget(il.append(NOP));
319     }
320 
321     private void translateSimpleContext(ClassGenerator classGen,
322                                         MethodGenerator methodGen) {
323         int index;
324         final ConstantPoolGen cpg = classGen.getConstantPool();
325         final InstructionList il = methodGen.getInstructionList();
326 
327         // Store matching node into a local variable
328         LocalVariableGen match;
329         match = methodGen.addLocalVariable("step_pattern_tmp1",
330                                            Util.getJCRefType(NODE_SIG),
331                                            null, null);
332         match.setStart(il.append(new ISTORE(match.getIndex())));
333 
334         // If pattern not reduced then check kernel
335         if (!_isEpsilon) {
336             il.append(new ILOAD(match.getIndex()));
337             translateKernel(classGen, methodGen);
338         }
339 
340         // Push current iterator and current node on the stack
341         il.append(methodGen.loadCurrentNode());
342         il.append(methodGen.loadIterator());
343 
344         // Create a new matching iterator using the matching node
345         index = cpg.addMethodref(MATCHING_ITERATOR, "<init>",
346                                  "(I" + NODE_ITERATOR_SIG + ")V");
347 
348         // Backwards branches are prohibited if an uninitialized object is
349         // on the stack by section 4.9.4 of the JVM Specification, 2nd Ed.
350         // We don't know whether this code might contain backwards branches,
351         // so we mustn't create the new object until after we've created
352         // the suspect arguments to its constructor.  Instead we calculate
353         // the values of the arguments to the constructor first, store them
354         // in temporary variables, create the object and reload the
355         // arguments from the temporaries to avoid the problem.
356 
357         _step.translate(classGen, methodGen);
358         LocalVariableGen stepIteratorTemp =
359                 methodGen.addLocalVariable("step_pattern_tmp2",
360                                            Util.getJCRefType(NODE_ITERATOR_SIG),
361                                            null, null);
362         stepIteratorTemp.setStart(
363                 il.append(new ASTORE(stepIteratorTemp.getIndex())));
364 
365         il.append(new NEW(cpg.addClass(MATCHING_ITERATOR)));
366         il.append(DUP);
367         il.append(new ILOAD(match.getIndex()));
368         stepIteratorTemp.setEnd(
369                 il.append(new ALOAD(stepIteratorTemp.getIndex())));
370         il.append(new INVOKESPECIAL(index));
371 
372         // Get the parent of the matching node
373         il.append(methodGen.loadDOM());
374         il.append(new ILOAD(match.getIndex()));
375         index = cpg.addInterfaceMethodref(DOM_INTF, GET_PARENT, GET_PARENT_SIG);
376         il.append(new INVOKEINTERFACE(index, 2));
377 
378         // Start the iterator with the parent
379         il.append(methodGen.setStartNode());
380 
381         // Overwrite current iterator and current node
382         il.append(methodGen.storeIterator());
383         match.setEnd(il.append(new ILOAD(match.getIndex())));
384         il.append(methodGen.storeCurrentNode());
385 
386         // Translate the expression of the predicate
387         Predicate pred = (Predicate) _predicates.elementAt(0);
388         Expression exp = pred.getExpr();
389         exp.translateDesynthesized(classGen, methodGen);
390 
391         // Backpatch true list and restore current iterator/node
392         InstructionHandle restore = il.append(methodGen.storeIterator());
393         il.append(methodGen.storeCurrentNode());
394         exp.backPatchTrueList(restore);
395         BranchHandle skipFalse = il.append(new GOTO(null));
396 
397         // Backpatch false list and restore current iterator/node
398         restore = il.append(methodGen.storeIterator());
399         il.append(methodGen.storeCurrentNode());
400         exp.backPatchFalseList(restore);
401         _falseList.add(il.append(new GOTO(null)));
402 
403         // True list falls through
404         skipFalse.setTarget(il.append(NOP));
405     }
406 
407     private void translateGeneralContext(ClassGenerator classGen,
408                                          MethodGenerator methodGen) {
409         final ConstantPoolGen cpg = classGen.getConstantPool();
410         final InstructionList il = methodGen.getInstructionList();
411 
412         int iteratorIndex = 0;
413         BranchHandle ifBlock = null;
414         LocalVariableGen iter, node, node2;
415         final String iteratorName = getNextFieldName();
416 
417         // Store node on the stack into a local variable
418         node = methodGen.addLocalVariable("step_pattern_tmp1",
419                                           Util.getJCRefType(NODE_SIG),
420                                           null, null);
421         node.setStart(il.append(new ISTORE(node.getIndex())));
422 
423         // Create a new local to store the iterator
424         iter = methodGen.addLocalVariable("step_pattern_tmp2",
425                                           Util.getJCRefType(NODE_ITERATOR_SIG),
426                                           null, null);
427 
428         // Add a new private field if this is the main class
429         if (!classGen.isExternal()) {
430             final Field iterator =
431                 new Field(ACC_PRIVATE,
432                           cpg.addUtf8(iteratorName),
433                           cpg.addUtf8(NODE_ITERATOR_SIG),
434                           null, cpg.getConstantPool());
435             classGen.addField(iterator);
436             iteratorIndex = cpg.addFieldref(classGen.getClassName(),
437                                             iteratorName,
438                                             NODE_ITERATOR_SIG);
439 
440             il.append(classGen.loadTranslet());
441             il.append(new GETFIELD(iteratorIndex));
442             il.append(DUP);
443             iter.setStart(il.append(new ASTORE(iter.getIndex())));
444             ifBlock = il.append(new IFNONNULL(null));
445             il.append(classGen.loadTranslet());
446         }
447 
448         // Compile the step created at type checking time
449         _step.translate(classGen, methodGen);
450         InstructionHandle iterStore = il.append(new ASTORE(iter.getIndex()));
451 
452         // If in the main class update the field too
453         if (!classGen.isExternal()) {
454             il.append(new ALOAD(iter.getIndex()));
455             il.append(new PUTFIELD(iteratorIndex));
456             ifBlock.setTarget(il.append(NOP));
457         } else {
458             // If class is not external, start of range for iter variable was
459             // set above
460             iter.setStart(iterStore);
461         }
462 
463         // Get the parent of the node on the stack
464         il.append(methodGen.loadDOM());
465         il.append(new ILOAD(node.getIndex()));
466         int index = cpg.addInterfaceMethodref(DOM_INTF,
467                                               GET_PARENT, GET_PARENT_SIG);
468         il.append(new INVOKEINTERFACE(index, 2));
469 
470         // Initialize the iterator with the parent
471         il.append(new ALOAD(iter.getIndex()));
472         il.append(SWAP);
473         il.append(methodGen.setStartNode());
474 
475         /*
476          * Inline loop:
477          *
478          * int node2;
479          * while ((node2 = iter.next()) != NodeIterator.END
480          *                && node2 < node);
481          * return node2 == node;
482          */
483         BranchHandle skipNext;
484         InstructionHandle begin, next;
485         node2 = methodGen.addLocalVariable("step_pattern_tmp3",
486                                            Util.getJCRefType(NODE_SIG),
487                                            null, null);
488 
489         skipNext = il.append(new GOTO(null));
490         next = il.append(new ALOAD(iter.getIndex()));
491         node2.setStart(next);
492         begin = il.append(methodGen.nextNode());
493         il.append(DUP);
494         il.append(new ISTORE(node2.getIndex()));
495         _falseList.add(il.append(new IFLT(null)));      // NodeIterator.END
496 
497         il.append(new ILOAD(node2.getIndex()));
498         il.append(new ILOAD(node.getIndex()));
499         iter.setEnd(il.append(new IF_ICMPLT(next)));
500 
501         node2.setEnd(il.append(new ILOAD(node2.getIndex())));
502         node.setEnd(il.append(new ILOAD(node.getIndex())));
503         _falseList.add(il.append(new IF_ICMPNE(null)));
504 
505         skipNext.setTarget(begin);
506     }
507 
508     public void translate(ClassGenerator classGen, MethodGenerator methodGen) {
509         final ConstantPoolGen cpg = classGen.getConstantPool();
510         final InstructionList il = methodGen.getInstructionList();
511 
512         if (hasPredicates()) {
513             switch (_contextCase) {
514             case NO_CONTEXT:
515                 translateNoContext(classGen, methodGen);
516                 break;
517 
518             case SIMPLE_CONTEXT:
519                 translateSimpleContext(classGen, methodGen);
520                 break;
521 
522             default:
523                 translateGeneralContext(classGen, methodGen);
524                 break;
525             }
526         }
527         else if (isWildcard()) {
528             il.append(POP);     // true list falls through
529         }
530         else {
531             translateKernel(classGen, methodGen);
532         }
533     }
534 }