package gr.uom.java.ast.decomposition.matching;

import gr.uom.java.ast.ASTInformationGenerator;
import gr.uom.java.ast.ASTReader;
import gr.uom.java.ast.ClassObject;
import gr.uom.java.ast.MethodObject;
import gr.uom.java.ast.decomposition.AbstractExpression;
import gr.uom.java.ast.decomposition.AbstractMethodFragment;
import gr.uom.java.ast.decomposition.StatementObject;
import gr.uom.java.ast.decomposition.StatementType;
import gr.uom.java.ast.decomposition.cfg.PDGNode;
import gr.uom.java.ast.decomposition.cfg.PlainVariable;
import gr.uom.java.ast.decomposition.matching.conditional.AbstractControlStructure;
import gr.uom.java.ast.decomposition.matching.conditional.AbstractControlStructureUtilities;
import gr.uom.java.ast.decomposition.matching.conditional.IfControlStructure;
import gr.uom.java.ast.decomposition.matching.conditional.SwitchControlStructure;
import gr.uom.java.ast.decomposition.matching.conditional.TernaryControlStructure;
import gr.uom.java.ast.decomposition.matching.loop.AbstractControlVariable;
import gr.uom.java.ast.decomposition.matching.loop.AbstractLoop;
import gr.uom.java.ast.decomposition.matching.loop.AbstractLoopUtilities;
import gr.uom.java.ast.decomposition.matching.loop.ConditionalLoop;
import gr.uom.java.ast.decomposition.matching.loop.ConditionalLoopASTNodeMatcher;
import gr.uom.java.ast.decomposition.matching.loop.ControlVariable;
import gr.uom.java.ast.decomposition.matching.loop.EnhancedForLoop;
import gr.uom.java.ast.inheritance.TypeBindingInheritanceDetection;
import gr.uom.java.ast.util.ExpressionExtractor;
import gr.uom.java.ast.util.MethodDeclarationUtility;
import gr.uom.java.ast.util.math.LevenshteinDistance;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;

import org.eclipse.jdt.core.ITypeRoot;
import org.eclipse.jdt.core.dom.ASTMatcher;
import org.eclipse.jdt.core.dom.ASTNode;
import org.eclipse.jdt.core.dom.AnonymousClassDeclaration;
import org.eclipse.jdt.core.dom.ArrayAccess;
import org.eclipse.jdt.core.dom.ArrayCreation;
import org.eclipse.jdt.core.dom.ArrayInitializer;
import org.eclipse.jdt.core.dom.Assignment;
import org.eclipse.jdt.core.dom.Block;
import org.eclipse.jdt.core.dom.BooleanLiteral;
import org.eclipse.jdt.core.dom.CastExpression;
import org.eclipse.jdt.core.dom.CatchClause;
import org.eclipse.jdt.core.dom.CharacterLiteral;
import org.eclipse.jdt.core.dom.ClassInstanceCreation;
import org.eclipse.jdt.core.dom.ConditionalExpression;
import org.eclipse.jdt.core.dom.DoStatement;
import org.eclipse.jdt.core.dom.EnhancedForStatement;
import org.eclipse.jdt.core.dom.Expression;
import org.eclipse.jdt.core.dom.ExpressionStatement;
import org.eclipse.jdt.core.dom.FieldAccess;
import org.eclipse.jdt.core.dom.ForStatement;
import org.eclipse.jdt.core.dom.IBinding;
import org.eclipse.jdt.core.dom.IMethodBinding;
import org.eclipse.jdt.core.dom.ITypeBinding;
import org.eclipse.jdt.core.dom.IVariableBinding;
import org.eclipse.jdt.core.dom.IfStatement;
import org.eclipse.jdt.core.dom.InfixExpression;
import org.eclipse.jdt.core.dom.InstanceofExpression;
import org.eclipse.jdt.core.dom.LabeledStatement;
import org.eclipse.jdt.core.dom.MethodDeclaration;
import org.eclipse.jdt.core.dom.MethodInvocation;
import org.eclipse.jdt.core.dom.Modifier;
import org.eclipse.jdt.core.dom.NullLiteral;
import org.eclipse.jdt.core.dom.NumberLiteral;
import org.eclipse.jdt.core.dom.ParenthesizedExpression;
import org.eclipse.jdt.core.dom.PrefixExpression;
import org.eclipse.jdt.core.dom.QualifiedName;
import org.eclipse.jdt.core.dom.ReturnStatement;
import org.eclipse.jdt.core.dom.SimpleName;
import org.eclipse.jdt.core.dom.Statement;
import org.eclipse.jdt.core.dom.StringLiteral;
import org.eclipse.jdt.core.dom.SuperFieldAccess;
import org.eclipse.jdt.core.dom.SuperMethodInvocation;
import org.eclipse.jdt.core.dom.SwitchStatement;
import org.eclipse.jdt.core.dom.SynchronizedStatement;
import org.eclipse.jdt.core.dom.ThisExpression;
import org.eclipse.jdt.core.dom.TryStatement;
import org.eclipse.jdt.core.dom.TypeLiteral;
import org.eclipse.jdt.core.dom.VariableDeclaration;
import org.eclipse.jdt.core.dom.VariableDeclarationFragment;
import org.eclipse.jdt.core.dom.VariableDeclarationStatement;
import org.eclipse.jdt.core.dom.WhileStatement;

public class ASTNodeMatcher extends ASTMatcher{

	private List<ASTNodeDifference> differences;
	private ITypeRoot typeRoot1;
	private ITypeRoot typeRoot2;
	private List<AbstractMethodFragment> additionallyMatchedFragments1;
	private List<AbstractMethodFragment> additionallyMatchedFragments2;
	
	public ASTNodeMatcher(ITypeRoot root1, ITypeRoot root2) {
		this.differences = new ArrayList<ASTNodeDifference>();
		this.typeRoot1 = root1;
		this.typeRoot2 = root2;
		this.additionallyMatchedFragments1 = new ArrayList<AbstractMethodFragment>();
		this.additionallyMatchedFragments2 = new ArrayList<AbstractMethodFragment>();
	}

	public boolean match(PDGNode nodeG1, PDGNode nodeG2) {
		NodePair pair = new NodePair(nodeG1.getId(), nodeG2.getId());
		NodePairComparisonCache cache = NodePairComparisonCache.getInstance();
		if(cache.containsNodePair(pair)) {
			this.differences.addAll(cache.getDifferencesForNodePair(pair));
			this.additionallyMatchedFragments1.addAll(cache.getAdditionallyMatchedFragments1(pair));
			this.additionallyMatchedFragments2.addAll(cache.getAdditionallyMatchedFragments2(pair));
			return cache.getMatchForNodePair(pair);
		}
		else {
			boolean match = nodeG1.getASTStatement().subtreeMatch(this, nodeG2.getASTStatement());
			cache.addDifferencesForNodePair(pair, this.differences);
			cache.addMatchForNodePair(pair, match);
			cache.setAdditionallyMatchedFragments1(pair, this.additionallyMatchedFragments1);
			cache.setAdditionallyMatchedFragments2(pair, this.additionallyMatchedFragments2);
			return match;
		}
	}

	protected void addDifference(ASTNodeDifference difference) {
		if(!differences.contains(difference))
			differences.add(difference);
	}

	public List<ASTNodeDifference> getDifferences() {
		return differences;
	}

	public ITypeRoot getTypeRoot1() {
		return typeRoot1;
	}

	public ITypeRoot getTypeRoot2() {
		return typeRoot2;
	}

	public List<AbstractMethodFragment> getAdditionallyMatchedFragments1() {
		return additionallyMatchedFragments1;
	}

	public List<AbstractMethodFragment> getAdditionallyMatchedFragments2() {
		return additionallyMatchedFragments2;
	}

	public String toString() {
		StringBuilder sb = new StringBuilder();
		for(ASTNodeDifference diff : differences) {
			sb.append(diff.toString());
		}
		return sb.toString();
	}

	public boolean isParameterizable() {
		if(onlyVariableTypeMismatchDifferences() || additionallyMatchedFragments1.size() > 0 || additionallyMatchedFragments2.size() > 0)
			return true;
		else if(methodInvocationMatchWithMissingExpressionAndDifferentNameAndDifferentArguments())
			return false;
		else {
			for(ASTNodeDifference diff : differences) {
				boolean expression1NestedUnderCatchClause = isNestedUnderAnonymousClassDeclaration(diff.getExpression1().getExpression());
				boolean expression2NestedUnderCatchClause = isNestedUnderAnonymousClassDeclaration(diff.getExpression2().getExpression());
				if(!diff.isParameterizable() && !expression1NestedUnderCatchClause && !expression2NestedUnderCatchClause)
					return false;
			}
			return true;
		}
	}

	private boolean methodInvocationMatchWithMissingExpressionAndDifferentNameAndDifferentArguments() {
		boolean missingExpression = false;
		boolean differentMethodName = false;
		boolean differentArguments = false;
		boolean expression1NestedUnderCatchClause = false;
		boolean expression2NestedUnderCatchClause = false;
		for(ASTNodeDifference difference : differences) {
			if(difference.containsDifferenceType(DifferenceType.MISSING_METHOD_INVOCATION_EXPRESSION))
				missingExpression = true;
			if(difference.containsDifferenceType(DifferenceType.METHOD_INVOCATION_NAME_MISMATCH))
				differentMethodName = true;
			if(difference.containsDifferenceType(DifferenceType.ARGUMENT_NUMBER_MISMATCH) || difference.containsDifferenceType(DifferenceType.TYPE_COMPATIBLE_REPLACEMENT))
				differentArguments = true;
			if(isNestedUnderAnonymousClassDeclaration(difference.getExpression1().getExpression()))
				expression1NestedUnderCatchClause = true;
			if(isNestedUnderAnonymousClassDeclaration(difference.getExpression2().getExpression()))
				expression2NestedUnderCatchClause = true;
		}
		return missingExpression && differentMethodName && differentArguments && !expression1NestedUnderCatchClause && !expression2NestedUnderCatchClause;
	}

	private boolean onlyVariableTypeMismatchDifferences() {
		int diffCount = 0;
		int variableTypeMismatchCount = 0;
		int subclassTypeMismatchCount = 0;
		int variableNameMismatchCount = 0;
		int methodInvocationNameMismatchCount = 0;
		int literalValueMismatchCount = 0;
		for(ASTNodeDifference difference : differences) {
			for(Difference diff : difference.getDifferences()) {
				diffCount++;
				if(diff.getType().equals(DifferenceType.VARIABLE_TYPE_MISMATCH)) {
					variableTypeMismatchCount++;
				}
				if(diff.getType().equals(DifferenceType.SUBCLASS_TYPE_MISMATCH)) {
					subclassTypeMismatchCount++;
				}
				if(diff.getType().equals(DifferenceType.VARIABLE_NAME_MISMATCH)) {
					variableNameMismatchCount++;
				}
				if(diff.getType().equals(DifferenceType.METHOD_INVOCATION_NAME_MISMATCH)) {
					methodInvocationNameMismatchCount++;
				}
				if(diff.getType().equals(DifferenceType.LITERAL_VALUE_MISMATCH)) {
					literalValueMismatchCount++;
				}
			}
		}
		if(diffCount > 0 && (diffCount == (variableTypeMismatchCount + subclassTypeMismatchCount + variableNameMismatchCount) ||
				diffCount == (variableTypeMismatchCount + subclassTypeMismatchCount + methodInvocationNameMismatchCount) ||
				diffCount == (variableTypeMismatchCount + subclassTypeMismatchCount + literalValueMismatchCount) ||
				diffCount == (variableTypeMismatchCount + subclassTypeMismatchCount + literalValueMismatchCount + methodInvocationNameMismatchCount) ||
				diffCount == (variableTypeMismatchCount + subclassTypeMismatchCount + literalValueMismatchCount + variableNameMismatchCount) ))
			return true;
		return false;
	}

	protected boolean isTypeHolder(Object o) {
		if(o.getClass().equals(MethodInvocation.class) || o.getClass().equals(SuperMethodInvocation.class)			
				|| o.getClass().equals(NumberLiteral.class) || o.getClass().equals(StringLiteral.class)
				|| o.getClass().equals(CharacterLiteral.class) || o.getClass().equals(BooleanLiteral.class)
				|| o.getClass().equals(TypeLiteral.class) || o.getClass().equals(NullLiteral.class)
				|| o.getClass().equals(ArrayCreation.class)
				|| o.getClass().equals(ClassInstanceCreation.class)
				|| o.getClass().equals(ArrayAccess.class) || o.getClass().equals(FieldAccess.class)
				|| o.getClass().equals(SuperFieldAccess.class) || o.getClass().equals(ParenthesizedExpression.class)
				|| o.getClass().equals(SimpleName.class) || o.getClass().equals(QualifiedName.class)
				|| o.getClass().equals(CastExpression.class) || o.getClass().equals(InfixExpression.class)
				|| o.getClass().equals(PrefixExpression.class) || o.getClass().equals(InstanceofExpression.class)
				|| o.getClass().equals(ThisExpression.class) || o.getClass().equals(ConditionalExpression.class))
			return true;
		return false;
	}

	protected ITypeBinding getTypeBinding(Object o) {
		if(o.getClass().equals(MethodInvocation.class)) {
			MethodInvocation methodInvocation = (MethodInvocation) o;
			return methodInvocation.resolveMethodBinding().getReturnType();
		}
		else if(o.getClass().equals(SuperMethodInvocation.class)) {
			SuperMethodInvocation superMethodInvocation = (SuperMethodInvocation) o;
			return superMethodInvocation.resolveMethodBinding().getReturnType();
		}
		else if(o.getClass().equals(NumberLiteral.class)) {
			NumberLiteral numberLiteral = (NumberLiteral) o;
			return numberLiteral.resolveTypeBinding();
		}
		else if(o.getClass().equals(StringLiteral.class)) {
			StringLiteral stringLiteral = (StringLiteral) o;
			return stringLiteral.resolveTypeBinding();
		}
		else if(o.getClass().equals(CharacterLiteral.class)) {
			CharacterLiteral characterLiteral = (CharacterLiteral) o;
			return characterLiteral.resolveTypeBinding();
		}
		else if(o.getClass().equals(BooleanLiteral.class)) {
			BooleanLiteral booleanLiteral = (BooleanLiteral) o;
			return booleanLiteral.resolveTypeBinding();
		}
		else if(o.getClass().equals(TypeLiteral.class)) {
			TypeLiteral typeLiteral = (TypeLiteral) o;
			return typeLiteral.resolveTypeBinding();
		}
		else if(o.getClass().equals(ArrayCreation.class)) {
			ArrayCreation arrayCreation = (ArrayCreation) o;
			return arrayCreation.resolveTypeBinding();
		}
		else if(o.getClass().equals(ClassInstanceCreation.class)) {
			ClassInstanceCreation classInstanceCreation = (ClassInstanceCreation) o;
			return classInstanceCreation.resolveTypeBinding();
		}
		else if(o.getClass().equals(ArrayAccess.class)) {
			ArrayAccess arrayAccess = (ArrayAccess) o;
			return arrayAccess.resolveTypeBinding();
		}
		else if(o.getClass().equals(FieldAccess.class)) {
			FieldAccess fieldAccess = (FieldAccess) o;
			return fieldAccess.resolveTypeBinding();
		}
		else if(o.getClass().equals(SuperFieldAccess.class)) {
			SuperFieldAccess superFieldAccess = (SuperFieldAccess) o;
			return superFieldAccess.resolveTypeBinding();
		}
		else if(o.getClass().equals(SimpleName.class)) {
			SimpleName simpleName = (SimpleName) o;
			return simpleName.resolveTypeBinding();
		}
		else if(o.getClass().equals(QualifiedName.class)) {
			QualifiedName qualifiedName = (QualifiedName) o;
			return qualifiedName.resolveTypeBinding();
		}
		else if(o.getClass().equals(CastExpression.class)) {
			CastExpression castExpression = (CastExpression) o;
			return castExpression.resolveTypeBinding();
		}
		else if(o.getClass().equals(InfixExpression.class)) {
			InfixExpression infixExpression = (InfixExpression) o;
			return infixExpression.resolveTypeBinding();
		}
		else if(o.getClass().equals(NullLiteral.class)) {
			NullLiteral nullLiteral = (NullLiteral) o;
			ASTNode parent = ((ASTNode)o).getParent();
			List<Expression> arguments = null;
			IMethodBinding methodBinding = null;
			if(parent instanceof MethodInvocation) {
				MethodInvocation parentMethodInvocation = (MethodInvocation)parent;
				arguments = parentMethodInvocation.arguments();
				methodBinding = parentMethodInvocation.resolveMethodBinding();
			}
			else if(parent instanceof SuperMethodInvocation) {
				SuperMethodInvocation parentMethodInvocation = (SuperMethodInvocation)parent;
				arguments = parentMethodInvocation.arguments();
				methodBinding = parentMethodInvocation.resolveMethodBinding();
			}
			else if(parent instanceof ClassInstanceCreation) {
				ClassInstanceCreation parentClassInstanceCreation = (ClassInstanceCreation)parent;
				arguments = parentClassInstanceCreation.arguments();
				methodBinding = parentClassInstanceCreation.resolveConstructorBinding();
			}
			if(arguments != null && methodBinding != null) {
				int argumentPosition = 0;
				for(Expression argument : arguments) {
					if(argument.equals(o)) {
						ITypeBinding[] parameterTypeBindings = methodBinding.getParameterTypes();
						//analyze only if the argument does not correspond to a varargs parameter
						if(argumentPosition < parameterTypeBindings.length) {
							return parameterTypeBindings[argumentPosition];
						}
					}
					argumentPosition++;
				}
			}
			return nullLiteral.resolveTypeBinding();
		}
		else if(o.getClass().equals(ParenthesizedExpression.class)) {
			ParenthesizedExpression expression = (ParenthesizedExpression) o;
			return expression.resolveTypeBinding();
		}
		else if(o.getClass().equals(PrefixExpression.class)) {
			PrefixExpression expression = (PrefixExpression) o;
			return expression.resolveTypeBinding();
		}
		else if(o.getClass().equals(InstanceofExpression.class)) {
			InstanceofExpression expression = (InstanceofExpression) o;
			return expression.resolveTypeBinding();
		}
		else if(o.getClass().equals(ThisExpression.class)) {
			ThisExpression expression = (ThisExpression) o;
			return expression.resolveTypeBinding();
		}
		else if(o.getClass().equals(ConditionalExpression.class)) {
			ConditionalExpression expression = (ConditionalExpression) o;
			return expression.resolveTypeBinding();
		}
		return null;
	}

	protected boolean typeBindingMatch(ITypeBinding binding1, ITypeBinding binding2) {
		//if bindings are both null then they were recovered from SimpleName expressions representing labels
		if(binding1 == null && binding2 == null)
			return true;
		if(binding1 != null && binding1.isAnonymous() && binding2 != null && binding2.isAnonymous()) {
			ITypeBinding[] interfaces1 = binding1.getInterfaces();
			ITypeBinding[] interfaces2 = binding2.getInterfaces();
			if(interfaces1.length == interfaces2.length) {
				for(int i=0; i<interfaces1.length; i++) {
					ITypeBinding interface1 = interfaces1[i];
					ITypeBinding interface2 = interfaces2[i];
					if(subclassTypeMismatch(interface1, interface2)) {
						return false;
					}
				}
				//all interface bindings are equal
				return true;
			}
			else {
				//different number of implemented interfaces
				return false;
			}
		}
		if(binding1.isCapture() && binding2.isCapture()) {
			ITypeBinding wildcardTypeBinding1 = binding1.getWildcard();
			ITypeBinding wildcardTypeBinding2 = binding2.getWildcard();
			if(wildcardTypeBinding1.isEqualTo(wildcardTypeBinding2) && wildcardTypeBinding1.getQualifiedName().equals(wildcardTypeBinding2.getQualifiedName()))
				return true;
		}
		if(binding1.isParameterizedType() && binding2.isParameterizedType()) {
			ITypeBinding[] typeArguments1 = binding1.getTypeArguments();
			ITypeBinding[] typeArguments2 = binding2.getTypeArguments();
			boolean allTypeArgumentsMatch = true;
			if(typeArguments1.length == typeArguments2.length) {
				int i = 0;
				for(ITypeBinding typeArgument1 : typeArguments1) {
					ITypeBinding typeArgument2 = typeArguments2[i];
					if(!typeBindingMatch(typeArgument1, typeArgument2)) {
						allTypeArgumentsMatch = false;
						break;
					}
					i++;
				}
			}
			else {
				allTypeArgumentsMatch = false;
			}
			ITypeBinding declarationTypeBinding1 = binding1.getTypeDeclaration();
			ITypeBinding declarationTypeBinding2 = binding2.getTypeDeclaration();
			boolean declarationTypeMatch = typeBindingMatch(declarationTypeBinding1, declarationTypeBinding2);
			if(declarationTypeMatch && allTypeArgumentsMatch)
				return true;
		}
		if(binding1.isEqualTo(binding2) && binding1.getQualifiedName().equals(binding2.getQualifiedName()))
			return true;
		if(binding1.getQualifiedName().equals("java.lang.Number") && isNumberPrimitiveType(binding2))
			return true;
		if(isNumberPrimitiveType(binding1) && binding2.getQualifiedName().equals("java.lang.Number"))
			return true;
		if(binding1.getName().equals("float") && binding2.getName().equals("double")) {
			return true;
		}
		if(binding1.getName().equals("double") && binding2.getName().equals("float")) {
			return true;
		}
		if(binding1.getName().equals("int") && binding2.getName().equals("byte")) {
			return true;
		}
		if(binding1.getName().equals("byte") && binding2.getName().equals("int")) {
			return true;
		}
		if(binding1.getName().equals("null") && !binding2.isPrimitive()) {
			return true;
		}
		if(binding2.getName().equals("null") && !binding1.isPrimitive()) {
			return true;
		}
		ITypeBinding commonSuperType = commonSuperType(binding1, binding2);
		return validCommonSuperType(commonSuperType);
	}

	private boolean subclassTypeMismatch(ITypeBinding nodeTypeBinding, ITypeBinding otherTypeBinding) {
		if(nodeTypeBinding.isParameterizedType() && otherTypeBinding.isParameterizedType()) {
			ITypeBinding declarationTypeBinding1 = nodeTypeBinding.getTypeDeclaration();
			ITypeBinding declarationTypeBinding2 = otherTypeBinding.getTypeDeclaration();
			return !declarationTypeBinding1.isEqualTo(declarationTypeBinding2) || !typeBindingMatch(nodeTypeBinding, otherTypeBinding);
		}
		return !nodeTypeBinding.isEqualTo(otherTypeBinding) || !nodeTypeBinding.getQualifiedName().equals(otherTypeBinding.getQualifiedName());
	}

	private static boolean isNumberPrimitiveType(ITypeBinding typeBinding) {
		if(typeBinding.isPrimitive()) {
			String name = typeBinding.getQualifiedName();
			if(name.equals("byte") || name.equals("double") || name.equals("float") || name.equals("int") || name.equals("long") || name.equals("short"))
				return true;
		}
		return false;
	}

	public static boolean validCommonSuperType(ITypeBinding commonSuperType) {
		if(commonSuperType != null && !isTaggingInterface(commonSuperType))
			return true;
		return false;
	}

	public static boolean isTaggingInterface(ITypeBinding typeBinding) {
		return typeBinding.getQualifiedName().equals("java.lang.Object") ||
				typeBinding.getQualifiedName().equals("java.io.Serializable") ||
				typeBinding.getQualifiedName().equals("java.lang.Runnable") ||
				typeBinding.getQualifiedName().equals("java.lang.Comparable") ||
				typeBinding.getQualifiedName().equals("java.lang.Cloneable") ||
				typeBinding.getQualifiedName().equals("java.util.EventListener");
	}

	public static ITypeBinding commonSuperType(ITypeBinding typeBinding1, ITypeBinding typeBinding2) {
		if(typeBinding1.getQualifiedName().equals("java.lang.Number") && isNumberPrimitiveType(typeBinding2))
			return typeBinding1;
		if(isNumberPrimitiveType(typeBinding1) && typeBinding2.getQualifiedName().equals("java.lang.Number"))
			return typeBinding2;
		Set<ITypeBinding> superTypes1 = getAllSuperTypes(typeBinding1);
		Set<ITypeBinding> superTypes2 = getAllSuperTypes(typeBinding2);
		for(ITypeBinding superType2 : superTypes2) {
			if(superType2.getQualifiedName().equals(typeBinding1.getQualifiedName()) || superType2.getErasure().getQualifiedName().equals(typeBinding1.getQualifiedName()) ||
					implementsInterface(superType2, typeBinding1) || implementsInterface(superType2.getErasure(), typeBinding1))
				return typeBinding1;
		}
		for(ITypeBinding superType1 : superTypes1) {
			if(superType1.getQualifiedName().equals(typeBinding2.getQualifiedName()) || superType1.getErasure().getQualifiedName().equals(typeBinding2.getQualifiedName()) ||
					implementsInterface(superType1, typeBinding2) || implementsInterface(superType1.getErasure(), typeBinding2))
				return typeBinding2;
		}
		List<ITypeBinding> typeBindings = new ArrayList<ITypeBinding>();
		for(ITypeBinding superType1 : superTypes1) {
			for(ITypeBinding superType2 : superTypes2) {
				if(superType1.getQualifiedName().equals(superType2.getQualifiedName()) &&
						!superType1.getQualifiedName().equals("java.lang.Object")) {
					addTypeBinding(superType1, typeBindings);
				}
			}
		}
		if(typeBindings.size() > 1) {
			TypeBindingInheritanceDetection inheritanceDetection = new TypeBindingInheritanceDetection(typeBindings);
			Set<String> leaves = inheritanceDetection.getLeavesInDeepestLevels();
			if(leaves.isEmpty()) {
				return typeBindings.get(0);
			}
			else {
				List<ITypeBinding> leafTypeBindings = new ArrayList<ITypeBinding>();
				for(String leaf : leaves) {
					for(ITypeBinding typeBinding : typeBindings) {
						if(leaf.equals(typeBinding.getQualifiedName())) {
							leafTypeBindings.add(typeBinding);
							break;
						}
					}
				}
				//return the first leaf that is a system class, if no system class is found return the first leaf that is a system interface
				for(ITypeBinding leafTypeBinding : leafTypeBindings) {
					if(leafTypeBinding.isClass()) {
						return leafTypeBinding;
					}
				}
				for(ITypeBinding leafTypeBinding : leafTypeBindings) {
					if(leafTypeBinding.isInterface() && ASTReader.getSystemObject().getClassObject(leafTypeBinding.getQualifiedName()) != null) {
						return leafTypeBinding;
					}
				}
				return leafTypeBindings.get(0);
			}
		}
		else if(typeBindings.size() == 1) {
			return typeBindings.get(0);
		}
		else {
			if(superTypes1.size() == 1 && superTypes2.size() == 1) {
				for(ITypeBinding superType1 : superTypes1) {
					for(ITypeBinding superType2 : superTypes2) {
						if(superType1.getQualifiedName().equals("java.lang.Object") &&
								superType2.getQualifiedName().equals("java.lang.Object")) {
							return superType1;
						}
					}
				}
			}
			if(superTypes1.size() == 1) {
				for(ITypeBinding superType1 : superTypes1) {
					if(superType1.getQualifiedName().equals("java.lang.Object"))
						return superType1;
				}
			}
			if(superTypes2.size() == 1) {
				for(ITypeBinding superType2 : superTypes2) {
					if(superType2.getQualifiedName().equals("java.lang.Object"))
						return superType2;
				}
			}
			return null;
		}
	}

	public static boolean implementsInterface(ITypeBinding typeBinding, ITypeBinding interfaceType) {
		ITypeBinding[] implementedInterfaces = typeBinding.getInterfaces();
		for(ITypeBinding implementedInterface : implementedInterfaces) {
			if(implementedInterface.getQualifiedName().equals(interfaceType.getQualifiedName()))
				return true;
		}
		return false;
	}

	private static void addTypeBinding(ITypeBinding typeBinding, List<ITypeBinding> typeBindings) {
		boolean found = false;
		for(ITypeBinding typeBinding2 : typeBindings) {
			if(typeBinding.isEqualTo(typeBinding2) && typeBinding.getQualifiedName().equals(typeBinding2.getQualifiedName())) {
				found = true;
				break;
			}
		}
		if(!found) {
			typeBindings.add(typeBinding);
		}
	}

	private static Set<ITypeBinding> getAllSuperTypes(ITypeBinding typeBinding) {
		Set<ITypeBinding> superTypes = new LinkedHashSet<ITypeBinding>();
		ITypeBinding superTypeBinding = typeBinding.getSuperclass();
		if(superTypeBinding != null) {
			superTypes.add(superTypeBinding);
			superTypes.addAll(getAllSuperTypes(superTypeBinding));
		}
		ITypeBinding[] superInterfaces = typeBinding.getInterfaces();
		for(ITypeBinding superInterface : superInterfaces) {
			superTypes.add(superInterface);
			superTypes.addAll(getAllSuperTypes(superInterface));
		}
		return superTypes;
	}

	protected boolean isInfixExpressionWithCompositeParent(ASTNode node) {
		if(node instanceof InfixExpression &&
				(node.getParent() instanceof IfStatement || node.getParent() instanceof InfixExpression ||
				node.getParent() instanceof WhileStatement || node.getParent() instanceof DoStatement ||
				node.getParent() instanceof ForStatement)) {
			return true;
		}
		return false;
	}

	private void processClassInstanceCreationArguments(List<Expression> nodeArguments, List<Expression> otherArguments,
			ASTNodeDifference astNodeDifference, String nodeToString, String otherToString, boolean identicalConstructorErasureType) {
		if(identicalConstructorErasureType) {
			if(nodeArguments.size() != otherArguments.size()) {
				Difference diff = new Difference(nodeToString,otherToString,DifferenceType.ARGUMENT_NUMBER_MISMATCH);
				int size1 = nodeArguments.size() == 0 ? 1 : nodeArguments.size();
				int size2 = otherArguments.size() == 0 ? 1 : otherArguments.size();
				diff.setWeight(size1 * size2);
				astNodeDifference.addDifference(diff);
			}
			else {
				for(int i=0; i<nodeArguments.size(); i++) {
					int differenceCountBefore = differences.size();
					safeSubtreeMatch(nodeArguments.get(i), otherArguments.get(i));
					reduceWeightOfReversedArguments(differenceCountBefore);
				}
			}
		}
	}

	private void processMethodInvocationArguments(List<Expression> nodeArguments, List<Expression> otherArguments,
			ASTNodeDifference astNodeDifference, String nodeToString, String otherToString, boolean overloadedMethods) {
		if(nodeArguments.size() != otherArguments.size()) {
			Difference diff = new Difference(nodeToString,otherToString,DifferenceType.ARGUMENT_NUMBER_MISMATCH);
			if(!overloadedMethods) {
				int size1 = nodeArguments.size() == 0 ? 1 : nodeArguments.size();
				int size2 = otherArguments.size() == 0 ? 1 : otherArguments.size();
				diff.setWeight(size1 * size2);
			}
			astNodeDifference.addDifference(diff);
		}
		else {
			for(int i=0; i<nodeArguments.size(); i++) {
				int differenceCountBefore = differences.size();
				safeSubtreeMatch(nodeArguments.get(i), otherArguments.get(i));
				reduceWeightOfReversedArguments(differenceCountBefore);
			}
		}
	}

	private boolean overloadedMethods(IMethodBinding methodBinding1, IMethodBinding methodBinding2) {
		List<ITypeBinding> parameterTypes1 = new ArrayList<ITypeBinding>(Arrays.asList(methodBinding1.getParameterTypes()));
		List<ITypeBinding> parameterTypes2 = new ArrayList<ITypeBinding>(Arrays.asList(methodBinding2.getParameterTypes()));
		return methodBinding1.getDeclaringClass().isEqualTo(methodBinding2.getDeclaringClass()) && methodBinding1.getName().equals(methodBinding2.getName()) &&
				(parameterTypes1.containsAll(parameterTypes2) || parameterTypes2.containsAll(parameterTypes1));
	}

	private static boolean isExpressionWithinMethodInvocationArgument(ASTNode expression) {
		ASTNode parent = expression.getParent();
		while(parent != null) {
			if(parent instanceof MethodInvocation) {
				MethodInvocation methodInvocation = (MethodInvocation)parent;
				List<Expression> arguments = methodInvocation.arguments();
				for(Expression argument : arguments) {
					if(argument.equals(expression)) {
						return true;
					}
				}
			}
			else if(parent instanceof SuperMethodInvocation) {
				SuperMethodInvocation methodInvocation = (SuperMethodInvocation)parent;
				List<Expression> arguments = methodInvocation.arguments();
				for(Expression argument : arguments) {
					if(argument.equals(expression)) {
						return true;
					}
				}
			}
			else if(parent instanceof ClassInstanceCreation) {
				ClassInstanceCreation classInstanceCreation = (ClassInstanceCreation)parent;
				List<Expression> arguments = classInstanceCreation.arguments();
				for(Expression argument : arguments) {
					if(argument.equals(expression)) {
						return true;
					}
				}
			}
			expression = parent;
			parent = parent.getParent();
		}
		return false;
	}

	public boolean match(ArrayAccess node, Object other) {
		ASTInformationGenerator.setCurrentITypeRoot(typeRoot1);
		AbstractExpression exp1 = new AbstractExpression(node);
		ASTInformationGenerator.setCurrentITypeRoot(typeRoot2);
		AbstractExpression exp2 = new AbstractExpression((Expression)other);
		if(isInfixExpressionWithCompositeParent((ASTNode)other)) {
			return super.match(node, other);
		}
		ASTNodeDifference astNodeDifference = new ASTNodeDifference(exp1, exp2);
		if(isTypeHolder(other)) {
			boolean typeMatch = typeBindingMatch(node.resolveTypeBinding(), getTypeBinding(other));
			if (!(other instanceof ArrayAccess)) {
				if(typeMatch) {
					Difference diff = new Difference(node.toString(),other.toString(),DifferenceType.TYPE_COMPATIBLE_REPLACEMENT,astNodeDifference.getWeight());
					astNodeDifference.addDifference(diff);
					addDifference(astNodeDifference);
				}
				else {
					Difference diff = new Difference(node.toString(),other.toString(),DifferenceType.AST_TYPE_MISMATCH);
					astNodeDifference.addDifference(diff);
					addDifference(astNodeDifference);
				}
			}
			else {
				ArrayAccess o = (ArrayAccess) other;
				safeSubtreeMatch(node.getArray(), o.getArray());
				safeSubtreeMatch(node.getIndex(), o.getIndex());
			}
			return typeMatch;
		}
		Difference diff = new Difference(node.toString(),other.toString(),DifferenceType.AST_TYPE_MISMATCH);
		astNodeDifference.addDifference(diff);
		addDifference(astNodeDifference);
		return false;
	}

	public boolean match(ArrayCreation node, Object other) {
		ASTInformationGenerator.setCurrentITypeRoot(typeRoot1);
		AbstractExpression exp1 = new AbstractExpression(node);
		ASTInformationGenerator.setCurrentITypeRoot(typeRoot2);
		AbstractExpression exp2 = new AbstractExpression((Expression)other);
		if(isInfixExpressionWithCompositeParent((ASTNode)other)) {
			return super.match(node, other);
		}
		ASTNodeDifference astNodeDifference = new ASTNodeDifference(exp1, exp2);
		if(isTypeHolder(other)) {
			boolean typeMatch = typeBindingMatch(node.resolveTypeBinding(), getTypeBinding(other));
			if (!(other instanceof ArrayCreation)) {
				if(typeMatch) {
					Difference diff = new Difference(node.toString(),other.toString(),DifferenceType.TYPE_COMPATIBLE_REPLACEMENT,astNodeDifference.getWeight());
					astNodeDifference.addDifference(diff);
				}
				else {
					Difference diff = new Difference(node.toString(),other.toString(),DifferenceType.AST_TYPE_MISMATCH);
					astNodeDifference.addDifference(diff);
				}
			}
			else {
				ArrayCreation o = (ArrayCreation) other;
