org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/ast/CombinedBinaryExpression.java

/*******************************************************************************
 * Copyright (c) 2006, 2012 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *     Stephan Herrmann - Contribution for
 *								bug 345305 - [compiler][null] Compiler misidentifies a case of "variable can only be null"
 *******************************************************************************/
package org.eclipse.jdt.internal.compiler.ast;

import org.eclipse.jdt.internal.compiler.ASTVisitor;
import org.eclipse.jdt.internal.compiler.codegen.CodeStream;
import org.eclipse.jdt.internal.compiler.flow.FlowContext;
import org.eclipse.jdt.internal.compiler.flow.FlowInfo;
import org.eclipse.jdt.internal.compiler.impl.Constant;
import org.eclipse.jdt.internal.compiler.lookup.BlockScope;
import org.eclipse.jdt.internal.compiler.lookup.TypeBinding;
import org.eclipse.jdt.internal.compiler.lookup.TypeIds;

/**
 * CombinedBinaryExpression is an implementation of BinaryExpression that
 * specifically attempts to mitigate the issues raised by expressions which
 * have a very deep leftmost branch. It does so by maintaining a table of
 * direct references to its subexpressions, and implementing non-recursive
 * variants of the most significant recursive algorithms of its ancestors.
 * The subexpressions table only holds intermediate binary expressions. Its
 * role is to provide the reversed navigation through the left relationship
 * of BinaryExpression to Expression. To cope with potentially very deep
 * left branches, an instance of CombinedBinaryExpression is created once in
 * a while, using variable thresholds held by {@link #arityMax}.
 * As a specific case, the topmost node of all binary expressions that are
 * deeper than one is a CombinedBinaryExpression, but it has no references
 * table.<br>
 * Notes:
 * <ul>
 * <li>CombinedBinaryExpression is not meant to behave in other ways than
 *     BinaryExpression in any observable respect;</li>
 * <li>visitors that implement their own traversal upon binary expressions
 *     should consider taking advantage of combined binary expressions, or
 *     else face a risk of StackOverflowError upon deep instances;</li>
 * <li>callers that need to change the operator should rebuild the expression
 *     from scratch, or else amend the references table as needed to cope with
 *     the resulting, separated expressions.</li>
 * </ul>
 */
public class CombinedBinaryExpression extends BinaryExpression {

	/**
	 * The number of consecutive binary expressions of this' left branch that
	 * bear the same operator as this.<br>
	 * Notes:
	 * <ul><li>the presence of a CombinedBinaryExpression instance resets
	 *         arity, even when its operator is compatible;</li>
	 *	   <li>this property is maintained by the parser.</li>
	 * </ul>
	 */
	public int arity;

	/**
	 * The threshold that will trigger the creation of the next full-fledged
	 * CombinedBinaryExpression. This field is only maintained for the
	 * topmost binary expression (it is 0 otherwise). It enables a variable
	 * policy, which scales better with very large expressions.
	 */
	public int arityMax;

	/**
	 * Upper limit for {@link #arityMax}.
	 */
	public static final int ARITY_MAX_MAX = 160;

	/**
	 * Default lower limit for {@link #arityMax}.
	 */
	public static final int ARITY_MAX_MIN = 20;

	/**
	 * Default value for the first term of the series of {@link #arityMax}
	 * values. Changing this allows for experimentation. Not meant to be
	 * changed during a parse operation.
	 */
	public static int defaultArityMaxStartingValue = ARITY_MAX_MIN;

	/**
	 * A table of references to the binary expressions of this' left branch.
	 * Instances of CombinedBinaryExpression are not repeated here. Instead,
	 * the left subexpression of referencesTable[0] may be a combined binary
	 * expression, if appropriate. Null when this only cares about tracking
	 * the expression's arity.
	 */
	public BinaryExpression referencesTable[];

/**
 * Make a new CombinedBinaryExpression. If arity is strictly greater than one,
 * a references table is built and initialized with the reverse relationship of
 * the one defined by {@link BinaryExpression#left}. arity and left must be
 * compatible with each other (that is, there must be at least arity - 1
 * consecutive compatible binary expressions into the leftmost branch of left,
 * the topmost of which being left's immediate left expression).
 * @param left the left branch expression
 * @param right the right branch expression
 * @param operator the operator for this binary expression - only PLUS for now
 * @param arity the number of binary expressions of a compatible operator that
 *        already exist into the leftmost branch of left (including left); must
 *        be strictly greater than 0
 */
public CombinedBinaryExpression(Expression left, Expression right, int operator, int arity) {
	super(left, right, operator);
	initArity(left, arity);
}
public CombinedBinaryExpression(CombinedBinaryExpression expression) {
	super(expression);
	initArity(expression.left, expression.arity);
}

public FlowInfo analyseCode(BlockScope currentScope, FlowContext flowContext,
		FlowInfo flowInfo) {
	// keep implementation in sync with BinaryExpression#analyseCode
	if (this.referencesTable == null) {
		return super.analyseCode(currentScope, flowContext, flowInfo);
	}
	try {
		BinaryExpression cursor;
		if ((cursor = this.referencesTable[0]).resolvedType.id !=
				TypeIds.T_JavaLangString) {
			cursor.left.checkNPE(currentScope, flowContext, flowInfo);
		}
		flowInfo = cursor.left.analyseCode(currentScope, flowContext, flowInfo).
			unconditionalInits();
		for (int i = 0, end = this.arity; i < end; i ++) {
			if ((cursor = this.referencesTable[i]).resolvedType.id !=
					TypeIds.T_JavaLangString) {
				cursor.right.checkNPE(currentScope, flowContext, flowInfo);
			}
			flowInfo = cursor.right.
				analyseCode(currentScope, flowContext, flowInfo).
					unconditionalInits();
		}
		if (this.resolvedType.id != TypeIds.T_JavaLangString) {
			this.right.checkNPE(currentScope, flowContext, flowInfo);
		}
		return this.right.analyseCode(currentScope, flowContext, flowInfo).
			unconditionalInits();
	} finally {
		// account for exception possibly thrown by arithmetics
		flowContext.recordAbruptExit();
	}
}

public void generateOptimizedStringConcatenation(BlockScope blockScope,
		CodeStream codeStream, int typeID) {
	// keep implementation in sync with BinaryExpression and Expression
	// #generateOptimizedStringConcatenation
	if (this.referencesTable == null) {
		super.generateOptimizedStringConcatenation(blockScope, codeStream,
			typeID);
	} else {
		if ((((this.bits & ASTNode.OperatorMASK) >> ASTNode.OperatorSHIFT) ==
				OperatorIds.PLUS)
			&& ((this.bits & ASTNode.ReturnTypeIDMASK) == TypeIds.T_JavaLangString)) {
			if (this.constant != Constant.NotAConstant) {
				codeStream.generateConstant(this.constant, this.implicitConversion);
				codeStream.invokeStringConcatenationAppendForType(
						this.implicitConversion & TypeIds.COMPILE_TYPE_MASK);
			} else {
				BinaryExpression cursor = this.referencesTable[0];

				int restart = 0;
	//			int cursorTypeID;
				int pc = codeStream.position;
				for (restart = this.arity - 1; restart >= 0; restart--) {
					if ((cursor = this.referencesTable[restart]).constant !=
							Constant.NotAConstant) {
						codeStream.generateConstant(cursor.constant,
							cursor.implicitConversion);
						codeStream.invokeStringConcatenationAppendForType(
							cursor.implicitConversion & TypeIds.COMPILE_TYPE_MASK);
						break;
					}
					// never happens for now - may reconsider if we decide to
					// cover more than string concatenation
	//				if (!((((cursor = this.referencesTable[restart]).bits &
	//						ASTNode.OperatorMASK) >> ASTNode.OperatorSHIFT) ==
	//							OperatorIds.PLUS) &
	//						((cursorTypeID = cursor.bits & ASTNode.ReturnTypeIDMASK) ==
	//							TypeIds.T_JavaLangString)) {
	//					if (cursorTypeID == T_JavaLangString &&
	//							cursor.constant != Constant.NotAConstant &&
	//							cursor.constant.stringValue().length() == 0) {
	//						break; // optimize str + ""
	//					}
	//					cursor.generateCode(blockScope, codeStream, true);
	//					codeStream.invokeStringConcatenationAppendForType(
	//							cursorTypeID);
	//					break;
	//				}
				}
				restart++;
				if (restart == 0) { // reached the leftmost expression
					cursor.left.generateOptimizedStringConcatenation(
						blockScope,
						codeStream,
						cursor.left.implicitConversion & TypeIds.COMPILE_TYPE_MASK);
				}
				int pcAux;
				for (int i = restart; i < this.arity; i++) {
					codeStream.recordPositionsFrom(pc,
						(cursor = this.referencesTable[i]).left.sourceStart);
					pcAux = codeStream.position;
					cursor.right.generateOptimizedStringConcatenation(blockScope,
						codeStream,	cursor.right.implicitConversion &
							TypeIds.COMPILE_TYPE_MASK);
					codeStream.recordPositionsFrom(pcAux, cursor.right.sourceStart);
				}
				codeStream.recordPositionsFrom(pc, this.left.sourceStart);
				pc = codeStream.position;
				this.right.generateOptimizedStringConcatenation(
					blockScope,
					codeStream,
					this.right.implicitConversion & TypeIds.COMPILE_TYPE_MASK);
				codeStream.recordPositionsFrom(pc, this.right.sourceStart);
			}
		} else {
			super.generateOptimizedStringConcatenation(blockScope, codeStream,
				typeID);
		}
	}
}

public void generateOptimizedStringConcatenationCreation(BlockScope blockScope,
		CodeStream codeStream, int typeID) {
	// keep implementation in sync with BinaryExpression
	// #generateOptimizedStringConcatenationCreation
	if (this.referencesTable == null) {
		super.generateOptimizedStringConcatenationCreation(blockScope,
			codeStream,	typeID);
	} else {
		if ((((this.bits & ASTNode.OperatorMASK) >> ASTNode.OperatorSHIFT) ==
				OperatorIds.PLUS) &&
					((this.bits & ASTNode.ReturnTypeIDMASK) ==
						TypeIds.T_JavaLangString) &&
					this.constant == Constant.NotAConstant) {
			int pc = codeStream.position;
			BinaryExpression cursor = this.referencesTable[this.arity - 1];
				// silence warnings
			int restart = 0;
			for (restart = this.arity - 1; restart >= 0; restart--) {
				if (((((cursor = this.referencesTable[restart]).bits &
						ASTNode.OperatorMASK) >> ASTNode.OperatorSHIFT) ==
							OperatorIds.PLUS) &&
						((cursor.bits & ASTNode.ReturnTypeIDMASK) ==
							TypeIds.T_JavaLangString)) {
					if (cursor.constant != Constant.NotAConstant) {
						codeStream.newStringContatenation(); // new: java.lang.StringBuffer
						codeStream.dup();
						codeStream.ldc(cursor.constant.stringValue());
						codeStream.invokeStringConcatenationStringConstructor();
						// invokespecial: java.lang.StringBuffer.<init>(Ljava.lang.String;)V
						break;
					}
				} else {
					cursor.generateOptimizedStringConcatenationCreation(blockScope,
						codeStream, cursor.implicitConversion &
							TypeIds.COMPILE_TYPE_MASK);
					break;
				}
			}
			restart++;
			if (restart == 0) { // reached the leftmost expression
				cursor.left.generateOptimizedStringConcatenationCreation(
					blockScope,
					codeStream,
					cursor.left.implicitConversion & TypeIds.COMPILE_TYPE_MASK);
			}
			int pcAux;
			for (int i = restart; i < this.arity; i++) {
				codeStream.recordPositionsFrom(pc,
					(cursor = this.referencesTable[i]).left.sourceStart);
				pcAux = codeStream.position;
				cursor.right.generateOptimizedStringConcatenation(blockScope,
					codeStream,	cursor.right.implicitConversion &
						TypeIds.COMPILE_TYPE_MASK);
				codeStream.recordPositionsFrom(pcAux, cursor.right.sourceStart);
			}
			codeStream.recordPositionsFrom(pc, this.left.sourceStart);
			pc = codeStream.position;
			this.right.generateOptimizedStringConcatenation(
				blockScope,
				codeStream,
				this.right.implicitConversion & TypeIds.COMPILE_TYPE_MASK);
			codeStream.recordPositionsFrom(pc, this.right.sourceStart);
		} else {
			super.generateOptimizedStringConcatenationCreation(blockScope,
				codeStream, typeID);
		}
	}
}
private void initArity(Expression expression, int value) {
	this.arity = value;
	if (value > 1) {
		this.referencesTable = new BinaryExpression[value];
		this.referencesTable[value - 1] = (BinaryExpression) expression;
		for (int i = value - 1; i > 0; i--) {
			this.referencesTable[i - 1] =
				(BinaryExpression) this.referencesTable[i].left;
		}
	} else {
		this.arityMax = defaultArityMaxStartingValue;
	}
}

public StringBuffer printExpressionNoParenthesis(int indent,
		StringBuffer output) {
	// keep implementation in sync with
	// BinaryExpression#printExpressionNoParenthesis and
	// OperatorExpression#printExpression
	if (this.referencesTable == null) {
		return super.printExpressionNoParenthesis(indent, output);
	}
	String operatorString = operatorToString();
	for (int i = this.arity - 1; i >= 0; i--) {
		output.append('(');
	}
	output = this.referencesTable[0].left.
		printExpression(indent, output);
	for (int i = 0, end = this.arity;
				i < end; i++) {
		output.append(' ').append(operatorString).append(' ');
		output = this.referencesTable[i].right.
			printExpression(0, output);
		output.append(')');
	}
	output.append(' ').append(operatorString).append(' ');
	return this.right.printExpression(0, output);
}

public TypeBinding resolveType(BlockScope scope) {
	// keep implementation in sync with BinaryExpression#resolveType
	if (this.referencesTable == null) {
		return super.resolveType(scope);
	}
	BinaryExpression cursor;
	if ((cursor = this.referencesTable[0]).left instanceof CastExpression) {
		cursor.left.bits |= ASTNode.DisableUnnecessaryCastCheck;
			// will check later on
	}
	cursor.left.resolveType(scope);
	for (int i = 0, end = this.arity; i < end; i ++) {
		this.referencesTable[i].nonRecursiveResolveTypeUpwards(scope);
	}
	nonRecursiveResolveTypeUpwards(scope);
	return this.resolvedType;
}

public void traverse(ASTVisitor visitor, BlockScope scope) {
	if (this.referencesTable == null) {
		super.traverse(visitor, scope);
	} else {
		if (visitor.visit(this, scope)) {
			int restart;
			for (restart = this.arity - 1;
					restart >= 0;
					restart--) {
				if (!visitor.visit(
						this.referencesTable[restart], scope)) {
					visitor.endVisit(
						this.referencesTable[restart], scope);
					break;
				}
			}
			restart++;
			// restart now points to the deepest BE for which
			// visit returned true, if any
			if (restart == 0) {
				this.referencesTable[0].left.traverse(visitor, scope);
			}
			for (int i = restart, end = this.arity;
						i < end; i++) {
				this.referencesTable[i].right.traverse(visitor, scope);
				visitor.endVisit(this.referencesTable[i], scope);
			}
			this.right.traverse(visitor, scope);
		}
		visitor.endVisit(this, scope);
	}
}

/**
 * Change {@link #arityMax} if and as needed. The current policy is to double
 * arityMax each time this method is called, until it reaches
 * {@link #ARITY_MAX_MAX}. Other policies may consider incrementing it less
 * agressively. Call only after an appropriate value has been assigned to
 * {@link #left}.
 */
// more sophisticate increment policies would leverage the leftmost expression
// to hold an indication of the number of uses of a given arityMax in a row
public void tuneArityMax() {
	if (this.arityMax < ARITY_MAX_MAX) {
		this.arityMax *= 2;
	}
}
}