001    package AST;
002    
003    import java.util.HashSet;
004    import java.io.File;
005    import java.util.*;
006    import beaver.*;
007    import java.util.ArrayList;
008    import java.util.zip.*;
009    import java.io.*;
010    import java.io.FileNotFoundException;
011    import java.util.Collection;
012    /**
013      * @ast class
014     * 
015     */
016    public class Constraints extends java.lang.Object {
017    
018        static class ConstraintSet {
019          public Collection supertypeConstraints = new HashSet(4);
020          public Collection subtypeConstraints = new HashSet(4);
021          public Collection equaltypeConstraints = new HashSet(4);
022          public TypeDecl typeArgument;
023        }
024    
025    
026        private Collection typeVariables;
027    
028    
029        private Map constraintsMap;
030    
031    
032        public boolean rawAccess = false;
033    
034    
035    
036        public Constraints() {
037          typeVariables = new ArrayList(4);
038          constraintsMap = new HashMap();
039        }
040    
041    
042    
043        public void addTypeVariable(TypeVariable T) {
044          if(!typeVariables.contains(T)) {
045            typeVariables.add(T);
046            constraintsMap.put(T, new ConstraintSet());
047          }
048        }
049    
050    
051    
052        public boolean unresolvedTypeArguments() {
053          for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
054            TypeVariable T = (TypeVariable)iter.next();
055            ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
056            if(set.typeArgument == null)
057              return true;
058          }
059          return false;
060        }
061    
062    
063    
064        public void printConstraints() {
065          System.err.println("Current constraints:");
066          for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
067            TypeVariable T = (TypeVariable)iter.next();
068            ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
069            for(Iterator i2 = set.supertypeConstraints.iterator(); i2.hasNext(); ) {
070              TypeDecl U = (TypeDecl)i2.next();
071              System.err.println("  " + T.fullName() + " :> " + U.fullName());
072            }
073            for(Iterator i2 = set.subtypeConstraints.iterator(); i2.hasNext(); ) {
074              TypeDecl U = (TypeDecl)i2.next();
075              System.err.println("  " + T.fullName() + " <: " + U.fullName());
076            }
077            for(Iterator i2 = set.equaltypeConstraints.iterator(); i2.hasNext(); ) {
078              TypeDecl U = (TypeDecl)i2.next();
079              System.err.println("  " + T.fullName() + " = " + U.fullName());
080            }
081          }
082        }
083    
084    
085    
086        
087        public void resolveBounds() {
088          for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
089            TypeVariable T = (TypeVariable)iter.next();
090            ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
091            if(set.typeArgument == null) {
092              //if(T.getNumTypeBound() == 1)
093                set.typeArgument = T.getTypeBound(0).type();
094              //else
095              //  throw new Error("Not supported for multiple bounds yet");
096            }
097          }
098        }
099    
100    
101    
102        public void resolveEqualityConstraints() {
103          for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
104            TypeVariable T = (TypeVariable)iter.next();
105            ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
106            boolean done = false;
107            for(Iterator i2 = set.equaltypeConstraints.iterator(); !done && i2.hasNext(); ) {
108              TypeDecl U = (TypeDecl)i2.next();
109              if(!typeVariables.contains(U)) {
110                replaceEqualityConstraints(T, U);   // replace equality constraints for other type variables
111                set.equaltypeConstraints.clear();
112                set.equaltypeConstraints.add(U);    // make U is the only equality constraint for T
113                set.typeArgument = U;
114                done = true;                        // continue on next type variable
115              }
116              else if(T == U) {
117                //i2.remove();                        // discard constraint
118              }
119              else {
120                replaceAllConstraints(T, U);         // rewrite all constraints involving T to use U instead
121                done = true;                        // continue on next type variable
122              }
123            }
124            if(set.typeArgument == null && set.equaltypeConstraints.size() == 1 && set.equaltypeConstraints.contains(T))
125               set.typeArgument = T;
126          }
127        }
128    
129    
130    
131        public void replaceEqualityConstraints(TypeDecl before, TypeDecl after) {
132          for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
133            TypeVariable T = (TypeVariable)iter.next();
134            ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
135            replaceConstraints(set.equaltypeConstraints, before, after);
136          }
137        }
138    
139    
140        
141        public void replaceAllConstraints(TypeDecl before, TypeDecl after) {
142          for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
143            TypeVariable T = (TypeVariable)iter.next();
144            ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
145            replaceConstraints(set.supertypeConstraints, before, after);
146            replaceConstraints(set.subtypeConstraints, before, after);
147            replaceConstraints(set.equaltypeConstraints, before, after);
148          }
149        }
150    
151    
152        
153        private void replaceConstraints(Collection constraints, TypeDecl before, TypeDecl after) {
154          Collection newConstraints = new ArrayList();
155          for(Iterator i2 = constraints.iterator(); i2.hasNext(); ) {
156            TypeDecl U = (TypeDecl)i2.next();
157            if(U == before) { //  TODO: fix parameterized type
158              i2.remove();
159              newConstraints.add(after);
160            }
161          }
162          constraints.addAll(newConstraints);
163        }
164    
165    
166    
167        public void resolveSubtypeConstraints() {
168          for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
169            TypeVariable T = (TypeVariable)iter.next();
170            ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
171            if((!set.subtypeConstraints.isEmpty() || T.getNumTypeBound() > 0) && set.typeArgument == null) {
172              ArrayList bounds = new ArrayList();
173              for(Iterator i2 = set.subtypeConstraints.iterator(); i2.hasNext(); ) {
174                bounds.add(i2.next());
175              }
176              for(int i = 0; i < T.getNumTypeBound(); i++) {
177                bounds.add(T.getTypeBound(i).type());
178              }
179              set.typeArgument = GLBTypeFactory.glb(bounds);
180            }
181          }
182        }
183    
184    
185        
186        public void resolveSupertypeConstraints() {
187          for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
188            TypeVariable T = (TypeVariable)iter.next();
189            ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
190            if(!set.supertypeConstraints.isEmpty() && set.typeArgument == null) {
191              //TypeDecl typeDecl = lub(set.supertypeConstraints);
192              TypeDecl typeDecl = T.lookupLUBType(set.supertypeConstraints).lub();
193              set.typeArgument = typeDecl;
194              /*
195              TypeDecl EC = (TypeDecl)set.supertypeConstraints.get(0);
196              for(Iterator i2 = set.supertypeConstraints.iterator(); i2.hasNext(); ) {
197                TypeDecl U = (TypeDecl)i2.next();
198                TypeDecl ST = U;
199                TypeDecl EST = ST.erasure();
200                EC = intersect(EC, EST);
201              }
202              TypeDecl MEC = EC;
203              //System.err.println(" MEC(" + T.fullName() + ") = " + MEC.fullName());
204              set.typeArgument = MEC;
205              */
206            }
207          }
208        }
209    
210    
211        
212        /*
213        // operates only on erased types. does it matter? (no type variables, no partypedecl)
214        private TypeDecl intersect(TypeDecl t1, TypeDecl t2) {
215          if(t1.instanceOf(t2))
216            return t1;
217          else if(t2.instanceOf(t1))
218            return t2;
219          else {
220            HashSet set = new HashSet();
221            for(Iterator iter = directSupertypes(t1).iterator(); iter.hasNext(); ) {
222              TypeDecl t1Super = (TypeDecl)iter.next();
223              set.add(intersect(t1Super, t2));
224            }
225            if(set.isEmpty())
226              throw new Error("Empty intersection of " + t1.fullName() + " and " + t2.fullName());
227            TypeDecl lowestType = (TypeDecl)set.iterator().next();
228            for(Iterator iter = set.iterator(); iter.hasNext(); ) {
229              TypeDecl type = (TypeDecl)iter.next();
230              if(type.instanceOf(lowestType))
231                lowestType = type;
232              else if(!lowestType.instanceOf(type))
233                throw new Error("Several leaf types in intersection, " + lowestType.fullName() + " and " + type.fullName());
234            }
235            return lowestType;
236          }
237        }
238        */
239    
240        public static HashSet directSupertypes(TypeDecl t) {
241          if(t instanceof ClassDecl) {
242            ClassDecl type = (ClassDecl)t;
243            HashSet set = new HashSet();
244            if(type.hasSuperclass())
245              set.add(type.superclass());
246            for(int i = 0; i < type.getNumImplements(); i++)
247              set.add(type.getImplements(i).type());
248            return set;
249          }
250          else if(t instanceof InterfaceDecl) {
251            InterfaceDecl type = (InterfaceDecl)t;
252            HashSet set = new HashSet();
253            for(int i = 0; i < type.getNumSuperInterfaceId(); i++)
254              set.add(type.getSuperInterfaceId(i).type());
255            return set;
256          }
257          else if(t instanceof TypeVariable) {
258            TypeVariable type = (TypeVariable)t;
259            HashSet set = new HashSet();
260            for(int i = 0; i < type.getNumTypeBound(); i++)
261              set.add(type.getTypeBound(i).type());
262            return set;
263          }
264          else
265            throw new Error("Operation not supported for " + t.fullName() + ", " + t.getClass().getName());
266        }
267    
268    
269    
270        public static HashSet parameterizedSupertypes(TypeDecl t) {
271          HashSet result = new HashSet();
272          addParameterizedSupertypes(t, new HashSet(), result);
273          return result;
274        }
275    
276    
277        public static void addParameterizedSupertypes(TypeDecl t, HashSet processed, HashSet result) {
278          if(!processed.contains(t)) {
279            processed.add(t);
280            if(t.isParameterizedType() /*&& !t.isRawType()*/)
281              result.add(t);
282            for(Iterator iter = directSupertypes(t).iterator(); iter.hasNext(); ) {
283              TypeDecl typeDecl = (TypeDecl)iter.next();
284              addParameterizedSupertypes(typeDecl, processed, result);
285            }
286          }
287        }
288    
289    
290    
291        public Collection typeArguments() {
292          ArrayList list = new ArrayList(typeVariables.size());
293          for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
294            TypeVariable T = (TypeVariable)iter.next();
295            ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
296            list.add(set.typeArgument);
297          }
298          return list;
299        }
300    
301    
302    
303        public void addSupertypeConstraint(TypeDecl T, TypeDecl A) {
304          ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
305          set.supertypeConstraints.add(A);
306          //System.out.println(T.name() + " :> " + A.fullName());
307        }
308    
309    
310        public void addSubtypeConstraint(TypeDecl T, TypeDecl A) {
311          ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
312          set.subtypeConstraints.add(A);
313          //System.out.println(T.name() + " <: " + A.fullName());
314        }
315    
316    
317        public void addEqualConstraint(TypeDecl T, TypeDecl A) {
318          ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
319          set.equaltypeConstraints.add(A);
320          //System.out.println(T.name() + " = " + A.fullName());
321        }
322    
323    
324        
325        public void convertibleTo(TypeDecl A, TypeDecl F) {
326          //System.out.println("Convertible to called with " + A.fullName() + "(" + A.getClass().getName() + ")" + " and " + F.fullName() + "(" + F.getClass().getName() + ")");
327          // If F does not involve a type parameter Tj then con constraint is implied on Tj
328          if(!F.involvesTypeParameters())
329            return;
330          // If A is the type of null, no constraint is implied on Tj.
331          if(A.isNull())
332            return;
333          // If A is a primitive type, then A is converted to a reference type U via boxing conversion
334          // and this algorithm is applied recursively to the constraint U << F.
335          if(A.isUnboxedPrimitive()) {
336            TypeDecl U = A.boxed();
337            convertibleTo(U, F);
338          }
339          // If F = Tj, then the constrint Tj :> A is implied
340          else if(F instanceof TypeVariable) {
341            if(typeVariables.contains(F))
342              addSupertypeConstraint(F, A);
343          }
344          // If F = U[], where the type U involves Tj, then if A is an array type V[]
345          // or a type variable with an upper bound that is an array type V[],
346          // where V is a reference type, this algorithm is applied recursively
347          // to the constraint V << U
348          else if(F.isArrayDecl()) {
349            //System.out.println("convertibleTo array decl");
350            TypeDecl U = ((ArrayDecl)F).componentType();
351            if(!U.involvesTypeParameters())
352              return;
353            if(A.isArrayDecl()) {
354              TypeDecl V = ((ArrayDecl)A).componentType();
355              if(V.isReferenceType())
356                convertibleTo(V, U);
357            }
358            else if(A.isTypeVariable()) {
359              TypeVariable t = (TypeVariable)A;
360              for(int i = 0; i < t.getNumTypeBound(); i++) {
361                TypeDecl typeBound = t.getTypeBound(i).type();
362                if(typeBound.isArrayDecl() && ((ArrayDecl)typeBound).componentType().isReferenceType()) {
363                  TypeDecl V = ((ArrayDecl)typeBound).componentType();
364                  convertibleTo(V, U);
365                }
366              }
367            }
368          }
369          else if(F instanceof ParTypeDecl && !F.isRawType()) {
370            for(Iterator iter = parameterizedSupertypes(A).iterator(); iter.hasNext(); ) {
371              ParTypeDecl PF = (ParTypeDecl)F;
372              ParTypeDecl PA = (ParTypeDecl)iter.next();
373              if(PF.genericDecl() == PA.genericDecl()) {
374                if(A.isRawType())
375                  rawAccess = true;
376                else
377                for(int i = 0; i < PF.getNumArgument(); i++) {
378                  TypeDecl T = PF.getArgument(i).type();
379                  if(T.involvesTypeParameters()) {
380                    if(!T.isWildcard()) {
381                      TypeDecl U = T;
382                      TypeDecl V = PA.getArgument(i).type();
383                      constraintEqual(V, U);
384                    }
385                    else if(T instanceof WildcardExtendsType) {
386                      TypeDecl U = ((WildcardExtendsType)T).getAccess().type();
387                      TypeDecl S = PA.getArgument(i).type();
388                      if(!S.isWildcard()) {
389                        TypeDecl V = S;
390                        convertibleTo(V, U);
391                      }
392                      else if(S instanceof WildcardExtendsType) {
393                        TypeDecl V = ((WildcardExtendsType)S).getAccess().type();
394                        convertibleTo(V, U);
395                      }
396                    }
397                    else if(T instanceof WildcardSuperType) {
398                      TypeDecl U = ((WildcardSuperType)T).getAccess().type();
399                      TypeDecl S = PA.getArgument(i).type();
400                      if(!S.isWildcard()) {
401                        TypeDecl V = S;
402                        convertibleFrom(V, U);
403                      }
404                      else if(S instanceof WildcardSuperType) {
405                        TypeDecl V = ((WildcardSuperType)S).getAccess().type();
406                        convertibleFrom(V, U);
407                      }
408                    }
409                  }
410                }
411              }
412            }
413          }
414        }
415    
416    
417    
418    
419        public void convertibleFrom(TypeDecl A, TypeDecl F) {
420          //System.out.println("ConvertibleFrom called with " + A.fullName() + "(" + A.getClass().getName() + ")" + " and " + F.fullName() + "(" + F.getClass().getName() + ")");
421          // If F does not involve a type parameter Tj then con constraint is implied on Tj
422          if(!F.involvesTypeParameters())
423            return;
424          // If A is the type of null, no constraint is implied on Tj.
425          else if(A.isNull())
426            return;
427          else if(F instanceof TypeVariable) {
428            if(typeVariables.contains(F))
429              addSubtypeConstraint(F, A);
430          }
431          else if(F.isArrayDecl()) {
432            TypeDecl U = ((ArrayDecl)F).componentType();
433            if(A.isArrayDecl()) {
434              TypeDecl V = ((ArrayDecl)A).componentType();
435              convertibleFrom(V, U);
436            }
437            else if(A.isTypeVariable()) {
438              TypeVariable t = (TypeVariable)A;
439              for(int i = 0; i < t.getNumTypeBound(); i++) {
440                TypeDecl typeBound = t.getTypeBound(i).type();
441                if(typeBound.isArrayDecl() && ((ArrayDecl)typeBound).componentType().isReferenceType()) {
442                  TypeDecl V = ((ArrayDecl)typeBound).componentType();
443                  convertibleFrom(V, U);
444                }
445              }
446            }
447          }
448          else if(F instanceof ParTypeDecl && !F.isRawType() && A instanceof ParTypeDecl && !A.isRawType()) {
449            ParTypeDecl PF = (ParTypeDecl)F;
450            ParTypeDecl PA = (ParTypeDecl)A;
451            TypeDecl G = PF.genericDecl();
452            TypeDecl H = PA.genericDecl();
453            for(int i = 0; i < PF.getNumArgument(); i++) {
454              TypeDecl T = PF.getArgument(i).type();
455              if(T.involvesTypeParameters()) {
456                // If F has the form G<...,U,...> where U is a type expression that involves Tj
457                if(!T.isWildcard()) {
458                  TypeDecl U = T;
459                  if(G.instanceOf(H)) {
460                    if(H != G) {
461                      for(Iterator iter = parameterizedSupertypes(F).iterator(); iter.hasNext(); ) {
462                        TypeDecl V = (TypeDecl)iter.next();
463                        if(!V.isRawType() && ((ParTypeDecl)V).genericDecl() == H) {
464                          if(F.instanceOf(V))
465                            convertibleFrom(A, V);
466                        }
467                      }
468                    }
469                    else if(PF.getNumArgument() == PA.getNumArgument()) {
470                      TypeDecl X = PA.getArgument(i).type();
471                      if(!X.isWildcard()) {
472                        TypeDecl W = X;
473                        constraintEqual(W, U);
474                      }
475                      else if(X instanceof WildcardExtendsType) {
476                        TypeDecl W = ((WildcardExtendsType)X).getAccess().type();
477                        convertibleFrom(W, U);
478                      }
479                      else if(X instanceof WildcardSuperType) {
480                        TypeDecl W = ((WildcardSuperType)X).getAccess().type();
481                        convertibleTo(W, U);
482                      }
483                    }
484                  }
485                }
486                else if(T instanceof WildcardExtendsType) {
487                  TypeDecl U = ((WildcardExtendsType)T).getAccess().type();
488                  if(G.instanceOf(H)) {
489                    if(H != G) {
490                      for(Iterator iter = parameterizedSupertypes(F).iterator(); iter.hasNext(); ) {
491                        TypeDecl V = (TypeDecl)iter.next();
492                        if(!V.isRawType() && ((ParTypeDecl)V).genericDecl() == H) {
493                          // replace type argument Un with ? extends Un in V
494                          ArrayList list = new ArrayList();
495                          for(int j = 0; j < ((ParTypeDecl)V).getNumArgument(); j++)
496                            list.add(((ParTypeDecl)V).getArgument(j).type().asWildcardExtends());
497                          V = ((GenericTypeDecl)H).lookupParTypeDecl(list);
498                          convertibleFrom(A, V);
499                        }
500                      }
501                    }
502                    else if(PF.getNumArgument() == PA.getNumArgument()) {
503                      TypeDecl X = PA.getArgument(i).type();
504                      if(X instanceof WildcardExtendsType) {
505                        TypeDecl W = ((WildcardExtendsType)X).getAccess().type();
506                        convertibleFrom(W, U);
507                      }
508                    }
509                  }
510                }
511                else if(T instanceof WildcardSuperType) {
512                  TypeDecl U = ((WildcardSuperType)T).getAccess().type();
513                  if(G.instanceOf(H)) {
514                    if(H != G) {
515                      for(Iterator iter = parameterizedSupertypes(F).iterator(); iter.hasNext(); ) {
516                        TypeDecl V = (TypeDecl)iter.next();
517                        if(!V.isRawType() && ((ParTypeDecl)V).genericDecl() == H) {
518                          // replace type argument Un with ? super Un in V
519                          ArrayList list = new ArrayList();
520                          for(int j = 0; j < ((ParTypeDecl)V).getNumArgument(); j++)
521                            list.add(((ParTypeDecl)V).getArgument(j).type().asWildcardExtends());
522                          V = ((GenericTypeDecl)H).lookupParTypeDecl(list);
523                          convertibleFrom(A, V);
524                        }
525                      }
526                    }
527                    else if(PF.getNumArgument() == PA.getNumArgument()) {
528                      TypeDecl X = PA.getArgument(i).type();
529                      if(X instanceof WildcardSuperType) {
530                        TypeDecl W = ((WildcardSuperType)X).getAccess().type();
531                        convertibleTo(W, U);
532                      }
533                    }
534                  }
535                }
536              }
537            }
538          }
539          else if(F.isRawType())
540            rawAccess = true;
541        }
542    
543    
544    
545        public void constraintEqual(TypeDecl A, TypeDecl F) {
546          //System.out.println("ConstraintEqual called with " + A.fullName() + "(" + A.getClass().getName() + ")" + " and " + F.fullName() + "(" + F.getClass().getName() + ")");
547          // If F does not involve a type parameter Tj then con constraint is implied on Tj
548          if(!F.involvesTypeParameters())
549            return;
550          // If A is the type of null, no constraint is implied on Tj.
551          else if(A.isNull())
552            return;
553          else if(F instanceof TypeVariable) {
554            if(typeVariables.contains(F))
555              addEqualConstraint(F, A);
556          }
557          else if(F.isArrayDecl()) {
558            TypeDecl U = ((ArrayDecl)F).componentType();
559            if(A.isArrayDecl()) {
560              TypeDecl V = ((ArrayDecl)A).componentType();
561              constraintEqual(V, U);
562            }
563            else if(A.isTypeVariable()) {
564              TypeVariable t = (TypeVariable)A;
565              for(int i = 0; i < t.getNumTypeBound(); i++) {
566                TypeDecl typeBound = t.getTypeBound(i).type();
567                if(typeBound.isArrayDecl() && ((ArrayDecl)typeBound).componentType().isReferenceType()) {
568                  TypeDecl V = ((ArrayDecl)typeBound).componentType();
569                  constraintEqual(V, U);
570                }
571              }
572            }
573          }
574          else if(F instanceof ParTypeDecl && !F.isRawType()) {
575            if(A instanceof ParTypeDecl) {
576              ParTypeDecl PF = (ParTypeDecl)F;
577              ParTypeDecl PA = (ParTypeDecl)A;
578              if(PF.genericDecl() == PA.genericDecl()) {
579                if(A.isRawType())
580                  rawAccess = true;
581                else
582                for(int i = 0; i < PF.getNumArgument(); i++) {
583                  TypeDecl T = PF.getArgument(i).type();
584                  if(T.involvesTypeParameters()) {
585                    if(!T.isWildcard()) {
586                      TypeDecl U = T;
587                      TypeDecl V = PA.getArgument(i).type();
588                      constraintEqual(V, U);
589                    }
590                    else if(T instanceof WildcardExtendsType) {
591                      TypeDecl U = ((WildcardExtendsType)T).getAccess().type();
592                      TypeDecl S = PA.getArgument(i).type();
593                      if(S instanceof WildcardExtendsType) {
594                        TypeDecl V = ((WildcardExtendsType)S).getAccess().type();
595                        constraintEqual(V, U);
596                      }
597                    }
598                    else if(T instanceof WildcardSuperType) {
599                      TypeDecl U = ((WildcardSuperType)T).getAccess().type();
600                      TypeDecl S = PA.getArgument(i).type();
601                      if(S instanceof WildcardSuperType) {
602                        TypeDecl V = ((WildcardSuperType)S).getAccess().type();
603                        constraintEqual(V, U);
604                      }
605                    }
606                  }
607                }
608              }
609            }
610          }
611        }
612    
613    
614    }