org.eclipse.jdt.ui/core refactoring/org/eclipse/jdt/internal/corext/refactoring/generics/InferTypeArgumentsConstraintsSolver.java - jdt/eclipse.jdt.ui - Git at Google

 /*******************************************************************************
  * Copyright (c) 2000, 2006 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
  *******************************************************************************/

 package org.eclipse.jdt.internal.corext.refactoring.generics;


 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;

 import org.eclipse.core.runtime.IProgressMonitor;
 import org.eclipse.core.runtime.OperationCanceledException;
 import org.eclipse.core.runtime.SubProgressMonitor;

 import org.eclipse.jdt.core.IJavaProject;
 import org.eclipse.jdt.core.dom.ITypeBinding;

 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.types.ArrayType;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.types.HierarchyType;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.types.TType;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.types.TypeEnvironment;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.typesets.EnumeratedTypeSet;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.typesets.SingletonTypeSet;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.typesets.TypeSet;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.typesets.TypeSetEnvironment;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.ArrayElementVariable2;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.ArrayTypeVariable2;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.CastVariable2;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.CollectionElementVariable2;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.ConstraintVariable2;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.ITypeConstraint2;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.IndependentTypeVariable2;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.TTypes;
 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.TypeEquivalenceSet;


 public class InferTypeArgumentsConstraintsSolver {

 	private static class TTypeComparator implements Comparator {
 		public int compare(Object o1, Object o2) {
 			return ((TType) o1).getPrettySignature().compareTo(((TType) o2).getPrettySignature());
 		}
 		public static TTypeComparator INSTANCE= new TTypeComparator();
 	}

 	private final static String CHOSEN_TYPE= "chosenType"; //$NON-NLS-1$

 	private final InferTypeArgumentsTCModel fTCModel;
 	private TypeSetEnvironment fTypeSetEnvironment;

 	/**
 	 * The work-list used by the type constraint solver to hold the set of
 	 * nodes in the constraint graph that remain to be (re-)processed. Entries
 	 * are <code>ConstraintVariable2</code>s.
 	 */
 	private LinkedList/*<ConstraintVariable2>*/ fWorkList;

 	private InferTypeArgumentsUpdate fUpdate;


 	public InferTypeArgumentsConstraintsSolver(InferTypeArgumentsTCModel typeConstraintFactory) {
 		fTCModel= typeConstraintFactory;
 		fWorkList= new LinkedList();
 	}

 	public InferTypeArgumentsUpdate solveConstraints(IProgressMonitor pm) {
 		pm.beginTask("", 2); //$NON-NLS-1$
 		fUpdate= new InferTypeArgumentsUpdate();

 		ConstraintVariable2[] allConstraintVariables= fTCModel.getAllConstraintVariables();
 		if (allConstraintVariables.length == 0)
 			return fUpdate;

 		fTypeSetEnvironment= new TypeSetEnvironment(fTCModel.getTypeEnvironment());
 		ParametricStructureComputer parametricStructureComputer= new ParametricStructureComputer(allConstraintVariables, fTCModel);
 		Collection/*<CollectionElementVariable2>*/ newVars= parametricStructureComputer.createElemConstraintVariables();

 		ArrayList newAllConstraintVariables= new ArrayList();
 		newAllConstraintVariables.addAll(Arrays.asList(allConstraintVariables));
 		newAllConstraintVariables.addAll(newVars);
 		allConstraintVariables= (ConstraintVariable2[]) newAllConstraintVariables.toArray(new ConstraintVariable2[newAllConstraintVariables.size()]);


 		//loop over all TypeEquivalenceSets and unify the elements from the fElemStructureEnv with the existing TypeEquivalenceSets
 		HashSet allTypeEquivalenceSets= new HashSet();
 		for (int i= 0; i < allConstraintVariables.length; i++) {
 			TypeEquivalenceSet typeEquivalenceSet= allConstraintVariables[i].getTypeEquivalenceSet();
 			if (typeEquivalenceSet != null)
 				allTypeEquivalenceSets.add(typeEquivalenceSet);
 		}
 		for (Iterator iter= allTypeEquivalenceSets.iterator(); iter.hasNext();) {
 			TypeEquivalenceSet typeEquivalenceSet= (TypeEquivalenceSet) iter.next();
 			ConstraintVariable2[] contributingVariables= typeEquivalenceSet.getContributingVariables();
 			for (int i= 0; i < contributingVariables.length; i++) {
 				for (int j= i + 1; j < contributingVariables.length; j++) {
 					ConstraintVariable2 first= contributingVariables[i];
 					ConstraintVariable2 second= contributingVariables[j];
 					fTCModel.createElementEqualsConstraints(first, second); // recursively
 				}
 			}
 		}
 		ITypeConstraint2[] allTypeConstraints= fTCModel.getAllTypeConstraints();
 		for (int i= 0; i < allTypeConstraints.length; i++) {
 			ITypeConstraint2 typeConstraint= allTypeConstraints[i];
 			fTCModel.createElementEqualsConstraints(typeConstraint.getLeft(), typeConstraint.getRight());
 		}

 		initializeTypeEstimates(allConstraintVariables);
 		if (pm.isCanceled())
 			throw new OperationCanceledException();
 		fWorkList.addAll(Arrays.asList(allConstraintVariables));
 		runSolver(new SubProgressMonitor(pm, 1));
 		chooseTypes(allConstraintVariables, new SubProgressMonitor(pm, 1));
 		findCastsToRemove(fTCModel.getCastVariables());
 		return fUpdate;
 	}

 	private void initializeTypeEstimates(ConstraintVariable2[] allConstraintVariables) {
 		for (int i= 0; i < allConstraintVariables.length; i++) {
 			ConstraintVariable2 cv= allConstraintVariables[i];
 			//TODO: not necessary for types that are not used in a TypeConstraint but only as type in CollectionElementVariable
 			//TODO: handle nested element variables; see ParametricStructureComputer.createAndInitVars()
 			TypeEquivalenceSet set= cv.getTypeEquivalenceSet();
 			if (set == null) {
 				set= new TypeEquivalenceSet(cv);
 				set.setTypeEstimate(createInitialEstimate(cv));
 				cv.setTypeEquivalenceSet(set);
 			} else {
 				TypeSet typeEstimate= (TypeSet) cv.getTypeEstimate();
 				if (typeEstimate == null) {
 					ConstraintVariable2[] cvs= set.getContributingVariables();
 					typeEstimate= fTypeSetEnvironment.getUniverseTypeSet();
 					for (int j= 0; j < cvs.length; j++) //TODO: optimize: just try to find an immutable CV; if not found, use Universe
 						typeEstimate= typeEstimate.intersectedWith(createInitialEstimate(cvs[j]));
 					set.setTypeEstimate(typeEstimate);
 				}
 			}
 		}
 	}

 	private TypeSet createInitialEstimate(ConstraintVariable2 cv) {
 		// TODO: check assumption: only immutable CVs have a type
 //		ParametricStructure parametricStructure= fElemStructureEnv.elemStructure(cv);
 //		if (parametricStructure != null && parametricStructure != ParametricStructureComputer.ParametricStructure.NONE) {
 //			return SubTypesOfSingleton.create(parametricStructure.getBase());
 //		}

 		TType type= cv.getType();
 		if (type == null) {
 			return fTypeSetEnvironment.getUniverseTypeSet();

 		} else if (cv instanceof IndependentTypeVariable2) {
 			return fTypeSetEnvironment.getUniverseTypeSet();
 			//TODO: solve problem with recursive bounds
 //			TypeVariable tv= (TypeVariable) type;
 //			TType[] bounds= tv.getBounds();
 //			TypeSet result= SubTypesOfSingleton.create(bounds[0].getErasure());
 //			for (int i= 1; i < bounds.length; i++) {
 //				result= result.intersectedWith(SubTypesOfSingleton.create(bounds[i].getErasure()));
 //			}
 //			return result;

 		} else if (cv instanceof ArrayTypeVariable2) {
 			return fTypeSetEnvironment.getUniverseTypeSet();
 		} else if (cv instanceof ArrayElementVariable2) {
 			if (cv.getType() != null && cv.getType().isTypeVariable()) {
 				return fTypeSetEnvironment.getUniverseTypeSet();
 			} else {
 				return new SingletonTypeSet(type, fTypeSetEnvironment);
 			}

 		} else if (type.isVoidType()) {
 			return fTypeSetEnvironment.getEmptyTypeSet();
 		} else {
 			return new SingletonTypeSet(type, fTypeSetEnvironment);
 		}
 	}

 	private void runSolver(SubProgressMonitor pm) {
 		pm.beginTask("", fWorkList.size() * 3); //$NON-NLS-1$
 		while (! fWorkList.isEmpty()) {
 			// Get a variable whose type estimate has changed
 			ConstraintVariable2 cv= (ConstraintVariable2) fWorkList.removeFirst();
 			List/*<ITypeConstraint2>*/ usedIn= fTCModel.getUsedIn(cv);
 			processConstraints(usedIn, cv);
 			pm.worked(1);
 			if (pm.isCanceled())
 				throw new OperationCanceledException();
 		}
 		pm.done();
 	}

 	/**
 	 * Given a list of <code>ITypeConstraint2</code>s that all refer to a
 	 * given <code>ConstraintVariable2</code> (whose type bound has presumably
 	 * just changed), process each <code>ITypeConstraint</code>, propagating
 	 * the type bound across the constraint as needed.
 	 *
 	 * @param usedIn the <code>List</code> of <code>ITypeConstraint2</code>s
 	 * to process
 	 * @param changedCv the constraint variable whose type bound has changed
 	 */
 	private void processConstraints(List/*<ITypeConstraint2>*/ usedIn, ConstraintVariable2 changedCv) {
 		int i= 0;
 		for (Iterator iter= usedIn.iterator(); iter.hasNext(); i++) {
 			ITypeConstraint2 tc= (ITypeConstraint2) iter.next();

 				maintainSimpleConstraint(changedCv, tc);
 				//TODO: prune tcs which cannot cause further changes
 				// Maybe these should be pruned after a special first loop over all ConstraintVariables,
 				// Since this can only happen once for every CV in the work list.
 //				if (isConstantConstraint(stc))
 //					fTypeConstraintFactory.removeUsedIn(stc, changedCv);
 		}
 	}

 	private void maintainSimpleConstraint(ConstraintVariable2 changedCv, ITypeConstraint2 stc) {
 		ConstraintVariable2 left= stc.getLeft();
 		ConstraintVariable2 right= stc.getRight();

 		TypeEquivalenceSet leftSet= left.getTypeEquivalenceSet();
 		TypeEquivalenceSet rightSet= right.getTypeEquivalenceSet();
 		TypeSet leftEstimate= (TypeSet) leftSet.getTypeEstimate();
 		TypeSet rightEstimate= (TypeSet) rightSet.getTypeEstimate();

 		if (leftEstimate.isUniverse() && rightEstimate.isUniverse())
 			return; // nothing to do

 		if (leftEstimate.equals(rightEstimate))
 			return; // nothing to do

 		TypeSet lhsSuperTypes= leftEstimate.superTypes();
 		TypeSet rhsSubTypes= rightEstimate.subTypes();

 		if (! rhsSubTypes.containsAll(leftEstimate)) {
 			TypeSet xsection= leftEstimate.intersectedWith(rhsSubTypes);

 //			if (xsection.isEmpty()) // too bad, but this can happen
 //				throw new IllegalStateException("Type estimate set is now empty for LHS in " + left + " <= " + right + "; estimates were " + leftEstimate + " <= " + rightEstimate); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$

 			leftSet.setTypeEstimate(xsection);
 			fWorkList.addAll(Arrays.asList(leftSet.getContributingVariables()));
 		}
 		if (! lhsSuperTypes.containsAll(rightEstimate)) {
 			TypeSet xsection= rightEstimate.intersectedWith(lhsSuperTypes);

 //			if (xsection.isEmpty())
 //				throw new IllegalStateException("Type estimate set is now empty for RHS in " + left + " <= " + right + "; estimates were " + leftEstimate + " <= " + rightEstimate); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$

 			rightSet.setTypeEstimate(xsection);
 			fWorkList.addAll(Arrays.asList(rightSet.getContributingVariables()));
 		}
 	}

 	private void chooseTypes(ConstraintVariable2[] allConstraintVariables, SubProgressMonitor pm) {
 		pm.beginTask("", allConstraintVariables.length); //$NON-NLS-1$
 		for (int i= 0; i < allConstraintVariables.length; i++) {
 			ConstraintVariable2 cv= allConstraintVariables[i];

 			TypeEquivalenceSet set= cv.getTypeEquivalenceSet();
 			if (set == null)
 				continue; //TODO: should not happen iff all unused constraint variables got pruned
 			//TODO: should calculate only once per EquivalenceRepresentative; can throw away estimate TypeSet afterwards
 			TType type= chooseSingleType((TypeSet) cv.getTypeEstimate()); //TODO: is null for Universe TypeSet
 			setChosenType(cv, type);

 			if (cv instanceof CollectionElementVariable2) {
 				CollectionElementVariable2 elementCv= (CollectionElementVariable2) cv;
 				fUpdate.addDeclaration(elementCv);
 			}

 			pm.worked(1);
 			if (pm.isCanceled())
 				throw new OperationCanceledException();
 		}
 		pm.done();
 	}

 	private TType chooseSingleType(TypeSet typeEstimate) {
 		if (typeEstimate.isUniverse() || typeEstimate.isEmpty()) {
 			return null;

 		} else if (typeEstimate.hasUniqueLowerBound()) {
 			return typeEstimate.uniqueLowerBound();

 		} else {
 			EnumeratedTypeSet lowerBound= typeEstimate.lowerBound().enumerate();
 			ArrayList/*<TType>*/ interfaceCandidates= null;
 			for (Iterator iter= lowerBound.iterator(); iter.hasNext();) {
 				TType type= (TType) iter.next();
 				if (! type.isInterface()) {
 					return type;
 				} else {
 					if (interfaceCandidates == null)
 						interfaceCandidates= new ArrayList(2);
 					interfaceCandidates.add(type);
 				}
 			}

 			if (interfaceCandidates == null || interfaceCandidates.size() == 0) {
 				return null;
 			} else if (interfaceCandidates.size() == 1) {
 				return (TType) interfaceCandidates.get(0);
 			} else {
 				ArrayList nontaggingCandidates= getNonTaggingInterfaces(interfaceCandidates);
 				if (nontaggingCandidates.size() != 0) {
 					return (TType) Collections.min(nontaggingCandidates, TTypeComparator.INSTANCE);
 				} else {
 					return (TType) Collections.min(interfaceCandidates, TTypeComparator.INSTANCE);
 				}
 			}
 		}
 	}

 	private static final int MAX_CACHE= 1024;
 	private Map/*<TType, Boolean>*/ fInterfaceTaggingCache= new LinkedHashMap(MAX_CACHE, 0.75f, true) {
 		private static final long serialVersionUID= 1L;
 		protected boolean removeEldestEntry(Map.Entry eldest) {
 			return size() > MAX_CACHE;
 		}
 	};

 	private ArrayList getNonTaggingInterfaces(ArrayList interfaceCandidates) {
 		ArrayList unresolvedTypes= new ArrayList();
 		ArrayList nonTagging= new ArrayList();

 		for (int i= 0; i < interfaceCandidates.size(); i++) {
 			TType interf= (TType) interfaceCandidates.get(i);
 			Object isTagging= fInterfaceTaggingCache.get(interf);
 			if (isTagging == null)
 				unresolvedTypes.add(interf);
 			else if (isTagging == Boolean.FALSE)
 				nonTagging.add(interf);
 		}

 		if (unresolvedTypes.size() != 0) {
 			TType[] interfaces= (TType[]) unresolvedTypes.toArray(new TType[unresolvedTypes.size()]);
 			HierarchyType firstInterface= (HierarchyType) interfaces[0];
 			IJavaProject javaProject= firstInterface.getJavaElementType().getJavaProject();
 			ITypeBinding[] interfaceBindings= TypeEnvironment.createTypeBindings(interfaces, javaProject); //expensive...
 			for (int i= 0; i < interfaceBindings.length; i++) {
 				if (interfaceBindings[i].getDeclaredMethods().length == 0) {
 					fInterfaceTaggingCache.put(interfaces[i], Boolean.TRUE);
 				} else {
 					fInterfaceTaggingCache.put(interfaces[i], Boolean.FALSE);
 					nonTagging.add(interfaces[i]);
 				}
 			}
 		}

 		return nonTagging;
 	}

 	private void findCastsToRemove(CastVariable2[] castVariables) {
 		for (int i= 0; i < castVariables.length; i++) {
 			CastVariable2 castCv= castVariables[i];
 			ConstraintVariable2 expressionVariable= castCv.getExpressionVariable();
 			TType chosenType= InferTypeArgumentsConstraintsSolver.getChosenType(expressionVariable);
 			TType castType= castCv.getType();
 			TType expressionType= expressionVariable.getType();
 			if (chosenType != null && TTypes.canAssignTo(chosenType, castType)) {
 				if (chosenType.equals(expressionType))
 					continue; // The type has not changed. Don't remove the cast, since it could be
 							   // there to get access to default-visible members or to
 							   // unify types of conditional expressions.
 				fUpdate.addCastToRemove(castCv);

 			} else if (expressionVariable instanceof ArrayTypeVariable2 && castType.isArrayType()) { // bug 97258
 				ArrayElementVariable2 arrayElementCv= fTCModel.getArrayElementVariable(expressionVariable);
 				if (arrayElementCv == null)
 					continue;
 				TType chosenArrayElementType= InferTypeArgumentsConstraintsSolver.getChosenType(arrayElementCv);
 				if (chosenArrayElementType != null && TTypes.canAssignTo(chosenArrayElementType, ((ArrayType) castType).getComponentType())) {
 					if (expressionType instanceof ArrayType && chosenArrayElementType.equals(((ArrayType) expressionType).getComponentType()))
 						continue; // The type has not changed. Don't remove the cast, since it could be
 								   // there to unify types of conditional expressions.
 					fUpdate.addCastToRemove(castCv);
 				}
 			}
 		}
 	}

 	public static TType getChosenType(ConstraintVariable2 cv) {
 		TType type= (TType) cv.getData(CHOSEN_TYPE);
 		if (type != null)
 			return type;
 		TypeEquivalenceSet set= cv.getTypeEquivalenceSet();
 		if (set == null) { //TODO: should not have to set this here. Clean up when caching chosen type
 			return null;
 //			// no representative == no restriction
 //			set= new TypeEquivalenceSet(cv);
 //			set.setTypeEstimate(TypeUniverseSet.create());
 //			cv.setTypeEquivalenceSet(set);
 		}
 		return cv.getTypeEstimate().chooseSingleType();
 	}

 	private static void setChosenType(ConstraintVariable2 cv, TType type) {
 		cv.setData(CHOSEN_TYPE, type);
 	}
 }
	/*******************************************************************************
	* Copyright (c) 2000, 2006 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
	*******************************************************************************/

	package org.eclipse.jdt.internal.corext.refactoring.generics;


	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collection;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.HashSet;
	import java.util.Iterator;
	import java.util.LinkedHashMap;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Map;

	import org.eclipse.core.runtime.IProgressMonitor;
	import org.eclipse.core.runtime.OperationCanceledException;
	import org.eclipse.core.runtime.SubProgressMonitor;

	import org.eclipse.jdt.core.IJavaProject;
	import org.eclipse.jdt.core.dom.ITypeBinding;

	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.types.ArrayType;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.types.HierarchyType;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.types.TType;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.types.TypeEnvironment;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.typesets.EnumeratedTypeSet;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.typesets.SingletonTypeSet;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.typesets.TypeSet;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.typesets.TypeSetEnvironment;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.ArrayElementVariable2;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.ArrayTypeVariable2;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.CastVariable2;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.CollectionElementVariable2;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.ConstraintVariable2;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.ITypeConstraint2;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.IndependentTypeVariable2;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.TTypes;
	import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.TypeEquivalenceSet;


	public class InferTypeArgumentsConstraintsSolver {

	private static class TTypeComparator implements Comparator {
	public int compare(Object o1, Object o2) {
	return ((TType) o1).getPrettySignature().compareTo(((TType) o2).getPrettySignature());
	}
	public static TTypeComparator INSTANCE= new TTypeComparator();
	}

	private final static String CHOSEN_TYPE= "chosenType"; //$NON-NLS-1$

	private final InferTypeArgumentsTCModel fTCModel;
	private TypeSetEnvironment fTypeSetEnvironment;

	/**
	* The work-list used by the type constraint solver to hold the set of
	* nodes in the constraint graph that remain to be (re-)processed. Entries
	* are <code>ConstraintVariable2</code>s.
	*/
	private LinkedList/<ConstraintVariable2>/ fWorkList;

	private InferTypeArgumentsUpdate fUpdate;


	public InferTypeArgumentsConstraintsSolver(InferTypeArgumentsTCModel typeConstraintFactory) {
	fTCModel= typeConstraintFactory;
	fWorkList= new LinkedList();
	}

	public InferTypeArgumentsUpdate solveConstraints(IProgressMonitor pm) {
	pm.beginTask("", 2); //$NON-NLS-1$
	fUpdate= new InferTypeArgumentsUpdate();

	ConstraintVariable2[] allConstraintVariables= fTCModel.getAllConstraintVariables();
	if (allConstraintVariables.length == 0)
	return fUpdate;

	fTypeSetEnvironment= new TypeSetEnvironment(fTCModel.getTypeEnvironment());
	ParametricStructureComputer parametricStructureComputer= new ParametricStructureComputer(allConstraintVariables, fTCModel);
	Collection/<CollectionElementVariable2>/ newVars= parametricStructureComputer.createElemConstraintVariables();

	ArrayList newAllConstraintVariables= new ArrayList();
	newAllConstraintVariables.addAll(Arrays.asList(allConstraintVariables));
	newAllConstraintVariables.addAll(newVars);
	allConstraintVariables= (ConstraintVariable2[]) newAllConstraintVariables.toArray(new ConstraintVariable2[newAllConstraintVariables.size()]);


	//loop over all TypeEquivalenceSets and unify the elements from the fElemStructureEnv with the existing TypeEquivalenceSets
	HashSet allTypeEquivalenceSets= new HashSet();
	for (int i= 0; i < allConstraintVariables.length; i++) {
	TypeEquivalenceSet typeEquivalenceSet= allConstraintVariables[i].getTypeEquivalenceSet();
	if (typeEquivalenceSet != null)
	allTypeEquivalenceSets.add(typeEquivalenceSet);
	}
	for (Iterator iter= allTypeEquivalenceSets.iterator(); iter.hasNext();) {
	TypeEquivalenceSet typeEquivalenceSet= (TypeEquivalenceSet) iter.next();
	ConstraintVariable2[] contributingVariables= typeEquivalenceSet.getContributingVariables();
	for (int i= 0; i < contributingVariables.length; i++) {
	for (int j= i + 1; j < contributingVariables.length; j++) {
	ConstraintVariable2 first= contributingVariables[i];
	ConstraintVariable2 second= contributingVariables[j];
	fTCModel.createElementEqualsConstraints(first, second); // recursively
	}
	}
	}
	ITypeConstraint2[] allTypeConstraints= fTCModel.getAllTypeConstraints();
	for (int i= 0; i < allTypeConstraints.length; i++) {
	ITypeConstraint2 typeConstraint= allTypeConstraints[i];
	fTCModel.createElementEqualsConstraints(typeConstraint.getLeft(), typeConstraint.getRight());
	}

	initializeTypeEstimates(allConstraintVariables);
	if (pm.isCanceled())
	throw new OperationCanceledException();
	fWorkList.addAll(Arrays.asList(allConstraintVariables));
	runSolver(new SubProgressMonitor(pm, 1));
	chooseTypes(allConstraintVariables, new SubProgressMonitor(pm, 1));
	findCastsToRemove(fTCModel.getCastVariables());
	return fUpdate;
	}

	private void initializeTypeEstimates(ConstraintVariable2[] allConstraintVariables) {
	for (int i= 0; i < allConstraintVariables.length; i++) {
	ConstraintVariable2 cv= allConstraintVariables[i];
	//TODO: not necessary for types that are not used in a TypeConstraint but only as type in CollectionElementVariable
	//TODO: handle nested element variables; see ParametricStructureComputer.createAndInitVars()
	TypeEquivalenceSet set= cv.getTypeEquivalenceSet();
	if (set == null) {
	set= new TypeEquivalenceSet(cv);
	set.setTypeEstimate(createInitialEstimate(cv));
	cv.setTypeEquivalenceSet(set);
	} else {
	TypeSet typeEstimate= (TypeSet) cv.getTypeEstimate();
	if (typeEstimate == null) {
	ConstraintVariable2[] cvs= set.getContributingVariables();
	typeEstimate= fTypeSetEnvironment.getUniverseTypeSet();
	for (int j= 0; j < cvs.length; j++) //TODO: optimize: just try to find an immutable CV; if not found, use Universe
	typeEstimate= typeEstimate.intersectedWith(createInitialEstimate(cvs[j]));
	set.setTypeEstimate(typeEstimate);
	}
	}
	}
	}

	private TypeSet createInitialEstimate(ConstraintVariable2 cv) {
	// TODO: check assumption: only immutable CVs have a type
	// ParametricStructure parametricStructure= fElemStructureEnv.elemStructure(cv);
	// if (parametricStructure != null && parametricStructure != ParametricStructureComputer.ParametricStructure.NONE) {
	// return SubTypesOfSingleton.create(parametricStructure.getBase());
	// }

	TType type= cv.getType();
	if (type == null) {
	return fTypeSetEnvironment.getUniverseTypeSet();

	} else if (cv instanceof IndependentTypeVariable2) {
	return fTypeSetEnvironment.getUniverseTypeSet();
	//TODO: solve problem with recursive bounds
	// TypeVariable tv= (TypeVariable) type;
	// TType[] bounds= tv.getBounds();
	// TypeSet result= SubTypesOfSingleton.create(bounds[0].getErasure());
	// for (int i= 1; i < bounds.length; i++) {
	// result= result.intersectedWith(SubTypesOfSingleton.create(bounds[i].getErasure()));
	// }
	// return result;

	} else if (cv instanceof ArrayTypeVariable2) {
	return fTypeSetEnvironment.getUniverseTypeSet();
	} else if (cv instanceof ArrayElementVariable2) {
	if (cv.getType() != null && cv.getType().isTypeVariable()) {
	return fTypeSetEnvironment.getUniverseTypeSet();
	} else {
	return new SingletonTypeSet(type, fTypeSetEnvironment);
	}

	} else if (type.isVoidType()) {
	return fTypeSetEnvironment.getEmptyTypeSet();
	} else {
	return new SingletonTypeSet(type, fTypeSetEnvironment);
	}
	}

	private void runSolver(SubProgressMonitor pm) {
	pm.beginTask("", fWorkList.size() * 3); //$NON-NLS-1$
	while (! fWorkList.isEmpty()) {
	// Get a variable whose type estimate has changed
	ConstraintVariable2 cv= (ConstraintVariable2) fWorkList.removeFirst();
	List/<ITypeConstraint2>/ usedIn= fTCModel.getUsedIn(cv);
	processConstraints(usedIn, cv);
	pm.worked(1);
	if (pm.isCanceled())
	throw new OperationCanceledException();
	}
	pm.done();
	}

	/**
	* Given a list of <code>ITypeConstraint2</code>s that all refer to a
	* given <code>ConstraintVariable2</code> (whose type bound has presumably
	* just changed), process each <code>ITypeConstraint</code>, propagating
	* the type bound across the constraint as needed.
	*
	* @param usedIn the <code>List</code> of <code>ITypeConstraint2</code>s
	* to process
	* @param changedCv the constraint variable whose type bound has changed
	*/
	private void processConstraints(List/<ITypeConstraint2>/ usedIn, ConstraintVariable2 changedCv) {
	int i= 0;
	for (Iterator iter= usedIn.iterator(); iter.hasNext(); i++) {
	ITypeConstraint2 tc= (ITypeConstraint2) iter.next();

	maintainSimpleConstraint(changedCv, tc);
	//TODO: prune tcs which cannot cause further changes
	// Maybe these should be pruned after a special first loop over all ConstraintVariables,
	// Since this can only happen once for every CV in the work list.
	// if (isConstantConstraint(stc))
	// fTypeConstraintFactory.removeUsedIn(stc, changedCv);
	}
	}

	private void maintainSimpleConstraint(ConstraintVariable2 changedCv, ITypeConstraint2 stc) {
	ConstraintVariable2 left= stc.getLeft();
	ConstraintVariable2 right= stc.getRight();

	TypeEquivalenceSet leftSet= left.getTypeEquivalenceSet();
	TypeEquivalenceSet rightSet= right.getTypeEquivalenceSet();
	TypeSet leftEstimate= (TypeSet) leftSet.getTypeEstimate();
	TypeSet rightEstimate= (TypeSet) rightSet.getTypeEstimate();

	if (leftEstimate.isUniverse() && rightEstimate.isUniverse())
	return; // nothing to do

	if (leftEstimate.equals(rightEstimate))
	return; // nothing to do

	TypeSet lhsSuperTypes= leftEstimate.superTypes();
	TypeSet rhsSubTypes= rightEstimate.subTypes();

	if (! rhsSubTypes.containsAll(leftEstimate)) {
	TypeSet xsection= leftEstimate.intersectedWith(rhsSubTypes);

	// if (xsection.isEmpty()) // too bad, but this can happen
	// throw new IllegalStateException("Type estimate set is now empty for LHS in " + left + " <= " + right + "; estimates were " + leftEstimate + " <= " + rightEstimate); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$

	leftSet.setTypeEstimate(xsection);
	fWorkList.addAll(Arrays.asList(leftSet.getContributingVariables()));
	}
	if (! lhsSuperTypes.containsAll(rightEstimate)) {
	TypeSet xsection= rightEstimate.intersectedWith(lhsSuperTypes);

	// if (xsection.isEmpty())
	// throw new IllegalStateException("Type estimate set is now empty for RHS in " + left + " <= " + right + "; estimates were " + leftEstimate + " <= " + rightEstimate); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$

	rightSet.setTypeEstimate(xsection);
	fWorkList.addAll(Arrays.asList(rightSet.getContributingVariables()));
	}
	}

	private void chooseTypes(ConstraintVariable2[] allConstraintVariables, SubProgressMonitor pm) {
	pm.beginTask("", allConstraintVariables.length); //$NON-NLS-1$
	for (int i= 0; i < allConstraintVariables.length; i++) {
	ConstraintVariable2 cv= allConstraintVariables[i];

	TypeEquivalenceSet set= cv.getTypeEquivalenceSet();
	if (set == null)
	continue; //TODO: should not happen iff all unused constraint variables got pruned
	//TODO: should calculate only once per EquivalenceRepresentative; can throw away estimate TypeSet afterwards
	TType type= chooseSingleType((TypeSet) cv.getTypeEstimate()); //TODO: is null for Universe TypeSet
	setChosenType(cv, type);

	if (cv instanceof CollectionElementVariable2) {
	CollectionElementVariable2 elementCv= (CollectionElementVariable2) cv;
	fUpdate.addDeclaration(elementCv);
	}

	pm.worked(1);
	if (pm.isCanceled())
	throw new OperationCanceledException();
	}
	pm.done();
	}

	private TType chooseSingleType(TypeSet typeEstimate) {
	if (typeEstimate.isUniverse() \|\| typeEstimate.isEmpty()) {
	return null;

	} else if (typeEstimate.hasUniqueLowerBound()) {
	return typeEstimate.uniqueLowerBound();

	} else {
	EnumeratedTypeSet lowerBound= typeEstimate.lowerBound().enumerate();
	ArrayList/<TType>/ interfaceCandidates= null;
	for (Iterator iter= lowerBound.iterator(); iter.hasNext();) {
	TType type= (TType) iter.next();
	if (! type.isInterface()) {
	return type;
	} else {
	if (interfaceCandidates == null)
	interfaceCandidates= new ArrayList(2);
	interfaceCandidates.add(type);
	}
	}

	if (interfaceCandidates == null \|\| interfaceCandidates.size() == 0) {
	return null;
	} else if (interfaceCandidates.size() == 1) {
	return (TType) interfaceCandidates.get(0);
	} else {
	ArrayList nontaggingCandidates= getNonTaggingInterfaces(interfaceCandidates);
	if (nontaggingCandidates.size() != 0) {
	return (TType) Collections.min(nontaggingCandidates, TTypeComparator.INSTANCE);
	} else {
	return (TType) Collections.min(interfaceCandidates, TTypeComparator.INSTANCE);
	}
	}
	}
	}

	private static final int MAX_CACHE= 1024;
	private Map/<TType, Boolean>/ fInterfaceTaggingCache= new LinkedHashMap(MAX_CACHE, 0.75f, true) {
	private static final long serialVersionUID= 1L;
	protected boolean removeEldestEntry(Map.Entry eldest) {
	return size() > MAX_CACHE;
	}
	};

	private ArrayList getNonTaggingInterfaces(ArrayList interfaceCandidates) {
	ArrayList unresolvedTypes= new ArrayList();
	ArrayList nonTagging= new ArrayList();

	for (int i= 0; i < interfaceCandidates.size(); i++) {
	TType interf= (TType) interfaceCandidates.get(i);
	Object isTagging= fInterfaceTaggingCache.get(interf);
	if (isTagging == null)
	unresolvedTypes.add(interf);
	else if (isTagging == Boolean.FALSE)
	nonTagging.add(interf);
	}

	if (unresolvedTypes.size() != 0) {
	TType[] interfaces= (TType[]) unresolvedTypes.toArray(new TType[unresolvedTypes.size()]);
	HierarchyType firstInterface= (HierarchyType) interfaces[0];
	IJavaProject javaProject= firstInterface.getJavaElementType().getJavaProject();
	ITypeBinding[] interfaceBindings= TypeEnvironment.createTypeBindings(interfaces, javaProject); //expensive...
	for (int i= 0; i < interfaceBindings.length; i++) {
	if (interfaceBindings[i].getDeclaredMethods().length == 0) {
	fInterfaceTaggingCache.put(interfaces[i], Boolean.TRUE);
	} else {
	fInterfaceTaggingCache.put(interfaces[i], Boolean.FALSE);
	nonTagging.add(interfaces[i]);
	}
	}
	}

	return nonTagging;
	}

	private void findCastsToRemove(CastVariable2[] castVariables) {
	for (int i= 0; i < castVariables.length; i++) {
	CastVariable2 castCv= castVariables[i];
	ConstraintVariable2 expressionVariable= castCv.getExpressionVariable();
	TType chosenType= InferTypeArgumentsConstraintsSolver.getChosenType(expressionVariable);
	TType castType= castCv.getType();
	TType expressionType= expressionVariable.getType();
	if (chosenType != null && TTypes.canAssignTo(chosenType, castType)) {
	if (chosenType.equals(expressionType))
	continue; // The type has not changed. Don't remove the cast, since it could be
	// there to get access to default-visible members or to
	// unify types of conditional expressions.
	fUpdate.addCastToRemove(castCv);

	} else if (expressionVariable instanceof ArrayTypeVariable2 && castType.isArrayType()) { // bug 97258
	ArrayElementVariable2 arrayElementCv= fTCModel.getArrayElementVariable(expressionVariable);
	if (arrayElementCv == null)
	continue;
	TType chosenArrayElementType= InferTypeArgumentsConstraintsSolver.getChosenType(arrayElementCv);
	if (chosenArrayElementType != null && TTypes.canAssignTo(chosenArrayElementType, ((ArrayType) castType).getComponentType())) {
	if (expressionType instanceof ArrayType && chosenArrayElementType.equals(((ArrayType) expressionType).getComponentType()))
	continue; // The type has not changed. Don't remove the cast, since it could be
	// there to unify types of conditional expressions.
	fUpdate.addCastToRemove(castCv);
	}
	}
	}
	}

	public static TType getChosenType(ConstraintVariable2 cv) {
	TType type= (TType) cv.getData(CHOSEN_TYPE);
	if (type != null)
	return type;
	TypeEquivalenceSet set= cv.getTypeEquivalenceSet();
	if (set == null) { //TODO: should not have to set this here. Clean up when caching chosen type
	return null;
	// // no representative == no restriction
	// set= new TypeEquivalenceSet(cv);
	// set.setTypeEstimate(TypeUniverseSet.create());
	// cv.setTypeEquivalenceSet(set);
	}
	return cv.getTypeEstimate().chooseSingleType();
	}

	private static void setChosenType(ConstraintVariable2 cv, TType type) {
	cv.setData(CHOSEN_TYPE, type);
	}
	}