StepPattern


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