001    /* Copyright (c) 2005-2008, Torbjorn Ekman
002     * All rights reserved.
003     *
004     * Redistribution and use in source and binary forms, with or without
005     * modification, are permitted provided that the following conditions are met:
006     *
007     * 1. Redistributions of source code must retain the above copyright notice,
008     * this list of conditions and the following disclaimer.
009     *
010     * 2. Redistributions in binary form must reproduce the above copyright notice,
011     * this list of conditions and the following disclaimer in the documentation
012     * and/or other materials provided with the distribution.
013     *
014     * 3. Neither the name of the copyright holder nor the names of its
015     * contributors may be used to endorse or promote products derived from this
016     * software without specific prior written permission.
017     *
018     * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019     * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020     * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021     * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
022     * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
023     * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
024     * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
025     * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
026     * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
027     * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
028     * POSSIBILITY OF SUCH DAMAGE.
029     */
030    
031    import java.util.*;
032    
033    aspect GenericMethodsInference {
034      syn boolean TypeDecl.isUnboxedPrimitive() = this instanceof PrimitiveType && isPrimitive();
035    
036      syn boolean TypeDecl.involvesTypeParameters() circular [false] = false;
037      eq TypeVariable.involvesTypeParameters() = true;
038      eq ArrayDecl.involvesTypeParameters() = componentType().involvesTypeParameters();
039      eq ParClassDecl.involvesTypeParameters() {
040        for (int i = 0; i < getNumArgument(); i++) {
041          if (getArgument(i).type().involvesTypeParameters()) {
042            return true;
043          }
044        }
045        return false;
046      }
047      eq ParInterfaceDecl.involvesTypeParameters() {
048        for (int i = 0; i < getNumArgument(); i++) {
049          if (getArgument(i).type().involvesTypeParameters()) {
050            return true;
051          }
052        }
053        return false;
054      }
055      eq WildcardExtendsType.involvesTypeParameters() = extendsType().involvesTypeParameters();
056      eq WildcardSuperType.involvesTypeParameters() = superType().involvesTypeParameters();
057    
058      inh TypeDecl Expr.assignConvertedType();
059      eq VariableDeclaration.getInit().assignConvertedType() = type();
060      eq FieldDeclaration.getInit().assignConvertedType() = type();
061      eq AssignSimpleExpr.getSource().assignConvertedType() = getDest().type();
062      eq ArrayInit.getInit().assignConvertedType() = declType().componentType();
063      eq ReturnStmt.getResult().assignConvertedType() = returnType();
064      eq Program.getChild().assignConvertedType() = typeNull();
065    
066      eq MethodAccess.getArg().assignConvertedType() = typeObject();
067    
068      inh TypeDecl Expr.typeObject();
069    
070      /**
071       * Infer type arguments based on the actual arguments and result assignment type.
072       */
073      public Collection<TypeDecl> Expr.computeConstraints(
074          TypeDecl resultType,
075          List<ParameterDeclaration> params,
076          List<Expr> args,
077          List<TypeVariable> typeParams) {
078        Constraints c = new Constraints();
079        // Store type parameters.
080        for (int i = 0; i < typeParams.getNumChild(); i++) {
081          c.addTypeVariable(typeParams.getChild(i));
082        }
083    
084        // Add initial constraints.
085        for (int i = 0; i < args.getNumChild(); i++) {
086          TypeDecl A = args.getChild(i).type();
087          int index = i >= params.getNumChild() ? params.getNumChild() - 1 : i;
088          TypeDecl F = params.getChild(index).type();
089          if (params.getChild(index) instanceof VariableArityParameterDeclaration
090             && (args.getNumChild() != params.getNumChild() || !A.isArrayDecl())) {
091            F = F.componentType();
092          }
093          c.convertibleTo(A, F);
094        }
095    
096        if (c.rawAccess) {
097          return new ArrayList<TypeDecl>();
098        }
099    
100        //c.printConstraints();
101        //System.err.println("Resolving equality constraints");
102        c.resolveEqualityConstraints();
103        //c.printConstraints();
104    
105        //System.err.println("Resolving supertype constraints");
106        c.resolveSupertypeConstraints();
107        //c.printConstraints();
108    
109        //System.err.println("Resolving unresolved type arguments");
110        //c.resolveBounds();
111        //c.printConstraints();
112    
113        if (c.unresolvedTypeArguments()) {
114          TypeDecl S = assignConvertedType();
115          if (S.isUnboxedPrimitive()) {
116            S = S.boxed();
117          }
118          TypeDecl R = resultType;
119          // TODO: replace all uses of type variables in R with their inferred types
120          TypeDecl Rprime = R;
121          if (R.isVoid()) {
122            R = typeObject();
123          }
124          c.convertibleFrom(S, R);
125          // TODO: additional constraints
126    
127          c.resolveEqualityConstraints();
128          c.resolveSupertypeConstraints();
129          //c.resolveBounds();
130    
131          c.resolveSubtypeConstraints();
132        }
133    
134        return c.typeArguments();
135      }
136    
137      class Constraints {
138        static class ConstraintSet {
139          public Collection supertypeConstraints = new HashSet(4);
140          public Collection subtypeConstraints = new HashSet(4);
141          public Collection equaltypeConstraints = new HashSet(4);
142          public TypeDecl typeArgument;
143        }
144        private Collection typeVariables;
145        private Map constraintsMap;
146        public boolean rawAccess = false;
147    
148        public Constraints() {
149          typeVariables = new ArrayList(4);
150          constraintsMap = new HashMap();
151        }
152    
153        public void addTypeVariable(TypeVariable T) {
154          if (!typeVariables.contains(T)) {
155            typeVariables.add(T);
156            constraintsMap.put(T, new ConstraintSet());
157          }
158        }
159    
160        public boolean unresolvedTypeArguments() {
161          for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
162            TypeVariable T = (TypeVariable) iter.next();
163            ConstraintSet set = (ConstraintSet) constraintsMap.get(T);
164            if (set.typeArgument == null) {
165              return true;
166            }
167          }
168          return false;
169        }
170    
171        public void printConstraints() {
172          System.err.println("Current constraints:");
173          for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
174            TypeVariable T = (TypeVariable) iter.next();
175            ConstraintSet set = (ConstraintSet) constraintsMap.get(T);
176            for (Iterator i2 = set.supertypeConstraints.iterator(); i2.hasNext(); ) {
177              TypeDecl U = (TypeDecl) i2.next();
178              System.err.println("  " + T.fullName() + " :> " + U.fullName());
179            }
180            for (Iterator i2 = set.subtypeConstraints.iterator(); i2.hasNext(); ) {
181              TypeDecl U = (TypeDecl) i2.next();
182              System.err.println("  " + T.fullName() + " <: " + U.fullName());
183            }
184            for (Iterator i2 = set.equaltypeConstraints.iterator(); i2.hasNext(); ) {
185              TypeDecl U = (TypeDecl) i2.next();
186              System.err.println("  " + T.fullName() + " = " + U.fullName());
187            }
188          }
189        }
190    
191    
192        public void resolveBounds() {
193          for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
194            TypeVariable T = (TypeVariable) iter.next();
195            ConstraintSet set = (ConstraintSet) constraintsMap.get(T);
196            if (set.typeArgument == null) {
197              set.typeArgument = T.getTypeBound(0).type();
198            }
199          }
200        }
201    
202        public void resolveEqualityConstraints() {
203          for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
204            TypeVariable T = (TypeVariable) iter.next();
205            ConstraintSet set = (ConstraintSet) constraintsMap.get(T);
206            boolean done = false;
207            for (Iterator i2 = set.equaltypeConstraints.iterator(); !done && i2.hasNext(); ) {
208              TypeDecl U = (TypeDecl) i2.next();
209              if (!typeVariables.contains(U)) {
210                replaceEqualityConstraints(T, U);   // replace equality constraints for other type variables
211                set.equaltypeConstraints.clear();
212                set.equaltypeConstraints.add(U);    // make U is the only equality constraint for T
213                set.typeArgument = U;
214                done = true;                        // continue on next type variable
215              } else if (T == U) {
216                //i2.remove();                        // discard constraint
217              } else {
218                replaceAllConstraints(T, U);         // rewrite all constraints involving T to use U instead
219                done = true;                        // continue on next type variable
220              }
221            }
222            if (set.typeArgument == null && set.equaltypeConstraints.size() == 1 && set.equaltypeConstraints.contains(T)) {
223              set.typeArgument = T;
224            }
225          }
226        }
227    
228        public void replaceEqualityConstraints(TypeDecl before, TypeDecl after) {
229          for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
230            TypeVariable T = (TypeVariable) iter.next();
231            ConstraintSet set = (ConstraintSet) constraintsMap.get(T);
232            replaceConstraints(set.equaltypeConstraints, before, after);
233          }
234        }
235    
236        public void replaceAllConstraints(TypeDecl before, TypeDecl after) {
237          for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
238            TypeVariable T = (TypeVariable) iter.next();
239            ConstraintSet set = (ConstraintSet) constraintsMap.get(T);
240            replaceConstraints(set.supertypeConstraints, before, after);
241            replaceConstraints(set.subtypeConstraints, before, after);
242            replaceConstraints(set.equaltypeConstraints, before, after);
243          }
244        }
245    
246        private void replaceConstraints(Collection constraints, TypeDecl before, TypeDecl after) {
247          Collection newConstraints = new ArrayList();
248          for (Iterator i2 = constraints.iterator(); i2.hasNext(); ) {
249            TypeDecl U = (TypeDecl) i2.next();
250            if (U == before) { //  TODO: fix parameterized type
251              i2.remove();
252              newConstraints.add(after);
253            }
254          }
255          constraints.addAll(newConstraints);
256        }
257    
258        public void resolveSubtypeConstraints() {
259          for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
260            TypeVariable T = (TypeVariable) iter.next();
261            ConstraintSet set = (ConstraintSet) constraintsMap.get(T);
262            if ((!set.subtypeConstraints.isEmpty() || T.getNumTypeBound() > 0) && set.typeArgument == null) {
263              ArrayList bounds = new ArrayList();
264              for (Iterator i2 = set.subtypeConstraints.iterator(); i2.hasNext(); ) {
265                bounds.add(i2.next());
266              }
267              for (int i = 0; i < T.getNumTypeBound(); i++) {
268                bounds.add(T.getTypeBound(i).type());
269              }
270              set.typeArgument = GLBTypeFactory.glb(bounds);
271            }
272          }
273        }
274    
275        public void resolveSupertypeConstraints() {
276          for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
277            TypeVariable T = (TypeVariable) iter.next();
278            ConstraintSet set = (ConstraintSet) constraintsMap.get(T);
279            if (!set.supertypeConstraints.isEmpty() && set.typeArgument == null) {
280              //TypeDecl typeDecl = lub(set.supertypeConstraints);
281              TypeDecl typeDecl = T.lookupLUBType(set.supertypeConstraints).lub();
282              set.typeArgument = typeDecl;
283              /*
284              TypeDecl EC = (TypeDecl) set.supertypeConstraints.get(0);
285              for (Iterator i2 = set.supertypeConstraints.iterator(); i2.hasNext(); ) {
286                TypeDecl U = (TypeDecl) i2.next();
287                TypeDecl ST = U;
288                TypeDecl EST = ST.erasure();
289                EC = intersect(EC, EST);
290              }
291              TypeDecl MEC = EC;
292              //System.err.println(" MEC(" + T.fullName() + ") = " + MEC.fullName());
293              set.typeArgument = MEC;
294              */
295            }
296          }
297        }
298    
299        /*
300        // operates only on erased types. does it matter? (no type variables, no partypedecl)
301        private TypeDecl intersect(TypeDecl t1, TypeDecl t2) {
302          if (t1.instanceOf(t2)) {
303            return t1;
304          } else if (t2.instanceOf(t1)) {
305            return t2;
306          } else {
307            HashSet set = new HashSet();
308            for (Iterator iter = directSupertypes(t1).iterator(); iter.hasNext(); ) {
309              TypeDecl t1Super = (TypeDecl) iter.next();
310              set.add(intersect(t1Super, t2));
311            }
312            if (set.isEmpty()) {
313              throw new Error("Empty intersection of " + t1.fullName() + " and " + t2.fullName());
314            }
315            TypeDecl lowestType = (TypeDecl) set.iterator().next();
316            for (Iterator iter = set.iterator(); iter.hasNext(); ) {
317              TypeDecl type = (TypeDecl) iter.next();
318              if (type.instanceOf(lowestType)) {
319                lowestType = type;
320              } else if (!lowestType.instanceOf(type)) {
321                throw new Error("Several leaf types in intersection, " + lowestType.fullName() + " and " + type.fullName());
322              }
323            }
324            return lowestType;
325          }
326        }
327        */
328    
329        public static HashSet directSupertypes(TypeDecl t) {
330          if (t instanceof ClassDecl) {
331            ClassDecl type = (ClassDecl) t;
332            HashSet set = new HashSet();
333            if (type.hasSuperclass()) {
334              set.add(type.superclass());
335            }
336            for (int i = 0; i < type.getNumImplements(); i++) {
337              set.add(type.getImplements(i).type());
338            }
339            return set;
340          } else if (t instanceof InterfaceDecl) {
341            InterfaceDecl type = (InterfaceDecl) t;
342            HashSet set = new HashSet();
343            for (int i = 0; i < type.getNumSuperInterface(); i++) {
344              set.add(type.getSuperInterface(i).type());
345            }
346            return set;
347          } else if (t instanceof TypeVariable) {
348            TypeVariable type = (TypeVariable) t;
349            HashSet set = new HashSet();
350            for (int i = 0; i < type.getNumTypeBound(); i++) {
351              set.add(type.getTypeBound(i).type());
352            }
353            return set;
354          } else {
355            throw new Error("Operation not supported for " + t.fullName() + ", " + t.getClass().getName());
356          }
357        }
358    
359        public static HashSet parameterizedSupertypes(TypeDecl t) {
360          HashSet result = new HashSet();
361          addParameterizedSupertypes(t, new HashSet(), result);
362          return result;
363        }
364        public static void addParameterizedSupertypes(TypeDecl t, HashSet processed, HashSet result) {
365          if (!processed.contains(t)) {
366            processed.add(t);
367            if (t.isParameterizedType() /*&& !t.isRawType()*/) {
368              result.add(t);
369            }
370            for (Iterator iter = directSupertypes(t).iterator(); iter.hasNext(); ) {
371              TypeDecl typeDecl = (TypeDecl) iter.next();
372              addParameterizedSupertypes(typeDecl, processed, result);
373            }
374          }
375        }
376    
377        public Collection<TypeDecl> typeArguments() {
378          Collection<TypeDecl> list = new ArrayList<TypeDecl>(typeVariables.size());
379          for (Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
380            TypeVariable T = (TypeVariable) iter.next();
381            ConstraintSet set = (ConstraintSet) constraintsMap.get(T);
382            list.add(set.typeArgument);
383          }
384          return list;
385        }
386    
387        public void addSupertypeConstraint(TypeDecl T, TypeDecl A) {
388          ConstraintSet set = (ConstraintSet) constraintsMap.get(T);
389          set.supertypeConstraints.add(A);
390          //System.out.println(T.name() + " :> " + A.fullName());
391        }
392        public void addSubtypeConstraint(TypeDecl T, TypeDecl A) {
393          ConstraintSet set = (ConstraintSet) constraintsMap.get(T);
394          set.subtypeConstraints.add(A);
395          //System.out.println(T.name() + " <: " + A.fullName());
396        }
397        public void addEqualConstraint(TypeDecl T, TypeDecl A) {
398          ConstraintSet set = (ConstraintSet) constraintsMap.get(T);
399          set.equaltypeConstraints.add(A);
400          //System.out.println(T.name() + " = " + A.fullName());
401        }
402    
403        public void convertibleTo(TypeDecl A, TypeDecl F) {
404          //System.out.println("Convertible to called with " + A.fullName() + "(" + A.getClass().getName() + ")" + " and " + F.fullName() + "(" + F.getClass().getName() + ")");
405          // If F does not involve a type parameter Tj then con constraint is implied on Tj
406          if (!F.involvesTypeParameters()) {
407            return;
408          }
409          // If A is the type of null, no constraint is implied on Tj.
410          if (A.isNull()) {
411            return;
412          }
413          // If A is a primitive type, then A is converted to a reference type U via boxing conversion
414          // and this algorithm is applied recursively to the constraint U << F.
415          if (A.isUnboxedPrimitive()) {
416            TypeDecl U = A.boxed();
417            convertibleTo(U, F);
418          }
419          // If F = Tj, then the constrint Tj :> A is implied
420          else if (F instanceof TypeVariable) {
421            if (typeVariables.contains(F)) {
422              addSupertypeConstraint(F, A);
423            }
424          }
425          // If F = U[], where the type U involves Tj, then if A is an array type V[]
426          // or a type variable with an upper bound that is an array type V[],
427          // where V is a reference type, this algorithm is applied recursively
428          // to the constraint V << U
429          else if (F.isArrayDecl()) {
430            //System.out.println("convertibleTo array decl");
431            TypeDecl U = ((ArrayDecl) F).componentType();
432            if (!U.involvesTypeParameters()) {
433              return;
434            }
435            if (A.isArrayDecl()) {
436              TypeDecl V = ((ArrayDecl) A).componentType();
437              if (V.isReferenceType()) {
438                convertibleTo(V, U);
439              }
440            } else if (A.isTypeVariable()) {
441              TypeVariable t = (TypeVariable) A;
442              for (int i = 0; i < t.getNumTypeBound(); i++) {
443                TypeDecl typeBound = t.getTypeBound(i).type();
444                if (typeBound.isArrayDecl() && ((ArrayDecl) typeBound).componentType().isReferenceType()) {
445                  TypeDecl V = ((ArrayDecl) typeBound).componentType();
446                  convertibleTo(V, U);
447                }
448              }
449            }
450          } else if (F instanceof ParTypeDecl && !F.isRawType()) {
451            for (Iterator iter = parameterizedSupertypes(A).iterator(); iter.hasNext(); ) {
452              ParTypeDecl PF = (ParTypeDecl) F;
453              ParTypeDecl PA = (ParTypeDecl) iter.next();
454              if (PF.genericDecl() == PA.genericDecl()) {
455                if (A.isRawType()) {
456                  rawAccess = true;
457                } else
458                for (int i = 0; i < PF.getNumArgument(); i++) {
459                  TypeDecl T = PF.getArgument(i).type();
460                  if (T.involvesTypeParameters()) {
461                    if (!T.isWildcard()) {
462                      TypeDecl U = T;
463                      TypeDecl V = PA.getArgument(i).type();
464                      constraintEqual(V, U);
465                    } else if (T instanceof WildcardExtendsType) {
466                      TypeDecl U = ((WildcardExtendsType) T).getAccess().type();
467                      TypeDecl S = PA.getArgument(i).type();
468                      if (!S.isWildcard()) {
469                        TypeDecl V = S;
470                        convertibleTo(V, U);
471                      } else if (S instanceof WildcardExtendsType) {
472                        TypeDecl V = ((WildcardExtendsType) S).getAccess().type();
473                        convertibleTo(V, U);
474                      }
475                    } else if (T instanceof WildcardSuperType) {
476                      TypeDecl U = ((WildcardSuperType) T).getAccess().type();
477                      TypeDecl S = PA.getArgument(i).type();
478                      if (!S.isWildcard()) {
479                        TypeDecl V = S;
480                        convertibleFrom(V, U);
481                      } else if (S instanceof WildcardSuperType) {
482                        TypeDecl V = ((WildcardSuperType) S).getAccess().type();
483                        convertibleFrom(V, U);
484                      }
485                    }
486                  }
487                }
488              }
489            }
490          }
491        }
492    
493    
494        public void convertibleFrom(TypeDecl A, TypeDecl F) {
495          //System.out.println("ConvertibleFrom called with " + A.fullName() + "(" + A.getClass().getName() + ")" + " and " + F.fullName() + "(" + F.getClass().getName() + ")");
496          // If F does not involve a type parameter Tj then con constraint is implied on Tj
497          if (!F.involvesTypeParameters()) {
498            return;
499          }
500          // If A is the type of null, no constraint is implied on Tj.
501          else if (A.isNull()) {
502            return;
503          } else if (F instanceof TypeVariable) {
504            if (typeVariables.contains(F)) {
505              addSubtypeConstraint(F, A);
506            }
507          } else if (F.isArrayDecl()) {
508            TypeDecl U = ((ArrayDecl) F).componentType();
509            if (A.isArrayDecl()) {
510              TypeDecl V = ((ArrayDecl) A).componentType();
511              convertibleFrom(V, U);
512            } else if (A.isTypeVariable()) {
513              TypeVariable t = (TypeVariable) A;
514              for (int i = 0; i < t.getNumTypeBound(); i++) {
515                TypeDecl typeBound = t.getTypeBound(i).type();
516                if (typeBound.isArrayDecl() && ((ArrayDecl) typeBound).componentType().isReferenceType()) {
517                  TypeDecl V = ((ArrayDecl) typeBound).componentType();
518                  convertibleFrom(V, U);
519                }
520              }
521            }
522          } else if (F instanceof ParTypeDecl && !F.isRawType() && A instanceof ParTypeDecl && !A.isRawType()) {
523            ParTypeDecl PF = (ParTypeDecl) F;
524            ParTypeDecl PA = (ParTypeDecl) A;
525            TypeDecl G = PF.genericDecl();
526            TypeDecl H = PA.genericDecl();
527            for (int i = 0; i < PF.getNumArgument(); i++) {
528              TypeDecl T = PF.getArgument(i).type();
529              if (T.involvesTypeParameters()) {
530                // If F has the form G<...,U,...> where U is a type expression that involves Tj
531                if (!T.isWildcard()) {
532                  TypeDecl U = T;
533                  if (G.instanceOf(H)) {
534                    if (H != G) {
535                      for (Iterator iter = parameterizedSupertypes(F).iterator(); iter.hasNext(); ) {
536                        TypeDecl V = (TypeDecl) iter.next();
537                        if (!V.isRawType() && ((ParTypeDecl) V).genericDecl() == H) {
538                          if (F.instanceOf(V)) {
539                            convertibleFrom(A, V);
540                          }
541                        }
542                      }
543                    } else if (PF.getNumArgument() == PA.getNumArgument()) {
544                      TypeDecl X = PA.getArgument(i).type();
545                      if (!X.isWildcard()) {
546                        TypeDecl W = X;
547                        constraintEqual(W, U);
548                      } else if (X instanceof WildcardExtendsType) {
549                        TypeDecl W = ((WildcardExtendsType) X).getAccess().type();
550                        convertibleFrom(W, U);
551                      } else if (X instanceof WildcardSuperType) {
552                        TypeDecl W = ((WildcardSuperType) X).getAccess().type();
553                        convertibleTo(W, U);
554                      }
555                    }
556                  }
557                } else if (T instanceof WildcardExtendsType) {
558                  TypeDecl U = ((WildcardExtendsType) T).getAccess().type();
559                  if (G.instanceOf(H)) {
560                    if (H != G) {
561                      for (Iterator iter = parameterizedSupertypes(F).iterator(); iter.hasNext(); ) {
562                        TypeDecl V = (TypeDecl) iter.next();
563                        if (!V.isRawType() && ((ParTypeDecl) V).genericDecl() == H) {
564                          // replace type argument Un with ? extends Un in V
565                          ArrayList list = new ArrayList();
566                          for (int j = 0; j < ((ParTypeDecl) V).getNumArgument(); j++) {
567                            list.add(((ParTypeDecl) V).getArgument(j).type().asWildcardExtends());
568                          }
569                          V = ((GenericTypeDecl) H).lookupParTypeDecl(list);
570                          convertibleFrom(A, V);
571                        }
572                      }
573                    } else if (PF.getNumArgument() == PA.getNumArgument()) {
574                      TypeDecl X = PA.getArgument(i).type();
575                      if (X instanceof WildcardExtendsType) {
576                        TypeDecl W = ((WildcardExtendsType) X).getAccess().type();
577                        convertibleFrom(W, U);
578                      }
579                    }
580                  }
581                } else if (T instanceof WildcardSuperType) {
582                  TypeDecl U = ((WildcardSuperType) T).getAccess().type();
583                  if (G.instanceOf(H)) {
584                    if (H != G) {
585                      for (Iterator iter = parameterizedSupertypes(F).iterator(); iter.hasNext(); ) {
586                        TypeDecl V = (TypeDecl) iter.next();
587                        if (!V.isRawType() && ((ParTypeDecl) V).genericDecl() == H) {
588                          // replace type argument Un with ? super Un in V
589                          ArrayList list = new ArrayList();
590                          for (int j = 0; j < ((ParTypeDecl) V).getNumArgument(); j++) {
591                            list.add(((ParTypeDecl) V).getArgument(j).type().asWildcardExtends());
592                          }
593                          V = ((GenericTypeDecl) H).lookupParTypeDecl(list);
594                          convertibleFrom(A, V);
595                        }
596                      }
597                    } else if (PF.getNumArgument() == PA.getNumArgument()) {
598                      TypeDecl X = PA.getArgument(i).type();
599                      if (X instanceof WildcardSuperType) {
600                        TypeDecl W = ((WildcardSuperType) X).getAccess().type();
601                        convertibleTo(W, U);
602                      }
603                    }
604                  }
605                }
606              }
607            }
608          } else if (F.isRawType()) {
609            rawAccess = true;
610          }
611        }
612    
613        public void constraintEqual(TypeDecl A, TypeDecl F) {
614          //System.out.println("ConstraintEqual called with " + A.fullName() + "(" + A.getClass().getName() + ")" + " and " + F.fullName() + "(" + F.getClass().getName() + ")");
615          // If F does not involve a type parameter Tj then con constraint is implied on Tj
616          if (!F.involvesTypeParameters()) {
617            return;
618          }
619          // If A is the type of null, no constraint is implied on Tj.
620          else if (A.isNull()) {
621            return;
622          } else if (F instanceof TypeVariable) {
623            if (typeVariables.contains(F)) {
624              addEqualConstraint(F, A);
625            }
626          } else if (F.isArrayDecl()) {
627            TypeDecl U = ((ArrayDecl) F).componentType();
628            if (A.isArrayDecl()) {
629              TypeDecl V = ((ArrayDecl) A).componentType();
630              constraintEqual(V, U);
631            } else if (A.isTypeVariable()) {
632              TypeVariable t = (TypeVariable) A;
633              for (int i = 0; i < t.getNumTypeBound(); i++) {
634                TypeDecl typeBound = t.getTypeBound(i).type();
635                if (typeBound.isArrayDecl() && ((ArrayDecl) typeBound).componentType().isReferenceType()) {
636                  TypeDecl V = ((ArrayDecl) typeBound).componentType();
637                  constraintEqual(V, U);
638                }
639              }
640            }
641          } else if (F instanceof ParTypeDecl && !F.isRawType()) {
642            if (A instanceof ParTypeDecl) {
643              ParTypeDecl PF = (ParTypeDecl) F;
644              ParTypeDecl PA = (ParTypeDecl) A;
645              if (PF.genericDecl() == PA.genericDecl()) {
646                if (A.isRawType()) {
647                  rawAccess = true;
648                } else
649                for (int i = 0; i < PF.getNumArgument(); i++) {
650                  TypeDecl T = PF.getArgument(i).type();
651                  if (T.involvesTypeParameters()) {
652                    if (!T.isWildcard()) {
653                      TypeDecl U = T;
654                      TypeDecl V = PA.getArgument(i).type();
655                      constraintEqual(V, U);
656                    } else if (T instanceof WildcardExtendsType) {
657                      TypeDecl U = ((WildcardExtendsType) T).getAccess().type();
658                      TypeDecl S = PA.getArgument(i).type();
659                      if (S instanceof WildcardExtendsType) {
660                        TypeDecl V = ((WildcardExtendsType) S).getAccess().type();
661                        constraintEqual(V, U);
662                      }
663                    } else if (T instanceof WildcardSuperType) {
664                      TypeDecl U = ((WildcardSuperType) T).getAccess().type();
665                      TypeDecl S = PA.getArgument(i).type();
666                      if (S instanceof WildcardSuperType) {
667                        TypeDecl V = ((WildcardSuperType) S).getAccess().type();
668                        constraintEqual(V, U);
669                      }
670                    }
671                  }
672                }
673              }
674            }
675          }
676        }
677      }
678    
679      syn lazy TypeDecl LUBType.lub() {
680        ArrayList list = new ArrayList();
681        for (int i = 0; i < getNumTypeBound(); i++) {
682          list.add(getTypeBound(i).type());
683        }
684        ArrayList bounds = new ArrayList();
685        for (Iterator iter = LUBType.MEC(list).iterator(); iter.hasNext(); ) {
686          TypeDecl W = (TypeDecl) iter.next();
687          TypeDecl C = W instanceof GenericTypeDecl ? lci(Inv(W, list), W) : W;
688          bounds.add(C);
689        }
690        if (bounds.size() == 1) {
691          return (TypeDecl) bounds.iterator().next();
692        }
693        return lookupLUBType(bounds);
694      }
695    
696        // the erased candidate set for type parameter Tj, EC,
697        // is the intersection of all the sets EST(U) for each
698        // U in U1...Uk
699        public static HashSet LUBType.EC(ArrayList list) {
700          HashSet result = new HashSet();
701          boolean first = true;
702          for (Iterator iter = list.iterator(); iter.hasNext(); ) {
703            TypeDecl U = (TypeDecl) iter.next();
704            // erased supertype set of U
705            HashSet EST = LUBType.EST(U);
706            if (first) {
707              result.addAll(EST);
708              first = false;
709            } else {
710              result.retainAll(EST);
711            }
712          }
713          return result;
714        }
715    
716        /**
717         * The minimal erased candidate set for Tj
718         * is MEC = {V | V in EC, forall  W != V in EC, not W <: V}
719         * @return minimal erased candidate set for Tj
720         */
721        public static HashSet LUBType.MEC(ArrayList list) {
722          HashSet EC = LUBType.EC(list);
723          if (EC.size() == 1) {
724            return EC;
725          }
726          HashSet MEC = new HashSet();
727          for (Iterator iter = EC.iterator(); iter.hasNext(); ) {
728            TypeDecl V = (TypeDecl) iter.next();
729            boolean keep = true;
730            for (Iterator i2 = EC.iterator(); i2.hasNext(); ) {
731              TypeDecl W = (TypeDecl) i2.next();
732              if (!(V instanceof TypeVariable) && V != W && W.instanceOf(V)) {
733                keep = false;
734              }
735            }
736            if (keep) {
737              MEC.add(V);
738            }
739          }
740          return MEC;
741        }
742    
743        /**
744         * relevant invocations of G, Inv(G)
745         * Inv(G) = {V | 1 <= i <= k, V in ST(Ui), V = G<...>}
746         * @return set of relevant invocations of G, Inv(G)
747         */
748        public static HashSet LUBType.Inv(TypeDecl G, ArrayList Us) {
749          HashSet result = new HashSet();
750          for (Iterator iter = Us.iterator(); iter.hasNext(); ) {
751            TypeDecl U = (TypeDecl) iter.next();
752            for (Iterator i2 = LUBType.ST(U).iterator(); i2.hasNext(); ) {
753              TypeDecl V = (TypeDecl) i2.next();
754              if (V instanceof ParTypeDecl && !V.isRawType() && ((ParTypeDecl) V).genericDecl() == G) {
755                result.add(V);
756              }
757            }
758          }
759          return result;
760        }
761    
762        /**
763         * @return least containing invocation (lci)
764         */
765        public TypeDecl LUBType.lci(HashSet set, TypeDecl G) {
766          ArrayList list = new ArrayList();
767          boolean first = true;
768          for (Iterator iter = set.iterator(); iter.hasNext(); ) {
769            ParTypeDecl decl = (ParTypeDecl) iter.next();
770            if (first) {
771              first = false;
772              for (int i = 0; i < decl.getNumArgument(); i++) {
773                list.add(decl.getArgument(i).type());
774              }
775            } else {
776              for (int i = 0; i < decl.getNumArgument(); i++) {
777                list.set(i, lcta((TypeDecl) list.get(i), decl.getArgument(i).type()));
778              }
779            }
780          }
781          return ((GenericTypeDecl) G).lookupParTypeDecl(list);
782        }
783    
784        /**
785         * least containing type arguments
786         */
787        public TypeDecl LUBType.lcta(TypeDecl X, TypeDecl Y) {
788          //System.err.println("Computing lcta for " + X.typeName() + " and " + Y.typeName());
789          if (!X.isWildcard() && !Y.isWildcard()) {
790            TypeDecl U = X;
791            TypeDecl V = Y;
792            return U == V ? U : lub(U, V).asWildcardExtends();
793          } else if (!X.isWildcard() && Y instanceof WildcardExtendsType) {
794            TypeDecl U = X;
795            TypeDecl V = ((WildcardExtendsType) Y).getAccess().type();
796            return lub(U, V).asWildcardExtends();
797          } else if (!Y.isWildcard() && X instanceof WildcardExtendsType) {
798            TypeDecl U = Y;
799            TypeDecl V = ((WildcardExtendsType) X).getAccess().type();
800            return lub(U, V).asWildcardExtends();
801          } else if (!X.isWildcard() && Y instanceof WildcardSuperType) {
802            TypeDecl U = X;
803            TypeDecl V = ((WildcardSuperType) Y).getAccess().type();
804            ArrayList bounds = new ArrayList();
805            bounds.add(U);
806            bounds.add(V);
807            return GLBTypeFactory.glb(bounds).asWildcardSuper();
808          } else if (!Y.isWildcard() && X instanceof WildcardSuperType) {
809            TypeDecl U = Y;
810            TypeDecl V = ((WildcardSuperType) X).getAccess().type();
811            ArrayList bounds = new ArrayList();
812            bounds.add(U);
813            bounds.add(V);
814            return GLBTypeFactory.glb(bounds).asWildcardSuper();
815          } else if (X instanceof WildcardExtendsType && Y instanceof WildcardExtendsType) {
816            TypeDecl U = ((WildcardExtendsType) X).getAccess().type();
817            TypeDecl V = ((WildcardExtendsType) Y).getAccess().type();
818            return lub(U, V).asWildcardExtends();
819          } else if (X instanceof WildcardExtendsType && Y instanceof WildcardSuperType) {
820            TypeDecl U = ((WildcardExtendsType) X).getAccess().type();
821            TypeDecl V = ((WildcardSuperType) Y).getAccess().type();
822            return U == V ? U : U.typeWildcard();
823          } else if (Y instanceof WildcardExtendsType && X instanceof WildcardSuperType) {
824            TypeDecl U = ((WildcardExtendsType) Y).getAccess().type();
825            TypeDecl V = ((WildcardSuperType) X).getAccess().type();
826            return U == V ? U : U.typeWildcard();
827          } else if (X instanceof WildcardSuperType && Y instanceof WildcardSuperType) {
828            TypeDecl U = ((WildcardSuperType) X).getAccess().type();
829            TypeDecl V = ((WildcardSuperType) Y).getAccess().type();
830            ArrayList bounds = new ArrayList();
831            bounds.add(U);
832            bounds.add(V);
833            return GLBTypeFactory.glb(bounds).asWildcardSuper();
834          } else {
835            throw new Error("lcta not defined for (" + X.getClass().getName() + ", " + Y.getClass().getName() + ")");
836          }
837        }
838    
839        public TypeDecl LUBType.lub(TypeDecl X, TypeDecl Y) {
840          ArrayList list = new ArrayList(2);
841          list.add(X);
842          list.add(Y);
843          return lub(list);
844        }
845    
846        public TypeDecl LUBType.lub(ArrayList list) {
847          return lookupLUBType(list);
848        }
849    
850        // erased supertype set of T
851        public static HashSet LUBType.EST(TypeDecl t) {
852          HashSet result = new HashSet();
853          for (Iterator iter = LUBType.ST(t).iterator(); iter.hasNext(); ) {
854            TypeDecl typeDecl = (TypeDecl) iter.next();
855            if (typeDecl instanceof TypeVariable) {
856              result.add(typeDecl);
857            } else {
858              result.add(typeDecl.erasure());
859            }
860          }
861          return result;
862        }
863    
864        /**
865         * @return supertype set of T
866         */
867        public static HashSet LUBType.ST(TypeDecl t) {
868          HashSet result = new HashSet();
869          LUBType.addSupertypes(result, t);
870          return result;
871        }
872    
873        public static void LUBType.addSupertypes(HashSet set, TypeDecl t) {
874          set.add(t);
875          if (t instanceof ClassDecl) {
876            ClassDecl type = (ClassDecl) t;
877            if (type.hasSuperclass()) {
878              addSupertypes(set, type.superclass());
879            }
880            for (int i = 0; i < type.getNumImplements(); i++) {
881              addSupertypes(set, type.getImplements(i).type());
882            }
883          } else if (t instanceof InterfaceDecl) {
884            InterfaceDecl type = (InterfaceDecl) t;
885            for (int i = 0; i < type.getNumSuperInterface(); i++) {
886              addSupertypes(set, type.getSuperInterface(i).type());
887            }
888            if (type.getNumSuperInterface() == 0) {
889              set.add(type.typeObject());
890            }
891          } else if (t instanceof TypeVariable) {
892            TypeVariable type = (TypeVariable) t;
893            for (int i = 0; i < type.getNumTypeBound(); i++) {
894              addSupertypes(set, type.getTypeBound(i).type());
895            }
896            if (type.getNumTypeBound() == 0) {
897              set.add(type.typeObject());
898            }
899          } else if (t instanceof LUBType) {
900            LUBType type = (LUBType) t;
901            for (int i = 0; i < type.getNumTypeBound(); i++) {
902              addSupertypes(set, type.getTypeBound(i).type());
903            }
904            if (type.getNumTypeBound() == 0) {
905              set.add(type.typeObject());
906            }
907          } else if (! (t instanceof NullType)) {
908            throw new Error("Operation not supported for " + t.fullName() + ", " + t.getClass().getName());
909          }
910        }
911    
912    }