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 }