001: /*******************************************************************************
002: * Copyright (c) 2006 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * IBM Corporation - initial API and implementation
010: *******************************************************************************/package org.eclipse.jdt.internal.compiler.ast;
011:
012: import org.eclipse.jdt.internal.compiler.ASTVisitor;
013: import org.eclipse.jdt.internal.compiler.codegen.CodeStream;
014: import org.eclipse.jdt.internal.compiler.flow.FlowContext;
015: import org.eclipse.jdt.internal.compiler.flow.FlowInfo;
016: import org.eclipse.jdt.internal.compiler.impl.Constant;
017: import org.eclipse.jdt.internal.compiler.lookup.BlockScope;
018: import org.eclipse.jdt.internal.compiler.lookup.TypeBinding;
019: import org.eclipse.jdt.internal.compiler.lookup.TypeIds;
020:
021: /**
022: * CombinedBinaryExpression is an implementation of BinaryExpression that
023: * specifically attempts to mitigate the issues raised by expressions which
024: * have a very deep leftmost branch. It does so by maintaining a table of
025: * direct references to its subexpressions, and implementing non-recursive
026: * variants of the most significant recursive algorithms of its ancestors.
027: * The subexpressions table only holds intermediate binary expressions. Its
028: * role is to provide the reversed navigation through the left relationship
029: * of BinaryExpression to Expression. To cope with potentially very deep
030: * left branches, an instance of CombinedBinaryExpression is created once in
031: * a while, using variable thresholds held by {@link #arityMax}.
032: * As a specific case, the topmost node of all binary expressions that are
033: * deeper than one is a CombinedBinaryExpression, but it has no references
034: * table.<br>
035: * Notes:
036: * <ul>
037: * <li>CombinedBinaryExpression is not meant to behave in other ways than
038: * BinaryExpression in any observable respect;</li>
039: * <li>visitors that implement their own traversal upon binary expressions
040: * should consider taking advantage of combined binary expressions, or
041: * else face a risk of StackOverflowError upon deep instances;</li>
042: * <li>callers that need to change the operator should rebuild the expression
043: * from scratch, or else amend the references table as needed to cope with
044: * the resulting, separated expressions.</li>
045: * </ul>
046: */
047: public class CombinedBinaryExpression extends BinaryExpression {
048:
049: /**
050: * The number of consecutive binary expressions of this' left branch that
051: * bear the same operator as this.<br>
052: * Notes:
053: * <ul><li>the presence of a CombinedBinaryExpression instance resets
054: * arity, even when its operator is compatible;</li>
055: * <li>this property is maintained by the parser.</li>
056: * </ul>
057: */
058: public int arity;
059:
060: /**
061: * The threshold that will trigger the creation of the next full-fledged
062: * CombinedBinaryExpression. This field is only maintained for the
063: * topmost binary expression (it is 0 otherwise). It enables a variable
064: * policy, which scales better with very large expressions.
065: */
066: public int arityMax;
067:
068: /**
069: * Upper limit for {@link #arityMax}.
070: */
071: public static final int ARITY_MAX_MAX = 160;
072:
073: /**
074: * Default lower limit for {@link #arityMax}.
075: */
076: public static final int ARITY_MAX_MIN = 20;
077:
078: /**
079: * Default value for the first term of the series of {@link #arityMax}
080: * values. Changing this allows for experimentation. Not meant to be
081: * changed during a parse operation.
082: */
083: public static int defaultArityMaxStartingValue = ARITY_MAX_MIN;
084:
085: /**
086: * A table of references to the binary expressions of this' left branch.
087: * Instances of CombinedBinaryExpression are not repeated here. Instead,
088: * the left subexpression of referencesTable[0] may be a combined binary
089: * expression, if appropriate. Null when this only cares about tracking
090: * the expression's arity.
091: */
092: public BinaryExpression referencesTable[];
093:
094: /**
095: * Make a new CombinedBinaryExpression. If arity is strictly greater than one,
096: * a references table is built and initialized with the reverse relationship of
097: * the one defined by {@link BinaryExpression#left}. arity and left must be
098: * compatible with each other (that is, there must be at least arity - 1
099: * consecutive compatible binary expressions into the leftmost branch of left,
100: * the topmost of which being left's immediate left expression).
101: * @param left the left branch expression
102: * @param right the right branch expression
103: * @param operator the operator for this binary expression - only PLUS for now
104: * @param arity the number of binary expressions of a compatible operator that
105: * already exist into the leftmost branch of left (including left); must
106: * be strictly greater than 0
107: */
108: public CombinedBinaryExpression(Expression left, Expression right,
109: int operator, int arity) {
110: super (left, right, operator);
111: this .arity = arity;
112: if (arity > 1) {
113: this .referencesTable = new BinaryExpression[arity];
114: this .referencesTable[arity - 1] = (BinaryExpression) left;
115: for (int i = arity - 1; i > 0; i--) {
116: this .referencesTable[i - 1] = (BinaryExpression) this .referencesTable[i].left;
117: }
118: } else {
119: this .arityMax = defaultArityMaxStartingValue;
120: }
121: }
122:
123: public FlowInfo analyseCode(BlockScope currentScope,
124: FlowContext flowContext, FlowInfo flowInfo) {
125: // keep implementation in sync with BinaryExpression#analyseCode
126: if (this .referencesTable == null) {
127: return super .analyseCode(currentScope, flowContext,
128: flowInfo);
129: }
130: BinaryExpression cursor;
131: if ((cursor = this .referencesTable[0]).resolvedType.id != TypeIds.T_JavaLangString) {
132: cursor.left.checkNPE(currentScope, flowContext, flowInfo);
133: }
134: flowInfo = cursor.left.analyseCode(currentScope, flowContext,
135: flowInfo).unconditionalInits();
136: for (int i = 0, end = this .arity; i < end; i++) {
137: if ((cursor = this .referencesTable[i]).resolvedType.id != TypeIds.T_JavaLangString) {
138: cursor.right.checkNPE(currentScope, flowContext,
139: flowInfo);
140: }
141: flowInfo = cursor.right.analyseCode(currentScope,
142: flowContext, flowInfo).unconditionalInits();
143: }
144: if (this .resolvedType.id != TypeIds.T_JavaLangString) {
145: this .right.checkNPE(currentScope, flowContext, flowInfo);
146: }
147: return this .right.analyseCode(currentScope, flowContext,
148: flowInfo).unconditionalInits();
149: }
150:
151: public void generateOptimizedStringConcatenation(
152: BlockScope blockScope, CodeStream codeStream, int typeID) {
153: // keep implementation in sync with BinaryExpression and Expression
154: // #generateOptimizedStringConcatenation
155: if (this .referencesTable == null) {
156: super .generateOptimizedStringConcatenation(blockScope,
157: codeStream, typeID);
158: } else {
159: if ((((this .bits & ASTNode.OperatorMASK) >> ASTNode.OperatorSHIFT) == OperatorIds.PLUS)
160: && ((this .bits & ASTNode.ReturnTypeIDMASK) == TypeIds.T_JavaLangString)) {
161: if (this .constant != Constant.NotAConstant) {
162: codeStream.generateConstant(this .constant,
163: this .implicitConversion);
164: codeStream
165: .invokeStringConcatenationAppendForType(this .implicitConversion
166: & TypeIds.COMPILE_TYPE_MASK);
167: } else {
168: BinaryExpression cursor = this .referencesTable[0];
169:
170: int restart = 0;
171: // int cursorTypeID;
172: int pc = codeStream.position;
173: for (restart = this .arity - 1; restart >= 0; restart--) {
174: if ((cursor = this .referencesTable[restart]).constant != Constant.NotAConstant) {
175: codeStream.generateConstant(
176: cursor.constant,
177: cursor.implicitConversion);
178: codeStream
179: .invokeStringConcatenationAppendForType(cursor.implicitConversion
180: & TypeIds.COMPILE_TYPE_MASK);
181: break;
182: }
183: // never happens for now - may reconsider if we decide to
184: // cover more than string concatenation
185: // if (!((((cursor = this.referencesTable[restart]).bits &
186: // ASTNode.OperatorMASK) >> ASTNode.OperatorSHIFT) ==
187: // OperatorIds.PLUS) &
188: // ((cursorTypeID = cursor.bits & ASTNode.ReturnTypeIDMASK) ==
189: // TypeIds.T_JavaLangString)) {
190: // if (cursorTypeID == T_JavaLangString &&
191: // cursor.constant != Constant.NotAConstant &&
192: // cursor.constant.stringValue().length() == 0) {
193: // break; // optimize str + ""
194: // }
195: // cursor.generateCode(blockScope, codeStream, true);
196: // codeStream.invokeStringConcatenationAppendForType(
197: // cursorTypeID);
198: // break;
199: // }
200: }
201: restart++;
202: if (restart == 0) { // reached the leftmost expression
203: cursor.left
204: .generateOptimizedStringConcatenation(
205: blockScope,
206: codeStream,
207: cursor.left.implicitConversion
208: & TypeIds.COMPILE_TYPE_MASK);
209: }
210: int pcAux;
211: for (int i = restart; i < this .arity; i++) {
212: codeStream
213: .recordPositionsFrom(
214: pc,
215: (cursor = this .referencesTable[i]).left.sourceStart);
216: pcAux = codeStream.position;
217: cursor.right
218: .generateOptimizedStringConcatenation(
219: blockScope,
220: codeStream,
221: cursor.right.implicitConversion
222: & TypeIds.COMPILE_TYPE_MASK);
223: codeStream.recordPositionsFrom(pcAux,
224: cursor.right.sourceStart);
225: }
226: codeStream.recordPositionsFrom(pc,
227: this .left.sourceStart);
228: pc = codeStream.position;
229: this .right.generateOptimizedStringConcatenation(
230: blockScope, codeStream,
231: this .right.implicitConversion
232: & TypeIds.COMPILE_TYPE_MASK);
233: codeStream.recordPositionsFrom(pc,
234: this .right.sourceStart);
235: }
236: } else {
237: super .generateOptimizedStringConcatenation(blockScope,
238: codeStream, typeID);
239: }
240: }
241: }
242:
243: public void generateOptimizedStringConcatenationCreation(
244: BlockScope blockScope, CodeStream codeStream, int typeID) {
245: // keep implementation in sync with BinaryExpression
246: // #generateOptimizedStringConcatenationCreation
247: if (this .referencesTable == null) {
248: super .generateOptimizedStringConcatenationCreation(
249: blockScope, codeStream, typeID);
250: } else {
251: if ((((this .bits & ASTNode.OperatorMASK) >> ASTNode.OperatorSHIFT) == OperatorIds.PLUS)
252: && ((this .bits & ASTNode.ReturnTypeIDMASK) == TypeIds.T_JavaLangString)
253: && this .constant == Constant.NotAConstant) {
254: int pc = codeStream.position;
255: BinaryExpression cursor = this .referencesTable[this .arity - 1];
256: // silence warnings
257: int restart = 0;
258: for (restart = this .arity - 1; restart >= 0; restart--) {
259: if (((((cursor = this .referencesTable[restart]).bits & ASTNode.OperatorMASK) >> ASTNode.OperatorSHIFT) == OperatorIds.PLUS)
260: && ((cursor.bits & ASTNode.ReturnTypeIDMASK) == TypeIds.T_JavaLangString)) {
261: if (cursor.constant != Constant.NotAConstant) {
262: codeStream.newStringContatenation(); // new: java.lang.StringBuffer
263: codeStream.dup();
264: codeStream.ldc(cursor.constant
265: .stringValue());
266: codeStream
267: .invokeStringConcatenationStringConstructor();
268: // invokespecial: java.lang.StringBuffer.<init>(Ljava.lang.String;)V
269: break;
270: }
271: } else {
272: cursor
273: .generateOptimizedStringConcatenationCreation(
274: blockScope,
275: codeStream,
276: cursor.implicitConversion
277: & TypeIds.COMPILE_TYPE_MASK);
278: break;
279: }
280: }
281: restart++;
282: if (restart == 0) { // reached the leftmost expression
283: cursor.left
284: .generateOptimizedStringConcatenationCreation(
285: blockScope, codeStream,
286: cursor.left.implicitConversion
287: & TypeIds.COMPILE_TYPE_MASK);
288: }
289: int pcAux;
290: for (int i = restart; i < this .arity; i++) {
291: codeStream
292: .recordPositionsFrom(
293: pc,
294: (cursor = this .referencesTable[i]).left.sourceStart);
295: pcAux = codeStream.position;
296: cursor.right.generateOptimizedStringConcatenation(
297: blockScope, codeStream,
298: cursor.right.implicitConversion
299: & TypeIds.COMPILE_TYPE_MASK);
300: codeStream.recordPositionsFrom(pcAux,
301: cursor.right.sourceStart);
302: }
303: codeStream.recordPositionsFrom(pc,
304: this .left.sourceStart);
305: pc = codeStream.position;
306: this .right.generateOptimizedStringConcatenation(
307: blockScope, codeStream,
308: this .right.implicitConversion
309: & TypeIds.COMPILE_TYPE_MASK);
310: codeStream.recordPositionsFrom(pc,
311: this .right.sourceStart);
312: } else {
313: super .generateOptimizedStringConcatenationCreation(
314: blockScope, codeStream, typeID);
315: }
316: }
317: }
318:
319: public StringBuffer printExpressionNoParenthesis(int indent,
320: StringBuffer output) {
321: // keep implementation in sync with
322: // BinaryExpression#printExpressionNoParenthesis and
323: // OperatorExpression#printExpression
324: if (this .referencesTable == null) {
325: return super .printExpressionNoParenthesis(indent, output);
326: }
327: String operatorString = operatorToString();
328: for (int i = this .arity - 1; i >= 0; i--) {
329: output.append('(');
330: }
331: output = this .referencesTable[0].left.printExpression(indent,
332: output);
333: for (int i = 0, end = this .arity; i < end; i++) {
334: output.append(' ').append(operatorString).append(' ');
335: output = this .referencesTable[i].right.printExpression(0,
336: output);
337: output.append(')');
338: }
339: output.append(' ').append(operatorString).append(' ');
340: return this .right.printExpression(0, output);
341: }
342:
343: public TypeBinding resolveType(BlockScope scope) {
344: // keep implementation in sync with BinaryExpression#resolveType
345: if (this .referencesTable == null) {
346: return super .resolveType(scope);
347: }
348: BinaryExpression cursor;
349: if ((cursor = this .referencesTable[0]).left instanceof CastExpression) {
350: cursor.left.bits |= ASTNode.DisableUnnecessaryCastCheck;
351: // will check later on
352: }
353: cursor.left.resolveType(scope);
354: for (int i = 0, end = this .arity; i < end; i++) {
355: this .referencesTable[i]
356: .nonRecursiveResolveTypeUpwards(scope);
357: }
358: nonRecursiveResolveTypeUpwards(scope);
359: return this .resolvedType;
360: }
361:
362: public void traverse(ASTVisitor visitor, BlockScope scope) {
363: if (this .referencesTable == null) {
364: super .traverse(visitor, scope);
365: } else {
366: if (visitor.visit(this , scope)) {
367: int restart;
368: for (restart = this .arity - 1; restart >= 0; restart--) {
369: if (!visitor.visit(this .referencesTable[restart],
370: scope)) {
371: visitor.endVisit(this .referencesTable[restart],
372: scope);
373: break;
374: }
375: }
376: restart++;
377: // restart now points to the deepest BE for which
378: // visit returned true, if any
379: if (restart == 0) {
380: this .referencesTable[0].left.traverse(visitor,
381: scope);
382: }
383: for (int i = restart, end = this .arity; i < end; i++) {
384: this .referencesTable[i].right.traverse(visitor,
385: scope);
386: visitor.endVisit(this .referencesTable[i], scope);
387: }
388: this .right.traverse(visitor, scope);
389: }
390: visitor.endVisit(this , scope);
391: }
392: }
393:
394: /**
395: * Change {@link #arityMax} if and as needed. The current policy is to double
396: * arityMax each time this method is called, until it reaches
397: * {@link #ARITY_MAX_MAX}. Other policies may consider incrementing it less
398: * agressively. Call only after an appropriate value has been assigned to
399: * {@link #left}.
400: */
401: // more sophisticate increment policies would leverage the leftmost expression
402: // to hold an indication of the number of uses of a given arityMax in a row
403: public void tuneArityMax() {
404: if (this .arityMax < ARITY_MAX_MAX) {
405: this .arityMax *= 2;
406: }
407: }
408: }
|