KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > jdt > internal > compiler > ast > CombinedBinaryExpression


1 /*******************************************************************************
2  * Copyright (c) 2006 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.jdt.internal.compiler.ast;
12
13 import org.eclipse.jdt.internal.compiler.ASTVisitor;
14 import org.eclipse.jdt.internal.compiler.codegen.CodeStream;
15 import org.eclipse.jdt.internal.compiler.flow.FlowContext;
16 import org.eclipse.jdt.internal.compiler.flow.FlowInfo;
17 import org.eclipse.jdt.internal.compiler.impl.Constant;
18 import org.eclipse.jdt.internal.compiler.lookup.BlockScope;
19 import org.eclipse.jdt.internal.compiler.lookup.TypeBinding;
20 import org.eclipse.jdt.internal.compiler.lookup.TypeIds;
21
22 /**
23  * CombinedBinaryExpression is an implementation of BinaryExpression that
24  * specifically attempts to mitigate the issues raised by expressions which
25  * have a very deep leftmost branch. It does so by maintaining a table of
26  * direct references to its subexpressions, and implementing non-recursive
27  * variants of the most significant recursive algorithms of its ancestors.
28  * The subexpressions table only holds intermediate binary expressions. Its
29  * role is to provide the reversed navigation through the left relationship
30  * of BinaryExpression to Expression. To cope with potentially very deep
31  * left branches, an instance of CombinedBinaryExpression is created once in
32  * a while, using variable thresholds held by {@link #arityMax}.
33  * As a specific case, the topmost node of all binary expressions that are
34  * deeper than one is a CombinedBinaryExpression, but it has no references
35  * table.<br>
36  * Notes:
37  * <ul>
38  * <li>CombinedBinaryExpression is not meant to behave in other ways than
39  * BinaryExpression in any observable respect;</li>
40  * <li>visitors that implement their own traversal upon binary expressions
41  * should consider taking advantage of combined binary expressions, or
42  * else face a risk of StackOverflowError upon deep instances;</li>
43  * <li>callers that need to change the operator should rebuild the expression
44  * from scratch, or else amend the references table as needed to cope with
45  * the resulting, separated expressions.</li>
46  * </ul>
47  */
48 public class CombinedBinaryExpression extends BinaryExpression {
49
50     /**
51      * The number of consecutive binary expressions of this' left branch that
52      * bear the same operator as this.<br>
53      * Notes:
54      * <ul><li>the presence of a CombinedBinaryExpression instance resets
55      * arity, even when its operator is compatible;</li>
56      * <li>this property is maintained by the parser.</li>
57      * </ul>
58      */
59     public int arity;
60     
61     /**
62      * The threshold that will trigger the creation of the next full-fledged
63      * CombinedBinaryExpression. This field is only maintained for the
64      * topmost binary expression (it is 0 otherwise). It enables a variable
65      * policy, which scales better with very large expressions.
66      */
67     public int arityMax;
68     
69     /**
70      * Upper limit for {@link #arityMax}.
71      */
72     public static final int ARITY_MAX_MAX = 160;
73     
74     /**
75      * Default lower limit for {@link #arityMax}.
76      */
77     public static final int ARITY_MAX_MIN = 20;
78     
79     /**
80      * Default value for the first term of the series of {@link #arityMax}
81      * values. Changing this allows for experimentation. Not meant to be
82      * changed during a parse operation.
83      */
84     public static int defaultArityMaxStartingValue = ARITY_MAX_MIN;
85     
86     /**
87      * A table of references to the binary expressions of this' left branch.
88      * Instances of CombinedBinaryExpression are not repeated here. Instead,
89      * the left subexpression of referencesTable[0] may be a combined binary
90      * expression, if appropriate. Null when this only cares about tracking
91      * the expression's arity.
92      */
93     public BinaryExpression referencesTable[];
94
95 /**
96  * Make a new CombinedBinaryExpression. If arity is strictly greater than one,
97  * a references table is built and initialized with the reverse relationship of
98  * the one defined by {@link BinaryExpression#left}. arity and left must be
99  * compatible with each other (that is, there must be at least arity - 1
100  * consecutive compatible binary expressions into the leftmost branch of left,
101  * the topmost of which being left's immediate left expression).
102  * @param left the left branch expression
103  * @param right the right branch expression
104  * @param operator the operator for this binary expression - only PLUS for now
105  * @param arity the number of binary expressions of a compatible operator that
106  * already exist into the leftmost branch of left (including left); must
107  * be strictly greater than 0
108  */
109 public CombinedBinaryExpression(Expression left, Expression right, int operator,
110         int arity) {
111     super(left, right, operator);
112     this.arity = arity;
113     if (arity > 1) {
114         this.referencesTable = new BinaryExpression[arity];
115         this.referencesTable[arity - 1] = (BinaryExpression) left;
116         for (int i = arity - 1; i > 0; i--) {
117             this.referencesTable[i - 1] =
118                 (BinaryExpression) this.referencesTable[i].left;
119         }
120     } else {
121         this.arityMax = defaultArityMaxStartingValue;
122     }
123 }
124
125 public FlowInfo analyseCode(BlockScope currentScope, FlowContext flowContext,
126         FlowInfo flowInfo) {
127     // keep implementation in sync with BinaryExpression#analyseCode
128 if (this.referencesTable == null) {
129         return super.analyseCode(currentScope, flowContext, flowInfo);
130     }
131     BinaryExpression cursor;
132     if ((cursor = this.referencesTable[0]).resolvedType.id !=
133             TypeIds.T_JavaLangString) {
134         cursor.left.checkNPE(currentScope, flowContext, flowInfo);
135     }
136     flowInfo = cursor.left.analyseCode(currentScope, flowContext, flowInfo).
137         unconditionalInits();
138     for (int i = 0, end = this.arity; i < end; i ++) {
139         if ((cursor = this.referencesTable[i]).resolvedType.id !=
140                 TypeIds.T_JavaLangString) {
141             cursor.right.checkNPE(currentScope, flowContext, flowInfo);
142         }
143         flowInfo = cursor.right.
144             analyseCode(currentScope, flowContext, flowInfo).
145                 unconditionalInits();
146     }
147     if (this.resolvedType.id != TypeIds.T_JavaLangString) {
148         this.right.checkNPE(currentScope, flowContext, flowInfo);
149     }
150     return this.right.analyseCode(currentScope, flowContext, flowInfo).
151         unconditionalInits();
152 }
153
154 public void generateOptimizedStringConcatenation(BlockScope blockScope,
155         CodeStream codeStream, int typeID) {
156     // keep implementation in sync with BinaryExpression and Expression
157 // #generateOptimizedStringConcatenation
158 if (this.referencesTable == null) {
159         super.generateOptimizedStringConcatenation(blockScope, codeStream,
160             typeID);
161     } else {
162         if ((((this.bits & ASTNode.OperatorMASK) >> ASTNode.OperatorSHIFT) ==
163                 OperatorIds.PLUS)
164             && ((this.bits & ASTNode.ReturnTypeIDMASK) == TypeIds.T_JavaLangString)) {
165             if (this.constant != Constant.NotAConstant) {
166                 codeStream.generateConstant(this.constant, this.implicitConversion);
167                 codeStream.invokeStringConcatenationAppendForType(
168                         this.implicitConversion & TypeIds.COMPILE_TYPE_MASK);
169             } else {
170                 BinaryExpression cursor = this.referencesTable[0];
171         
172                 int restart = 0;
173     // int cursorTypeID;
174 int pc = codeStream.position;
175                 for (restart = this.arity - 1; restart >= 0; restart--) {
176                     if ((cursor = this.referencesTable[restart]).constant !=
177                             Constant.NotAConstant) {
178                         codeStream.generateConstant(cursor.constant,
179                             cursor.implicitConversion);
180                         codeStream.invokeStringConcatenationAppendForType(
181                             cursor.implicitConversion & TypeIds.COMPILE_TYPE_MASK);
182                         break;
183                     }
184                     // never happens for now - may reconsider if we decide to
185 // cover more than string concatenation
186 // if (!((((cursor = this.referencesTable[restart]).bits &
187 // ASTNode.OperatorMASK) >> ASTNode.OperatorSHIFT) ==
188 // OperatorIds.PLUS) &
189 // ((cursorTypeID = cursor.bits & ASTNode.ReturnTypeIDMASK) ==
190 // TypeIds.T_JavaLangString)) {
191 // if (cursorTypeID == T_JavaLangString &&
192 // cursor.constant != Constant.NotAConstant &&
193 // cursor.constant.stringValue().length() == 0) {
194 // break; // optimize str + ""
195 // }
196 // cursor.generateCode(blockScope, codeStream, true);
197 // codeStream.invokeStringConcatenationAppendForType(
198 // cursorTypeID);
199 // break;
200 // }
201 }
202                 restart++;
203                 if (restart == 0) { // reached the leftmost expression
204 cursor.left.generateOptimizedStringConcatenation(
205                         blockScope,
206                         codeStream,
207                         cursor.left.implicitConversion & TypeIds.COMPILE_TYPE_MASK);
208                 }
209                 int pcAux;
210                 for (int i = restart; i < this.arity; i++) {
211                     codeStream.recordPositionsFrom(pc,
212                         (cursor = this.referencesTable[i]).left.sourceStart);
213                     pcAux = codeStream.position;
214                     cursor.right.generateOptimizedStringConcatenation(blockScope,
215                         codeStream, cursor.right.implicitConversion &
216                             TypeIds.COMPILE_TYPE_MASK);
217                     codeStream.recordPositionsFrom(pcAux, cursor.right.sourceStart);
218                 }
219                 codeStream.recordPositionsFrom(pc, this.left.sourceStart);
220                 pc = codeStream.position;
221                 this.right.generateOptimizedStringConcatenation(
222                     blockScope,
223                     codeStream,
224                     this.right.implicitConversion & TypeIds.COMPILE_TYPE_MASK);
225                 codeStream.recordPositionsFrom(pc, this.right.sourceStart);
226             }
227         } else {
228             super.generateOptimizedStringConcatenation(blockScope, codeStream,
229                 typeID);
230         }
231     }
232 }
233
234 public void generateOptimizedStringConcatenationCreation(BlockScope blockScope,
235         CodeStream codeStream, int typeID) {
236     // keep implementation in sync with BinaryExpression
237 // #generateOptimizedStringConcatenationCreation
238 if (this.referencesTable == null) {
239         super.generateOptimizedStringConcatenationCreation(blockScope,
240             codeStream, typeID);
241     } else {
242         if ((((this.bits & ASTNode.OperatorMASK) >> ASTNode.OperatorSHIFT) ==
243                 OperatorIds.PLUS) &&
244                     ((this.bits & ASTNode.ReturnTypeIDMASK) ==
245                         TypeIds.T_JavaLangString) &&
246                     this.constant == Constant.NotAConstant) {
247             int pc = codeStream.position;
248             BinaryExpression cursor = this.referencesTable[this.arity - 1];
249                 // silence warnings
250 int restart = 0;
251             for (restart = this.arity - 1; restart >= 0; restart--) {
252                 if (((((cursor = this.referencesTable[restart]).bits &
253                         ASTNode.OperatorMASK) >> ASTNode.OperatorSHIFT) ==
254                             OperatorIds.PLUS) &&
255                         ((cursor.bits & ASTNode.ReturnTypeIDMASK) ==
256                             TypeIds.T_JavaLangString)) {
257                     if (cursor.constant != Constant.NotAConstant) {
258                         codeStream.newStringContatenation(); // new: java.lang.StringBuffer
259 codeStream.dup();
260                         codeStream.ldc(cursor.constant.stringValue());
261                         codeStream.invokeStringConcatenationStringConstructor();
262                         // invokespecial: java.lang.StringBuffer.<init>(Ljava.lang.String;)V
263 break;
264                     }
265                 } else {
266                     cursor.generateOptimizedStringConcatenationCreation(blockScope,
267                         codeStream, cursor.implicitConversion &
268                             TypeIds.COMPILE_TYPE_MASK);
269                     break;
270                 }
271             }
272             restart++;
273             if (restart == 0) { // reached the leftmost expression
274 cursor.left.generateOptimizedStringConcatenationCreation(
275                     blockScope,
276                     codeStream,
277                     cursor.left.implicitConversion & TypeIds.COMPILE_TYPE_MASK);
278             }
279             int pcAux;
280             for (int i = restart; i < this.arity; i++) {
281                 codeStream.recordPositionsFrom(pc,
282                     (cursor = this.referencesTable[i]).left.sourceStart);
283                 pcAux = codeStream.position;
284                 cursor.right.generateOptimizedStringConcatenation(blockScope,
285                     codeStream, cursor.right.implicitConversion &
286                         TypeIds.COMPILE_TYPE_MASK);
287                 codeStream.recordPositionsFrom(pcAux, cursor.right.sourceStart);
288             }
289             codeStream.recordPositionsFrom(pc, this.left.sourceStart);
290             pc = codeStream.position;
291             this.right.generateOptimizedStringConcatenation(
292                 blockScope,
293                 codeStream,
294                 this.right.implicitConversion & TypeIds.COMPILE_TYPE_MASK);
295             codeStream.recordPositionsFrom(pc, this.right.sourceStart);
296         } else {
297             super.generateOptimizedStringConcatenationCreation(blockScope,
298                 codeStream, typeID);
299         }
300     }
301 }
302
303 public StringBuffer JavaDoc printExpressionNoParenthesis(int indent,
304         StringBuffer JavaDoc output) {
305     // keep implementation in sync with
306 // BinaryExpression#printExpressionNoParenthesis and
307 // OperatorExpression#printExpression
308 if (this.referencesTable == null) {
309         return super.printExpressionNoParenthesis(indent, output);
310     }
311     String JavaDoc operatorString = operatorToString();
312     for (int i = this.arity - 1; i >= 0; i--) {
313         output.append('(');
314     }
315     output = this.referencesTable[0].left.
316         printExpression(indent, output);
317     for (int i = 0, end = this.arity;
318                 i < end; i++) {
319         output.append(' ').append(operatorString).append(' ');
320         output = this.referencesTable[i].right.
321             printExpression(0, output);
322         output.append(')');
323     }
324     output.append(' ').append(operatorString).append(' ');
325     return this.right.printExpression(0, output);
326 }
327
328 public TypeBinding resolveType(BlockScope scope) {
329     // keep implementation in sync with BinaryExpression#resolveType
330 if (this.referencesTable == null) {
331         return super.resolveType(scope);
332     }
333     BinaryExpression cursor;
334     if ((cursor = this.referencesTable[0]).left instanceof CastExpression) {
335         cursor.left.bits |= ASTNode.DisableUnnecessaryCastCheck;
336             // will check later on
337 }
338     cursor.left.resolveType(scope);
339     for (int i = 0, end = this.arity; i < end; i ++) {
340         this.referencesTable[i].nonRecursiveResolveTypeUpwards(scope);
341     }
342     nonRecursiveResolveTypeUpwards(scope);
343     return this.resolvedType;
344 }
345
346 public void traverse(ASTVisitor visitor, BlockScope scope) {
347     if (this.referencesTable == null) {
348         super.traverse(visitor, scope);
349     } else {
350         if (visitor.visit(this, scope)) {
351             int restart;
352             for (restart = this.arity - 1;
353                     restart >= 0;
354                     restart--) {
355                 if (!visitor.visit(
356                         this.referencesTable[restart], scope)) {
357                     visitor.endVisit(
358                         this.referencesTable[restart], scope);
359                     break;
360                 }
361             }
362             restart++;
363             // restart now points to the deepest BE for which
364 // visit returned true, if any
365 if (restart == 0) {
366                 this.referencesTable[0].left.traverse(visitor, scope);
367             }
368             for (int i = restart, end = this.arity;
369                         i < end; i++) {
370                 this.referencesTable[i].right.traverse(visitor, scope);
371                 visitor.endVisit(this.referencesTable[i], scope);
372             }
373             this.right.traverse(visitor, scope);
374         }
375         visitor.endVisit(this, scope);
376     }
377 }
378
379 /**
380  * Change {@link #arityMax} if and as needed. The current policy is to double
381  * arityMax each time this method is called, until it reaches
382  * {@link #ARITY_MAX_MAX}. Other policies may consider incrementing it less
383  * agressively. Call only after an appropriate value has been assigned to
384  * {@link #left}.
385  */
386 // more sophisticate increment policies would leverage the leftmost expression
387 // to hold an indication of the number of uses of a given arityMax in a row
388 public void tuneArityMax() {
389     if (this.arityMax < ARITY_MAX_MAX) {
390         this.arityMax *= 2;
391     }
392 }
393 }
394
Popular Tags