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