/*******************************************************************************
 * Copyright (c) 2000, 2003 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials 
 * are made available under the terms of the Common Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/cpl-v10.html
 * 
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package net.sourceforge.phpdt.internal.compiler.lookup;

import net.sourceforge.phpdt.core.compiler.CharOperation;
import net.sourceforge.phpdt.internal.compiler.ast.MethodDeclaration;
import net.sourceforge.phpdt.internal.compiler.ast.TypeDeclaration;
import net.sourceforge.phpdt.internal.compiler.problem.ProblemReporter;
import net.sourceforge.phpdt.internal.compiler.util.HashtableOfObject;

public final class MethodVerifier implements TagBits, TypeConstants {
	SourceTypeBinding type;

	HashtableOfObject inheritedMethods;

	HashtableOfObject currentMethods;

	ReferenceBinding runtimeException;

	ReferenceBinding errorException;

	LookupEnvironment environment;

	/*
	 * Binding creation is responsible for reporting all problems with types: -
	 * all modifier problems (duplicates & multiple visibility modifiers +
	 * incompatible combinations - abstract/final) - plus invalid modifiers
	 * given the context (the verifier did not do this before) - qualified name
	 * collisions between a type and a package (types in default packages are
	 * excluded) - all type hierarchy problems: - cycles in the superclass or
	 * superinterface hierarchy - an ambiguous, invisible or missing superclass
	 * or superinterface - extending a final class - extending an interface
	 * instead of a class - implementing a class instead of an interface -
	 * implementing the same interface more than once (ie. duplicate interfaces) -
	 * with nested types: - shadowing an enclosing type's source name - defining
	 * a static class or interface inside a non-static nested class - defining
	 * an interface as a local type (local types can only be classes)
	 */
	public MethodVerifier(LookupEnvironment environment) {
		this.type = null; // Initialized with the public method
							// verify(SourceTypeBinding)
		this.inheritedMethods = null;
		this.currentMethods = null;
		this.runtimeException = null;
		this.errorException = null;
		this.environment = environment;
	}

	private void checkAgainstInheritedMethods(MethodBinding currentMethod,
			MethodBinding[] methods, int length) {
		currentMethod.modifiers |= CompilerModifiers.AccOverriding;
		for (int i = length; --i >= 0;) {
			MethodBinding inheritedMethod = methods[i];
			if (!currentMethod.isAbstract() && inheritedMethod.isAbstract())
				currentMethod.modifiers |= CompilerModifiers.AccImplementing;

			if (currentMethod.returnType != inheritedMethod.returnType) {
				this.problemReporter(currentMethod).incompatibleReturnType(
						currentMethod, inheritedMethod);
			} else if (currentMethod.isStatic() != inheritedMethod.isStatic()) { // Cannot
																					// override
																					// a
																					// static
																					// method
																					// or
																					// hide
																					// an
																					// instance
																					// method
				this.problemReporter(currentMethod).staticAndInstanceConflict(
						currentMethod, inheritedMethod);
			} else {
				if (currentMethod.thrownExceptions != NoExceptions)
					this.checkExceptions(currentMethod, inheritedMethod);
				if (inheritedMethod.isFinal())
					this.problemReporter(currentMethod)
							.finalMethodCannotBeOverridden(currentMethod,
									inheritedMethod);
				if (!this.isAsVisible(currentMethod, inheritedMethod))
					this.problemReporter(currentMethod).visibilityConflict(
							currentMethod, inheritedMethod);
				// if (inheritedMethod.isViewedAsDeprecated())
				// if (!currentMethod.isViewedAsDeprecated() ||
				// environment.options.reportDeprecationInsideDeprecatedCode)
				// this.problemReporter(currentMethod).overridesDeprecatedMethod(currentMethod,
				// inheritedMethod);
			}
		}
	}

	/*
	 * "8.4.4" Verify that newExceptions are all included in
	 * inheritedExceptions. Assumes all exceptions are valid and throwable.
	 * Unchecked exceptions (compatible with runtime & error) are ignored (see
	 * the spec on pg. 203).
	 */
	private void checkExceptions(MethodBinding newMethod,
			MethodBinding inheritedMethod) {
		ReferenceBinding[] newExceptions = newMethod.thrownExceptions;
		ReferenceBinding[] inheritedExceptions = inheritedMethod.thrownExceptions;
		for (int i = newExceptions.length; --i >= 0;) {
			ReferenceBinding newException = newExceptions[i];
			int j = inheritedExceptions.length;
			while (--j > -1
					&& !this.isSameClassOrSubclassOf(newException,
							inheritedExceptions[j]))
				;
			if (j == -1)
				if (!(newException.isCompatibleWith(this.runtimeException()) || newException
						.isCompatibleWith(this.errorException())))
					this.problemReporter(newMethod)
							.incompatibleExceptionInThrowsClause(this.type,
									newMethod, inheritedMethod, newException);
		}
	}

	private void checkInheritedMethods(MethodBinding[] methods, int length) {
		TypeBinding returnType = methods[0].returnType;
		int index = length;
		while (--index > 0 && returnType == methods[index].returnType)
			;
		if (index > 0) { // All inherited methods do NOT have the same
							// vmSignature
			this.problemReporter().inheritedMethodsHaveIncompatibleReturnTypes(
					this.type, methods, length);
			return;
		}

		MethodBinding concreteMethod = null;
		if (!type.isInterface()) { // ignore concrete methods for interfaces
			for (int i = length; --i >= 0;) { // Remember that only one of the
												// methods can be non-abstract
				if (!methods[i].isAbstract()) {
					concreteMethod = methods[i];
					break;
				}
			}
		}
		if (concreteMethod == null) {
			if (this.type.isClass() && !this.type.isAbstract()) {
				for (int i = length; --i >= 0;)
					if (!mustImplementAbstractMethod(methods[i]))
						return; // have already reported problem against the
								// concrete superclass

				TypeDeclaration typeDeclaration = this.type.scope.referenceContext;
				if (typeDeclaration != null) {
					MethodDeclaration missingAbstractMethod = typeDeclaration
							.addMissingAbstractMethodFor(methods[0]);
					missingAbstractMethod.scope.problemReporter()
							.abstractMethodMustBeImplemented(this.type,
									methods[0]);
				} else {
					this.problemReporter().abstractMethodMustBeImplemented(
							this.type, methods[0]);
				}
			}
			return;
		}

		MethodBinding[] abstractMethods = new MethodBinding[length - 1];
		index = 0;
		for (int i = length; --i >= 0;)
			if (methods[i] != concreteMethod)
				abstractMethods[index++] = methods[i];

		// Remember that interfaces can only define public instance methods
		if (concreteMethod.isStatic())
			// Cannot inherit a static method which is specified as an instance
			// method by an interface
			this.problemReporter().staticInheritedMethodConflicts(type,
					concreteMethod, abstractMethods);
		if (!concreteMethod.isPublic())
			// Cannot reduce visibility of a public method specified by an
			// interface
			this.problemReporter().inheritedMethodReducesVisibility(type,
					concreteMethod, abstractMethods);
		if (concreteMethod.thrownExceptions != NoExceptions)
			for (int i = abstractMethods.length; --i >= 0;)
				this.checkExceptions(concreteMethod, abstractMethods[i]);
	}

	/*
	 * For each inherited method identifier (message pattern - vm signature
	 * minus the return type) if current method exists if current's vm signature
	 * does not match an inherited signature then complain else compare
	 * current's exceptions & visibility against each inherited method else if
	 * inherited methods = 1 if inherited is abstract && type is NOT an
	 * interface or abstract, complain else if vm signatures do not match
	 * complain else find the concrete implementation amongst the abstract
	 * methods (can only be 1) if one exists then it must be a public instance
	 * method compare concrete's exceptions against each abstract method else
	 * complain about missing implementation only if type is NOT an interface or
	 * abstract
	 */
	private void checkMethods() {
		boolean mustImplementAbstractMethods = this.type.isClass()
				&& !this.type.isAbstract();
		char[][] methodSelectors = this.inheritedMethods.keyTable;
		for (int s = methodSelectors.length; --s >= 0;) {
			if (methodSelectors[s] != null) {
				MethodBinding[] current = (MethodBinding[]) this.currentMethods
						.get(methodSelectors[s]);
				MethodBinding[] inherited = (MethodBinding[]) this.inheritedMethods.valueTable[s];

				int index = -1;
				MethodBinding[] matchingInherited = new MethodBinding[inherited.length];
				if (current != null) {
					for (int i = 0, length1 = current.length; i < length1; i++) {
						while (index >= 0)
							matchingInherited[index--] = null; // clear the
																// previous
																// contents of
																// the matching
																// methods
						MethodBinding currentMethod = current[i];
						for (int j = 0, length2 = inherited.length; j < length2; j++) {
							if (inherited[j] != null
									&& currentMethod
											.areParametersEqual(inherited[j])) {
								matchingInherited[++index] = inherited[j];
								inherited[j] = null; // do not want to find
														// it again
							}
						}
						if (index >= 0)
							this.checkAgainstInheritedMethods(currentMethod,
									matchingInherited, index + 1); // pass in
																	// the
																	// length of
																	// matching
					}
				}
				for (int i = 0, length = inherited.length; i < length; i++) {
					while (index >= 0)
						matchingInherited[index--] = null; // clear the
															// previous contents
															// of the matching
															// methods
					if (inherited[i] != null) {
						matchingInherited[++index] = inherited[i];
						for (int j = i + 1; j < length; j++) {
							if (inherited[j] != null
									&& inherited[i]
											.areParametersEqual(inherited[j])) {
								matchingInherited[++index] = inherited[j];
								inherited[j] = null; // do not want to find
														// it again
							}
						}
					}
					if (index > 0) {
						this
								.checkInheritedMethods(matchingInherited,
										index + 1); // pass in the length of
													// matching
					} else if (mustImplementAbstractMethods && index == 0
							&& matchingInherited[0].isAbstract()) {
						if (mustImplementAbstractMethod(matchingInherited[0])) {
							TypeDeclaration typeDeclaration = this.type.scope.referenceContext;
							if (typeDeclaration != null) {
								MethodDeclaration missingAbstractMethod = typeDeclaration
										.addMissingAbstractMethodFor(matchingInherited[0]);
								missingAbstractMethod.scope
										.problemReporter()
										.abstractMethodMustBeImplemented(
												this.type, matchingInherited[0]);
							} else {
								this
										.problemReporter()
										.abstractMethodMustBeImplemented(
												this.type, matchingInherited[0]);
							}
						}
					}
				}
			}
		}
	}

	private void checkPackagePrivateAbstractMethod(MethodBinding abstractMethod) {
		ReferenceBinding superType = this.type.superclass();
		char[] selector = abstractMethod.selector;
		do {
			if (!superType.isValidBinding())
				return;
			if (!superType.isAbstract())
				return; // closer non abstract super type will be flagged
						// instead

			MethodBinding[] methods = superType.getMethods(selector);
			nextMethod: for (int m = methods.length; --m >= 0;) {
				MethodBinding method = methods[m];
				if (method.returnType != abstractMethod.returnType
						|| !method.areParametersEqual(abstractMethod))
					continue nextMethod;
				if (method.isPrivate() || method.isConstructor()
						|| method.isDefaultAbstract())
					continue nextMethod;
				if (superType.fPackage == abstractMethod.declaringClass.fPackage)
					return; // found concrete implementation of abstract method
							// in same package
			}
		} while ((superType = superType.superclass()) != abstractMethod.declaringClass);

		// non visible abstract methods cannot be overridden so the type must be
		// defined abstract
		this.problemReporter().abstractMethodCannotBeOverridden(this.type,
				abstractMethod);
	}

	/*
	 * Binding creation is responsible for reporting: - all modifier problems
	 * (duplicates & multiple visibility modifiers + incompatible combinations) -
	 * plus invalid modifiers given the context... examples: - interface methods
	 * can only be public - abstract methods can only be defined by abstract
	 * classes - collisions... 2 methods with identical vmSelectors - multiple
	 * methods with the same message pattern but different return types -
	 * ambiguous, invisible or missing return/argument/exception types - check
	 * the type of any array is not void - check that each exception type is
	 * Throwable or a subclass of it
	 */
	private void computeInheritedMethods() {
		this.inheritedMethods = new HashtableOfObject(51); // maps method
															// selectors to an
															// array of
															// methods... must
															// search to match
															// paramaters &
															// return type
		ReferenceBinding[][] interfacesToVisit = new ReferenceBinding[5][];
		int lastPosition = 0;
		interfacesToVisit[lastPosition] = type.superInterfaces();

		ReferenceBinding superType = this.type.isClass() ? this.type
				.superclass() : this.type.scope.getJavaLangObject(); // check
																		// interface
																		// methods
																		// against
																		// Object
		MethodBinding[] nonVisibleDefaultMethods = null;
		int nonVisibleCount = 0;

		while (superType != null) {
			if (superType.isValidBinding()) {
				ReferenceBinding[] itsInterfaces = superType.superInterfaces();
				if (itsInterfaces != NoSuperInterfaces) {
					if (++lastPosition == interfacesToVisit.length)
						System
								.arraycopy(
										interfacesToVisit,
										0,
										interfacesToVisit = new ReferenceBinding[lastPosition * 2][],
										0, lastPosition);
					interfacesToVisit[lastPosition] = itsInterfaces;
				}

				MethodBinding[] methods = superType.methods();
				nextMethod: for (int m = methods.length; --m >= 0;) {
					MethodBinding method = methods[m];
					if (!(method.isPrivate() || method.isConstructor() || method
							.isDefaultAbstract())) { // look at all methods
														// which are NOT private
														// or constructors or
														// default abstract
						MethodBinding[] existingMethods = (MethodBinding[]) this.inheritedMethods
								.get(method.selector);
						if (existingMethods != null) {
							for (int i = 0, length = existingMethods.length; i < length; i++) {
								if (method.returnType == existingMethods[i].returnType
										&& method
												.areParametersEqual(existingMethods[i])) {
									if (method.isDefault()
											&& method.isAbstract()
											&& method.declaringClass.fPackage != type.fPackage)
										checkPackagePrivateAbstractMethod(method);
									continue nextMethod;
								}
							}
						}
						if (nonVisibleDefaultMethods != null)
							for (int i = 0; i < nonVisibleCount; i++)
								if (method.returnType == nonVisibleDefaultMethods[i].returnType
										&& CharOperation
												.equals(
														method.selector,
														nonVisibleDefaultMethods[i].selector)
										&& method
												.areParametersEqual(nonVisibleDefaultMethods[i]))
									continue nextMethod;

						if (!(method.isDefault() && method.declaringClass.fPackage != type.fPackage)) { // ignore
																										// methods
																										// which
																										// have
																										// default
																										// visibility
																										// and
																										// are
																										// NOT
																										// defined
																										// in
																										// another
																										// package
							if (existingMethods == null)
								existingMethods = new MethodBinding[1];
							else
								System
										.arraycopy(
												existingMethods,
												0,
												(existingMethods = new MethodBinding[existingMethods.length + 1]),
												0, existingMethods.length - 1);
							existingMethods[existingMethods.length - 1] = method;
							this.inheritedMethods.put(method.selector,
									existingMethods);
						} else {
							if (nonVisibleDefaultMethods == null)
								nonVisibleDefaultMethods = new MethodBinding[10];
							else if (nonVisibleCount == nonVisibleDefaultMethods.length)
								System
										.arraycopy(
												nonVisibleDefaultMethods,
												0,
												(nonVisibleDefaultMethods = new MethodBinding[nonVisibleCount * 2]),
												0, nonVisibleCount);
							nonVisibleDefaultMethods[nonVisibleCount++] = method;

							if (method.isAbstract() && !this.type.isAbstract()) // non
																				// visible
																				// abstract
																				// methods
																				// cannot
																				// be
																				// overridden
																				// so
																				// the
																				// type
																				// must
																				// be
																				// defined
																				// abstract
								this.problemReporter()
										.abstractMethodCannotBeOverridden(
												this.type, method);

							MethodBinding[] current = (MethodBinding[]) this.currentMethods
									.get(method.selector);
							if (current != null) { // non visible methods
													// cannot be overridden so a
													// warning is issued
								foundMatch: for (int i = 0, length = current.length; i < length; i++) {
									if (method.returnType == current[i].returnType
											&& method
													.areParametersEqual(current[i])) {
										this.problemReporter()
												.overridesPackageDefaultMethod(
														current[i], method);
										break foundMatch;
									}
								}
							}
						}
					}
				}
				superType = superType.superclass();
			}
		}

		for (int i = 0; i <= lastPosition; i++) {
			ReferenceBinding[] interfaces = interfacesToVisit[i];
			if (interfaces == null) {
				interfaces = new ReferenceBinding[0];
			}
			for (int j = 0, length = interfaces.length; j < length; j++) {
				superType = interfaces[j];
				if ((superType.tagBits & InterfaceVisited) == 0) {
					superType.tagBits |= InterfaceVisited;
					if (superType.isValidBinding()) {
						ReferenceBinding[] itsInterfaces = superType
								.superInterfaces();
						if (itsInterfaces != NoSuperInterfaces) {
							if (++lastPosition == interfacesToVisit.length)
								System
										.arraycopy(
												interfacesToVisit,
												0,
												interfacesToVisit = new ReferenceBinding[lastPosition * 2][],
												0, lastPosition);
							interfacesToVisit[lastPosition] = itsInterfaces;
						}

						MethodBinding[] methods = superType.methods();
						for (int m = methods.length; --m >= 0;) { // Interface
																	// methods
																	// are all
																	// abstract
																	// public
							MethodBinding method = methods[m];
							MethodBinding[] existingMethods = (MethodBinding[]) this.inheritedMethods
									.get(method.selector);
							if (existingMethods == null)
								existingMethods = new MethodBinding[1];
							else
								System
										.arraycopy(
												existingMethods,
												0,
												(existingMethods = new MethodBinding[existingMethods.length + 1]),
												0, existingMethods.length - 1);
							existingMethods[existingMethods.length - 1] = method;
							this.inheritedMethods.put(method.selector,
									existingMethods);
						}
					}
				}
			}
		}

		// bit reinitialization
		for (int i = 0; i <= lastPosition; i++) {
			ReferenceBinding[] interfaces = interfacesToVisit[i];
			if (interfaces == null) {
				interfaces = new ReferenceBinding[0];
			}
			for (int j = 0, length = interfaces.length; j < length; j++)
				interfaces[j].tagBits &= ~InterfaceVisited;
		}
	}

	private void computeMethods() {
		MethodBinding[] methods = type.methods();
		if (methods == null) {
			methods = new MethodBinding[0];
		}
		int size = methods.length;
		this.currentMethods = new HashtableOfObject(size == 0 ? 1 : size); // maps
																			// method
																			// selectors
																			// to
																			// an
																			// array
																			// of
																			// methods...
																			// must
																			// search
																			// to
																			// match
																			// paramaters
																			// &
																			// return
																			// type
		for (int m = size; --m >= 0;) {
			MethodBinding method = methods[m];
			if (!(method.isConstructor() || method.isDefaultAbstract())) { // keep
																			// all
																			// methods
																			// which
																			// are
																			// NOT
																			// constructors
																			// or
																			// default
																			// abstract
				MethodBinding[] existingMethods = (MethodBinding[]) this.currentMethods
						.get(method.selector);
				if (existingMethods == null)
					existingMethods = new MethodBinding[1];
				else
					System
							.arraycopy(
									existingMethods,
									0,
									(existingMethods = new MethodBinding[existingMethods.length + 1]),
									0, existingMethods.length - 1);
				existingMethods[existingMethods.length - 1] = method;
				this.currentMethods.put(method.selector, existingMethods);
			}
		}
	}

	private ReferenceBinding errorException() {
		if (errorException == null)
			this.errorException = this.type.scope.getJavaLangError();
		return errorException;
	}

	private boolean isAsVisible(MethodBinding newMethod,
			MethodBinding inheritedMethod) {
		if (inheritedMethod.modifiers == newMethod.modifiers)
			return true;

		if (newMethod.isPublic())
			return true; // Covers everything
		if (inheritedMethod.isPublic())
			return false;

		if (newMethod.isProtected())
			return true;
		if (inheritedMethod.isProtected())
			return false;

		return !newMethod.isPrivate(); // The inheritedMethod cannot be private
										// since it would not be visible
	}

	private boolean isSameClassOrSubclassOf(ReferenceBinding testClass,
			ReferenceBinding superclass) {
		do {
			if (testClass == superclass)
				return true;
		} while ((testClass = testClass.superclass()) != null);
		return false;
	}

	private boolean mustImplementAbstractMethod(MethodBinding abstractMethod) {
		// if the type's superclass is an abstract class, then all abstract
		// methods must be implemented
		// otherwise, skip it if the type's superclass must implement any of the
		// inherited methods
		ReferenceBinding superclass = this.type.superclass();
		ReferenceBinding declaringClass = abstractMethod.declaringClass;
		if (declaringClass.isClass()) {
			while (superclass.isAbstract() && superclass != declaringClass)
				superclass = superclass.superclass(); // find the first
														// concrete superclass
														// or the abstract
														// declaringClass
		} else {
			if (this.type.implementsInterface(declaringClass, false)) {
				if (this.type.isAbstract())
					return false; // leave it for the subclasses
				if (!superclass.implementsInterface(declaringClass, true)) // only
																			// if a
																			// superclass
																			// does
																			// not
																			// also
																			// implement
																			// the
																			// interface
					return true;
			}
			while (superclass.isAbstract()
					&& !superclass.implementsInterface(declaringClass, false))
				superclass = superclass.superclass(); // find the first
														// concrete superclass
														// or the superclass
														// which implements the
														// interface
		}
		return superclass.isAbstract(); // if it is a concrete class then we
										// have already reported problem against
										// it
	}

	private ProblemReporter problemReporter() {
		return this.type.scope.problemReporter();
	}

	private ProblemReporter problemReporter(MethodBinding currentMethod) {
		ProblemReporter reporter = problemReporter();
		if (currentMethod.declaringClass == type) // only report against the
													// currentMethod if its
													// implemented by the type
			reporter.referenceContext = currentMethod.sourceMethod();
		return reporter;
	}

	private ReferenceBinding runtimeException() {
		if (runtimeException == null)
			this.runtimeException = this.type.scope
					.getJavaLangRuntimeException();
		return runtimeException;
	}

	public void verify(SourceTypeBinding type) {
		this.type = type;
		this.computeMethods();
		this.computeInheritedMethods();
		this.checkMethods();
	}

	public String toString() {
		StringBuffer buffer = new StringBuffer(10);
		buffer.append("MethodVerifier for type: "); //$NON-NLS-1$
		buffer.append(type.readableName());
		buffer.append('\n');
		buffer.append("\t-inherited methods: "); //$NON-NLS-1$
		buffer.append(this.inheritedMethods);
		return buffer.toString();
	}
}