KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > jdt > internal > corext > refactoring > generics > InferTypeArgumentsConstraintsSolver


1 /*******************************************************************************
2  * Copyright (c) 2000, 2006 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/

11
12 package org.eclipse.jdt.internal.corext.refactoring.generics;
13
14
15 import java.util.ArrayList JavaDoc;
16 import java.util.Arrays JavaDoc;
17 import java.util.Collection JavaDoc;
18 import java.util.Collections JavaDoc;
19 import java.util.Comparator JavaDoc;
20 import java.util.HashSet JavaDoc;
21 import java.util.Iterator JavaDoc;
22 import java.util.LinkedHashMap JavaDoc;
23 import java.util.LinkedList JavaDoc;
24 import java.util.List JavaDoc;
25 import java.util.Map JavaDoc;
26
27 import org.eclipse.core.runtime.IProgressMonitor;
28 import org.eclipse.core.runtime.OperationCanceledException;
29 import org.eclipse.core.runtime.SubProgressMonitor;
30
31 import org.eclipse.jdt.core.IJavaProject;
32 import org.eclipse.jdt.core.dom.ITypeBinding;
33
34 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.types.ArrayType;
35 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.types.HierarchyType;
36 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.types.TType;
37 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.types.TypeEnvironment;
38 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.typesets.EnumeratedTypeSet;
39 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.typesets.SingletonTypeSet;
40 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.typesets.TypeSet;
41 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints.typesets.TypeSetEnvironment;
42 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.ArrayElementVariable2;
43 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.ArrayTypeVariable2;
44 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.CastVariable2;
45 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.CollectionElementVariable2;
46 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.ConstraintVariable2;
47 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.ITypeConstraint2;
48 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.IndependentTypeVariable2;
49 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.TTypes;
50 import org.eclipse.jdt.internal.corext.refactoring.typeconstraints2.TypeEquivalenceSet;
51
52
53 public class InferTypeArgumentsConstraintsSolver {
54
55     private static class TTypeComparator implements Comparator JavaDoc {
56         public int compare(Object JavaDoc o1, Object JavaDoc o2) {
57             return ((TType) o1).getPrettySignature().compareTo(((TType) o2).getPrettySignature());
58         }
59         public static TTypeComparator INSTANCE= new TTypeComparator();
60     }
61     
62     private final static String JavaDoc CHOSEN_TYPE= "chosenType"; //$NON-NLS-1$
63

64     private final InferTypeArgumentsTCModel fTCModel;
65     private TypeSetEnvironment fTypeSetEnvironment;
66     
67     /**
68      * The work-list used by the type constraint solver to hold the set of
69      * nodes in the constraint graph that remain to be (re-)processed. Entries
70      * are <code>ConstraintVariable2</code>s.
71      */

72     private LinkedList JavaDoc/*<ConstraintVariable2>*/ fWorkList;
73     
74     private InferTypeArgumentsUpdate fUpdate;
75     
76     
77     public InferTypeArgumentsConstraintsSolver(InferTypeArgumentsTCModel typeConstraintFactory) {
78         fTCModel= typeConstraintFactory;
79         fWorkList= new LinkedList JavaDoc();
80     }
81     
82     public InferTypeArgumentsUpdate solveConstraints(IProgressMonitor pm) {
83         pm.beginTask("", 2); //$NON-NLS-1$
84
fUpdate= new InferTypeArgumentsUpdate();
85         
86         ConstraintVariable2[] allConstraintVariables= fTCModel.getAllConstraintVariables();
87         if (allConstraintVariables.length == 0)
88             return fUpdate;
89         
90         fTypeSetEnvironment= new TypeSetEnvironment(fTCModel.getTypeEnvironment());
91         ParametricStructureComputer parametricStructureComputer= new ParametricStructureComputer(allConstraintVariables, fTCModel);
92         Collection JavaDoc/*<CollectionElementVariable2>*/ newVars= parametricStructureComputer.createElemConstraintVariables();
93         
94         ArrayList JavaDoc newAllConstraintVariables= new ArrayList JavaDoc();
95         newAllConstraintVariables.addAll(Arrays.asList(allConstraintVariables));
96         newAllConstraintVariables.addAll(newVars);
97         allConstraintVariables= (ConstraintVariable2[]) newAllConstraintVariables.toArray(new ConstraintVariable2[newAllConstraintVariables.size()]);
98         
99         
100         //loop over all TypeEquivalenceSets and unify the elements from the fElemStructureEnv with the existing TypeEquivalenceSets
101
HashSet JavaDoc allTypeEquivalenceSets= new HashSet JavaDoc();
102         for (int i= 0; i < allConstraintVariables.length; i++) {
103             TypeEquivalenceSet typeEquivalenceSet= allConstraintVariables[i].getTypeEquivalenceSet();
104             if (typeEquivalenceSet != null)
105                 allTypeEquivalenceSets.add(typeEquivalenceSet);
106         }
107         for (Iterator JavaDoc iter= allTypeEquivalenceSets.iterator(); iter.hasNext();) {
108             TypeEquivalenceSet typeEquivalenceSet= (TypeEquivalenceSet) iter.next();
109             ConstraintVariable2[] contributingVariables= typeEquivalenceSet.getContributingVariables();
110             for (int i= 0; i < contributingVariables.length; i++) {
111                 for (int j= i + 1; j < contributingVariables.length; j++) {
112                     ConstraintVariable2 first= contributingVariables[i];
113                     ConstraintVariable2 second= contributingVariables[j];
114                     fTCModel.createElementEqualsConstraints(first, second); // recursively
115
}
116             }
117         }
118         ITypeConstraint2[] allTypeConstraints= fTCModel.getAllTypeConstraints();
119         for (int i= 0; i < allTypeConstraints.length; i++) {
120             ITypeConstraint2 typeConstraint= allTypeConstraints[i];
121             fTCModel.createElementEqualsConstraints(typeConstraint.getLeft(), typeConstraint.getRight());
122         }
123         
124         initializeTypeEstimates(allConstraintVariables);
125         if (pm.isCanceled())
126             throw new OperationCanceledException();
127         fWorkList.addAll(Arrays.asList(allConstraintVariables));
128         runSolver(new SubProgressMonitor(pm, 1));
129         chooseTypes(allConstraintVariables, new SubProgressMonitor(pm, 1));
130         findCastsToRemove(fTCModel.getCastVariables());
131         return fUpdate;
132     }
133
134     private void initializeTypeEstimates(ConstraintVariable2[] allConstraintVariables) {
135         for (int i= 0; i < allConstraintVariables.length; i++) {
136             ConstraintVariable2 cv= allConstraintVariables[i];
137             //TODO: not necessary for types that are not used in a TypeConstraint but only as type in CollectionElementVariable
138
//TODO: handle nested element variables; see ParametricStructureComputer.createAndInitVars()
139
TypeEquivalenceSet set= cv.getTypeEquivalenceSet();
140             if (set == null) {
141                 set= new TypeEquivalenceSet(cv);
142                 set.setTypeEstimate(createInitialEstimate(cv));
143                 cv.setTypeEquivalenceSet(set);
144             } else {
145                 TypeSet typeEstimate= (TypeSet) cv.getTypeEstimate();
146                 if (typeEstimate == null) {
147                     ConstraintVariable2[] cvs= set.getContributingVariables();
148                     typeEstimate= fTypeSetEnvironment.getUniverseTypeSet();
149                     for (int j= 0; j < cvs.length; j++) //TODO: optimize: just try to find an immutable CV; if not found, use Universe
150
typeEstimate= typeEstimate.intersectedWith(createInitialEstimate(cvs[j]));
151                     set.setTypeEstimate(typeEstimate);
152                 }
153             }
154         }
155     }
156
157     private TypeSet createInitialEstimate(ConstraintVariable2 cv) {
158         // TODO: check assumption: only immutable CVs have a type
159
// ParametricStructure parametricStructure= fElemStructureEnv.elemStructure(cv);
160
// if (parametricStructure != null && parametricStructure != ParametricStructureComputer.ParametricStructure.NONE) {
161
// return SubTypesOfSingleton.create(parametricStructure.getBase());
162
// }
163

164         TType type= cv.getType();
165         if (type == null) {
166             return fTypeSetEnvironment.getUniverseTypeSet();
167             
168         } else if (cv instanceof IndependentTypeVariable2) {
169             return fTypeSetEnvironment.getUniverseTypeSet();
170             //TODO: solve problem with recursive bounds
171
// TypeVariable tv= (TypeVariable) type;
172
// TType[] bounds= tv.getBounds();
173
// TypeSet result= SubTypesOfSingleton.create(bounds[0].getErasure());
174
// for (int i= 1; i < bounds.length; i++) {
175
// result= result.intersectedWith(SubTypesOfSingleton.create(bounds[i].getErasure()));
176
// }
177
// return result;
178

179         } else if (cv instanceof ArrayTypeVariable2) {
180             return fTypeSetEnvironment.getUniverseTypeSet();
181         } else if (cv instanceof ArrayElementVariable2) {
182             if (cv.getType() != null && cv.getType().isTypeVariable()) {
183                 return fTypeSetEnvironment.getUniverseTypeSet();
184             } else {
185                 return new SingletonTypeSet(type, fTypeSetEnvironment);
186             }
187             
188         } else if (type.isVoidType()) {
189             return fTypeSetEnvironment.getEmptyTypeSet();
190         } else {
191             return new SingletonTypeSet(type, fTypeSetEnvironment);
192         }
193     }
194
195     private void runSolver(SubProgressMonitor pm) {
196         pm.beginTask("", fWorkList.size() * 3); //$NON-NLS-1$
197
while (! fWorkList.isEmpty()) {
198             // Get a variable whose type estimate has changed
199
ConstraintVariable2 cv= (ConstraintVariable2) fWorkList.removeFirst();
200             List JavaDoc/*<ITypeConstraint2>*/ usedIn= fTCModel.getUsedIn(cv);
201             processConstraints(usedIn, cv);
202             pm.worked(1);
203             if (pm.isCanceled())
204                 throw new OperationCanceledException();
205         }
206         pm.done();
207     }
208     
209     /**
210      * Given a list of <code>ITypeConstraint2</code>s that all refer to a
211      * given <code>ConstraintVariable2</code> (whose type bound has presumably
212      * just changed), process each <code>ITypeConstraint</code>, propagating
213      * the type bound across the constraint as needed.
214      *
215      * @param usedIn the <code>List</code> of <code>ITypeConstraint2</code>s
216      * to process
217      * @param changedCv the constraint variable whose type bound has changed
218      */

219     private void processConstraints(List JavaDoc/*<ITypeConstraint2>*/ usedIn, ConstraintVariable2 changedCv) {
220         int i= 0;
221         for (Iterator JavaDoc iter= usedIn.iterator(); iter.hasNext(); i++) {
222             ITypeConstraint2 tc= (ITypeConstraint2) iter.next();
223
224                 maintainSimpleConstraint(changedCv, tc);
225                 //TODO: prune tcs which cannot cause further changes
226
// Maybe these should be pruned after a special first loop over all ConstraintVariables,
227
// Since this can only happen once for every CV in the work list.
228
// if (isConstantConstraint(stc))
229
// fTypeConstraintFactory.removeUsedIn(stc, changedCv);
230
}
231     }
232     
233     private void maintainSimpleConstraint(ConstraintVariable2 changedCv, ITypeConstraint2 stc) {
234         ConstraintVariable2 left= stc.getLeft();
235         ConstraintVariable2 right= stc.getRight();
236
237         TypeEquivalenceSet leftSet= left.getTypeEquivalenceSet();
238         TypeEquivalenceSet rightSet= right.getTypeEquivalenceSet();
239         TypeSet leftEstimate= (TypeSet) leftSet.getTypeEstimate();
240         TypeSet rightEstimate= (TypeSet) rightSet.getTypeEstimate();
241             
242         if (leftEstimate.isUniverse() && rightEstimate.isUniverse())
243             return; // nothing to do
244

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

248         TypeSet lhsSuperTypes= leftEstimate.superTypes();
249         TypeSet rhsSubTypes= rightEstimate.subTypes();
250
251         if (! rhsSubTypes.containsAll(leftEstimate)) {
252             TypeSet xsection= leftEstimate.intersectedWith(rhsSubTypes);
253
254 // if (xsection.isEmpty()) // too bad, but this can happen
255
// 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$
256

257             leftSet.setTypeEstimate(xsection);
258             fWorkList.addAll(Arrays.asList(leftSet.getContributingVariables()));
259         }
260         if (! lhsSuperTypes.containsAll(rightEstimate)) {
261             TypeSet xsection= rightEstimate.intersectedWith(lhsSuperTypes);
262
263 // if (xsection.isEmpty())
264
// 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$
265

266             rightSet.setTypeEstimate(xsection);
267             fWorkList.addAll(Arrays.asList(rightSet.getContributingVariables()));
268         }
269     }
270
271     private void chooseTypes(ConstraintVariable2[] allConstraintVariables, SubProgressMonitor pm) {
272         pm.beginTask("", allConstraintVariables.length); //$NON-NLS-1$
273
for (int i= 0; i < allConstraintVariables.length; i++) {
274             ConstraintVariable2 cv= allConstraintVariables[i];
275                 
276             TypeEquivalenceSet set= cv.getTypeEquivalenceSet();
277             if (set == null)
278                 continue; //TODO: should not happen iff all unused constraint variables got pruned
279
//TODO: should calculate only once per EquivalenceRepresentative; can throw away estimate TypeSet afterwards
280
TType type= chooseSingleType((TypeSet) cv.getTypeEstimate()); //TODO: is null for Universe TypeSet
281
setChosenType(cv, type);
282             
283             if (cv instanceof CollectionElementVariable2) {
284                 CollectionElementVariable2 elementCv= (CollectionElementVariable2) cv;
285                 fUpdate.addDeclaration(elementCv);
286             }
287             
288             pm.worked(1);
289             if (pm.isCanceled())
290                 throw new OperationCanceledException();
291         }
292         pm.done();
293     }
294
295     private TType chooseSingleType(TypeSet typeEstimate) {
296         if (typeEstimate.isUniverse() || typeEstimate.isEmpty()) {
297             return null;
298         
299         } else if (typeEstimate.hasUniqueLowerBound()) {
300             return typeEstimate.uniqueLowerBound();
301         
302         } else {
303             EnumeratedTypeSet lowerBound= typeEstimate.lowerBound().enumerate();
304             ArrayList JavaDoc/*<TType>*/ interfaceCandidates= null;
305             for (Iterator JavaDoc iter= lowerBound.iterator(); iter.hasNext();) {
306                 TType type= (TType) iter.next();
307                 if (! type.isInterface()) {
308                     return type;
309                 } else {
310                     if (interfaceCandidates == null)
311                         interfaceCandidates= new ArrayList JavaDoc(2);
312                     interfaceCandidates.add(type);
313                 }
314             }
315             
316             if (interfaceCandidates == null || interfaceCandidates.size() == 0) {
317                 return null;
318             } else if (interfaceCandidates.size() == 1) {
319                 return (TType) interfaceCandidates.get(0);
320             } else {
321                 ArrayList JavaDoc nontaggingCandidates= getNonTaggingInterfaces(interfaceCandidates);
322                 if (nontaggingCandidates.size() != 0) {
323                     return (TType) Collections.min(nontaggingCandidates, TTypeComparator.INSTANCE);
324                 } else {
325                     return (TType) Collections.min(interfaceCandidates, TTypeComparator.INSTANCE);
326                 }
327             }
328         }
329     }
330
331     private static final int MAX_CACHE= 1024;
332     private Map JavaDoc/*<TType, Boolean>*/ fInterfaceTaggingCache= new LinkedHashMap JavaDoc(MAX_CACHE, 0.75f, true) {
333         private static final long serialVersionUID= 1L;
334         protected boolean removeEldestEntry(Map.Entry JavaDoc eldest) {
335             return size() > MAX_CACHE;
336         }
337     };
338     
339     private ArrayList JavaDoc getNonTaggingInterfaces(ArrayList JavaDoc interfaceCandidates) {
340         ArrayList JavaDoc unresolvedTypes= new ArrayList JavaDoc();
341         ArrayList JavaDoc nonTagging= new ArrayList JavaDoc();
342         
343         for (int i= 0; i < interfaceCandidates.size(); i++) {
344             TType interf= (TType) interfaceCandidates.get(i);
345             Object JavaDoc isTagging= fInterfaceTaggingCache.get(interf);
346             if (isTagging == null)
347                 unresolvedTypes.add(interf);
348             else if (isTagging == Boolean.FALSE)
349                 nonTagging.add(interf);
350         }
351         
352         if (unresolvedTypes.size() != 0) {
353             TType[] interfaces= (TType[]) unresolvedTypes.toArray(new TType[unresolvedTypes.size()]);
354             HierarchyType firstInterface= (HierarchyType) interfaces[0];
355             IJavaProject javaProject= firstInterface.getJavaElementType().getJavaProject();
356             ITypeBinding[] interfaceBindings= TypeEnvironment.createTypeBindings(interfaces, javaProject); //expensive...
357
for (int i= 0; i < interfaceBindings.length; i++) {
358                 if (interfaceBindings[i].getDeclaredMethods().length == 0) {
359                     fInterfaceTaggingCache.put(interfaces[i], Boolean.TRUE);
360                 } else {
361                     fInterfaceTaggingCache.put(interfaces[i], Boolean.FALSE);
362                     nonTagging.add(interfaces[i]);
363                 }
364             }
365         }
366         
367         return nonTagging;
368     }
369
370     private void findCastsToRemove(CastVariable2[] castVariables) {
371         for (int i= 0; i < castVariables.length; i++) {
372             CastVariable2 castCv= castVariables[i];
373             ConstraintVariable2 expressionVariable= castCv.getExpressionVariable();
374             TType chosenType= InferTypeArgumentsConstraintsSolver.getChosenType(expressionVariable);
375             TType castType= castCv.getType();
376             TType expressionType= expressionVariable.getType();
377             if (chosenType != null && TTypes.canAssignTo(chosenType, castType)) {
378                 if (chosenType.equals(expressionType))
379                     continue; // The type has not changed. Don't remove the cast, since it could be
380
// there to get access to default-visible members or to
381
// unify types of conditional expressions.
382
fUpdate.addCastToRemove(castCv);
383                 
384             } else if (expressionVariable instanceof ArrayTypeVariable2 && castType.isArrayType()) { // bug 97258
385
ArrayElementVariable2 arrayElementCv= fTCModel.getArrayElementVariable(expressionVariable);
386                 if (arrayElementCv == null)
387                     continue;
388                 TType chosenArrayElementType= InferTypeArgumentsConstraintsSolver.getChosenType(arrayElementCv);
389                 if (chosenArrayElementType != null && TTypes.canAssignTo(chosenArrayElementType, ((ArrayType) castType).getComponentType())) {
390                     if (expressionType instanceof ArrayType && chosenArrayElementType.equals(((ArrayType) expressionType).getComponentType()))
391                         continue; // The type has not changed. Don't remove the cast, since it could be
392
// there to unify types of conditional expressions.
393
fUpdate.addCastToRemove(castCv);
394                 }
395             }
396         }
397     }
398
399     public static TType getChosenType(ConstraintVariable2 cv) {
400         TType type= (TType) cv.getData(CHOSEN_TYPE);
401         if (type != null)
402             return type;
403         TypeEquivalenceSet set= cv.getTypeEquivalenceSet();
404         if (set == null) { //TODO: should not have to set this here. Clean up when caching chosen type
405
return null;
406 // // no representative == no restriction
407
// set= new TypeEquivalenceSet(cv);
408
// set.setTypeEstimate(TypeUniverseSet.create());
409
// cv.setTypeEquivalenceSet(set);
410
}
411         return cv.getTypeEstimate().chooseSingleType();
412     }
413
414     private static void setChosenType(ConstraintVariable2 cv, TType type) {
415         cv.setData(CHOSEN_TYPE, type);
416     }
417 }
418
Popular Tags