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