/*
 * The JastAdd Extensible Java Compiler (http://jastadd.org) is covered
 * by the modified BSD License. You should have received a copy of the
 * modified BSD license with this compiler.
 * 
 * Copyright (c) 2005-2008, Torbjorn Ekman
 * All rights reserved.
 */

import java.util.*;

aspect GenericMethodsInference {
  syn boolean TypeDecl.isUnboxedPrimitive() = this instanceof PrimitiveType && isPrimitive();

  syn boolean TypeDecl.involvesTypeParameters() circular [false] = false;
  eq TypeVariable.involvesTypeParameters() = true;
  eq ArrayDecl.involvesTypeParameters() = componentType().involvesTypeParameters();
  eq ParClassDecl.involvesTypeParameters() {
    for(int i = 0; i < getNumArgument(); i++)
      if(getArgument(i).type().involvesTypeParameters())
        return true;
    return false;
  }
  eq ParInterfaceDecl.involvesTypeParameters() {
    for(int i = 0; i < getNumArgument(); i++)
      if(getArgument(i).type().involvesTypeParameters())
        return true;
    return false;
  }
  eq WildcardExtendsType.involvesTypeParameters() = extendsType().involvesTypeParameters();
  eq WildcardSuperType.involvesTypeParameters() = superType().involvesTypeParameters();

  inh TypeDecl Expr.assignConvertedType();
  eq VariableDeclaration.getInit().assignConvertedType() = type();
  eq FieldDeclaration.getInit().assignConvertedType() = type();
  eq AssignSimpleExpr.getSource().assignConvertedType() = getDest().type();
  eq ArrayInit.getInit().assignConvertedType() = declType().componentType();
  eq ReturnStmt.getResult().assignConvertedType() = returnType();
  eq Program.getChild().assignConvertedType() = typeNull();

  eq MethodAccess.getArg().assignConvertedType() = typeObject();

  inh TypeDecl MethodAccess.typeObject();

  // Generic Method Type Inference
  public Collection MethodAccess.computeConstraints(GenericMethodDecl decl) {
    Constraints c = new Constraints();
    // store type parameters
    for(int i = 0; i < decl.original().getNumTypeParameter(); i++)
      c.addTypeVariable(decl.original().getTypeParameter(i));
    
    // add initial constraints
    for(int i = 0; i < getNumArg(); i++) {
      TypeDecl A = getArg(i).type();
      int index = i >= decl.getNumParameter() ? decl.getNumParameter() - 1 : i;
      TypeDecl F = decl.getParameter(index).type();
      if(decl.getParameter(index) instanceof VariableArityParameterDeclaration)
        F = F.componentType();
      c.convertibleTo(A, F);
    }
    
    //c.printConstraints();
    //System.err.println("Resolving equality constraints");
    c.resolveEqualityConstraints();
    //c.printConstraints();

    //System.err.println("Resolving supertype constraints");
    c.resolveSupertypeConstraints();
    //c.printConstraints();

    //System.err.println("Resolving unresolved type arguments");
    //c.resolveBounds();
    //c.printConstraints();

    if(c.unresolvedTypeArguments()) {
      TypeDecl S = assignConvertedType();
      if(S.isUnboxedPrimitive())
        S = S.boxed();
      TypeDecl R = decl.type();
      // TODO: replace all uses of type variables in R with their inferred types
      TypeDecl Rprime = R;
      if(R.isVoid())
        R = typeObject();
      c.convertibleFrom(S, R);
      // TODO: additional constraints

      c.resolveEqualityConstraints();
      c.resolveSupertypeConstraints();
      //c.resolveBounds();

      c.resolveSubtypeConstraints();
    }

    return c.typeArguments();
  }

  class Constraints {
    static class ConstraintSet {
      public Collection supertypeConstraints = new HashSet(4);
      public Collection subtypeConstraints = new HashSet(4);
      public Collection equaltypeConstraints = new HashSet(4);
      public TypeDecl typeArgument;
    }
    private Collection typeVariables;
    private Map constraintsMap;

    public Constraints() {
      typeVariables = new ArrayList(4);
      constraintsMap = new HashMap();
    }

    public void addTypeVariable(TypeVariable T) {
      if(!typeVariables.contains(T)) {
        typeVariables.add(T);
        constraintsMap.put(T, new ConstraintSet());
      }
    }

    public boolean unresolvedTypeArguments() {
      for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
        TypeVariable T = (TypeVariable)iter.next();
        ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
        if(set.typeArgument == null)
          return true;
      }
      return false;
    }

    public void printConstraints() {
      System.err.println("Current constraints:");
      for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
        TypeVariable T = (TypeVariable)iter.next();
        ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
        for(Iterator i2 = set.supertypeConstraints.iterator(); i2.hasNext(); ) {
          TypeDecl U = (TypeDecl)i2.next();
          System.err.println("  " + T.fullName() + " :> " + U.fullName());
        }
        for(Iterator i2 = set.subtypeConstraints.iterator(); i2.hasNext(); ) {
          TypeDecl U = (TypeDecl)i2.next();
          System.err.println("  " + T.fullName() + " <: " + U.fullName());
        }
        for(Iterator i2 = set.equaltypeConstraints.iterator(); i2.hasNext(); ) {
          TypeDecl U = (TypeDecl)i2.next();
          System.err.println("  " + T.fullName() + " = " + U.fullName());
        }
      }
    }

    
    public void resolveBounds() {
      for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
        TypeVariable T = (TypeVariable)iter.next();
        ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
        if(set.typeArgument == null) {
          //if(T.getNumTypeBound() == 1)
            set.typeArgument = T.getTypeBound(0).type();
          //else
          //  throw new Error("Not supported for multiple bounds yet");
        }
      }
    }

    public void resolveEqualityConstraints() {
      for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
        TypeVariable T = (TypeVariable)iter.next();
        ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
        boolean done = false;
        for(Iterator i2 = set.equaltypeConstraints.iterator(); !done && i2.hasNext(); ) {
          TypeDecl U = (TypeDecl)i2.next();
          if(!typeVariables.contains(U)) {
            replaceEqualityConstraints(T, U);   // replace equality constraints for other type variables
            set.equaltypeConstraints.clear();
            set.equaltypeConstraints.add(U);    // make U is the only equality constraint for T
            set.typeArgument = U;
            done = true;                        // continue on next type variable
          }
          else if(T == U) {
            //i2.remove();                        // discard constraint
          }
          else {
            replaceAllConstraints(T, U);         // rewrite all constraints involving T to use U instead
            done = true;                        // continue on next type variable
          }
        }
        if(set.typeArgument == null && set.equaltypeConstraints.size() == 1 && set.equaltypeConstraints.contains(T))
        	set.typeArgument = T;
      }
    }

    public void replaceEqualityConstraints(TypeDecl before, TypeDecl after) {
      for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
        TypeVariable T = (TypeVariable)iter.next();
        ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
        replaceConstraints(set.equaltypeConstraints, before, after);
      }
    }
    
    public void replaceAllConstraints(TypeDecl before, TypeDecl after) {
      for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
        TypeVariable T = (TypeVariable)iter.next();
        ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
        replaceConstraints(set.supertypeConstraints, before, after);
        replaceConstraints(set.subtypeConstraints, before, after);
        replaceConstraints(set.equaltypeConstraints, before, after);
      }
    }
    
    private void replaceConstraints(Collection constraints, TypeDecl before, TypeDecl after) {
      Collection newConstraints = new ArrayList();
      for(Iterator i2 = constraints.iterator(); i2.hasNext(); ) {
        TypeDecl U = (TypeDecl)i2.next();
        if(U == before) { //  TODO: fix parameterized type
          i2.remove();
          newConstraints.add(after);
        }
      }
      constraints.addAll(newConstraints);
    }

    public void resolveSubtypeConstraints() {
      for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
        TypeVariable T = (TypeVariable)iter.next();
        ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
        if((!set.subtypeConstraints.isEmpty() || T.getNumTypeBound() > 0) && set.typeArgument == null) {
          ArrayList bounds = new ArrayList();
          for(Iterator i2 = set.subtypeConstraints.iterator(); i2.hasNext(); ) {
            bounds.add(i2.next());
          }
          for(int i = 0; i < T.getNumTypeBound(); i++) {
            bounds.add(T.getTypeBound(i).type());
          }
          set.typeArgument = GLBTypeFactory.glb(bounds);
        }
      }
    }
    
    public void resolveSupertypeConstraints() {
      for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
        TypeVariable T = (TypeVariable)iter.next();
        ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
        if(!set.supertypeConstraints.isEmpty() && set.typeArgument == null) {
          //TypeDecl typeDecl = lub(set.supertypeConstraints);
          TypeDecl typeDecl = T.lookupLUBType(set.supertypeConstraints).lub();
          set.typeArgument = typeDecl;
          /*
          TypeDecl EC = (TypeDecl)set.supertypeConstraints.get(0);
          for(Iterator i2 = set.supertypeConstraints.iterator(); i2.hasNext(); ) {
            TypeDecl U = (TypeDecl)i2.next();
            TypeDecl ST = U;
            TypeDecl EST = ST.erasure();
            EC = intersect(EC, EST);
          }
          TypeDecl MEC = EC;
          //System.err.println(" MEC(" + T.fullName() + ") = " + MEC.fullName());
          set.typeArgument = MEC;
          */
        }
      }
    }
    
    /*
    // operates only on erased types. does it matter? (no type variables, no partypedecl)
    private TypeDecl intersect(TypeDecl t1, TypeDecl t2) {
      if(t1.instanceOf(t2))
        return t1;
      else if(t2.instanceOf(t1))
        return t2;
      else {
        HashSet set = new HashSet();
        for(Iterator iter = directSupertypes(t1).iterator(); iter.hasNext(); ) {
          TypeDecl t1Super = (TypeDecl)iter.next();
          set.add(intersect(t1Super, t2));
        }
        if(set.isEmpty())
          throw new Error("Empty intersection of " + t1.fullName() + " and " + t2.fullName());
        TypeDecl lowestType = (TypeDecl)set.iterator().next();
        for(Iterator iter = set.iterator(); iter.hasNext(); ) {
          TypeDecl type = (TypeDecl)iter.next();
          if(type.instanceOf(lowestType))
            lowestType = type;
          else if(!lowestType.instanceOf(type))
            throw new Error("Several leaf types in intersection, " + lowestType.fullName() + " and " + type.fullName());
        }
        return lowestType;
      }
    }
    */

    public static HashSet directSupertypes(TypeDecl t) {
      if(t instanceof ClassDecl) {
        ClassDecl type = (ClassDecl)t;
        HashSet set = new HashSet();
        if(type.hasSuperclass())
          set.add(type.superclass());
        for(int i = 0; i < type.getNumImplements(); i++)
          set.add(type.getImplements(i).type());
        return set;
      }
      else if(t instanceof InterfaceDecl) {
        InterfaceDecl type = (InterfaceDecl)t;
        HashSet set = new HashSet();
        for(int i = 0; i < type.getNumSuperInterfaceId(); i++)
          set.add(type.getSuperInterfaceId(i).type());
        return set;
      }
      else if(t instanceof TypeVariable) {
        TypeVariable type = (TypeVariable)t;
        HashSet set = new HashSet();
        for(int i = 0; i < type.getNumTypeBound(); i++)
          set.add(type.getTypeBound(i).type());
        return set;
      }
      else
        throw new Error("Operation not supported for " + t.fullName() + ", " + t.getClass().getName());
    }

    public static HashSet parameterizedSupertypes(TypeDecl t) {
      HashSet result = new HashSet();
      addParameterizedSupertypes(t, new HashSet(), result);
      return result;
    }
    public static void addParameterizedSupertypes(TypeDecl t, HashSet processed, HashSet result) {
      if(!processed.contains(t)) {
        processed.add(t);
        if(t.isParameterizedType() && !t.isRawType())
          result.add(t);
        for(Iterator iter = directSupertypes(t).iterator(); iter.hasNext(); ) {
          TypeDecl typeDecl = (TypeDecl)iter.next();
          addParameterizedSupertypes(typeDecl, processed, result);
        }
      }
    }

    public Collection typeArguments() {
      ArrayList list = new ArrayList(typeVariables.size());
      for(Iterator iter = typeVariables.iterator(); iter.hasNext(); ) {
        TypeVariable T = (TypeVariable)iter.next();
        ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
        list.add(set.typeArgument);
      }
      return list;
    }

    public void addSupertypeConstraint(TypeDecl T, TypeDecl A) {
      ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
      set.supertypeConstraints.add(A);
      //System.out.println(T.name() + " :> " + A.fullName());
    }
    public void addSubtypeConstraint(TypeDecl T, TypeDecl A) {
      ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
      set.subtypeConstraints.add(A);
      //System.out.println(T.name() + " <: " + A.fullName());
    }
    public void addEqualConstraint(TypeDecl T, TypeDecl A) {
      ConstraintSet set = (ConstraintSet)constraintsMap.get(T);
      set.equaltypeConstraints.add(A);
      //System.out.println(T.name() + " = " + A.fullName());
    }
    
    public void convertibleTo(TypeDecl A, TypeDecl F) {
      //System.out.println("Convertible to called with " + A.fullName() + "(" + A.getClass().getName() + ")" + " and " + F.fullName() + "(" + F.getClass().getName() + ")");
      // If F does not involve a type parameter Tj then con constraint is implied on Tj
      if(!F.involvesTypeParameters())
        return;
      // If A is the type of null, no constraint is implied on Tj.
      if(A.isNull())
        return;
      // If A is a primitive type, then A is converted to a reference type U via boxing conversion
      // and this algorithm is applied recursively to the constraint U << F.
      if(A.isUnboxedPrimitive()) {
        TypeDecl U = A.boxed();
        convertibleTo(U, F);
      }
      // If F = Tj, then the constrint Tj :> A is implied
      else if(F instanceof TypeVariable) {
        if(typeVariables.contains(F))
          addSupertypeConstraint(F, A);
      }
      // If F = U[], where the type U involves Tj, then if A is an array type V[]
      // or a type variable with an upper bound that is an array type V[],
      // where V is a reference type, this algorithm is applied recursively
      // to the constraint V << U
      else if(F.isArrayDecl()) {
        //System.out.println("convertibleTo array decl");
        TypeDecl U = ((ArrayDecl)F).componentType();
        if(!U.involvesTypeParameters())
          return;
        if(A.isArrayDecl()) {
          TypeDecl V = ((ArrayDecl)A).componentType();
          if(V.isReferenceType())
            convertibleTo(V, U);
        }
        else if(A.isTypeVariable()) {
          TypeVariable t = (TypeVariable)A;
          for(int i = 0; i < t.getNumTypeBound(); i++) {
            TypeDecl typeBound = t.getTypeBound(i).type();
            if(typeBound.isArrayDecl() && ((ArrayDecl)typeBound).componentType().isReferenceType()) {
              TypeDecl V = ((ArrayDecl)typeBound).componentType();
              convertibleTo(V, U);
            }
          }
        }
      }
      else if(F instanceof ParTypeDecl && !F.isRawType()) {
        for(Iterator iter = parameterizedSupertypes(A).iterator(); iter.hasNext(); ) {
          ParTypeDecl PF = (ParTypeDecl)F;
          ParTypeDecl PA = (ParTypeDecl)iter.next();
          if(PF.genericDecl() == PA.genericDecl()) {
            for(int i = 0; i < PF.getNumArgument(); i++) {
              TypeDecl T = PF.getArgument(i).type();
              if(T.involvesTypeParameters()) {
                if(!T.isWildcard()) {
                  TypeDecl U = T;
                  TypeDecl V = PA.getArgument(i).type();
                  constraintEqual(V, U);
                }
                else if(T instanceof WildcardExtendsType) {
                  TypeDecl U = ((WildcardExtendsType)T).getAccess().type();
                  TypeDecl S = PA.getArgument(i).type();
                  if(!S.isWildcard()) {
                    TypeDecl V = S;
                    convertibleTo(V, U);
                  }
                  else if(S instanceof WildcardExtendsType) {
                    TypeDecl V = ((WildcardExtendsType)S).getAccess().type();
                    convertibleTo(V, U);
                  }
                }
                else if(T instanceof WildcardSuperType) {
                  TypeDecl U = ((WildcardSuperType)T).getAccess().type();
                  TypeDecl S = PA.getArgument(i).type();
                  if(!S.isWildcard()) {
                    TypeDecl V = S;
                    convertibleFrom(V, U);
                  }
                  else if(S instanceof WildcardSuperType) {
                    TypeDecl V = ((WildcardSuperType)S).getAccess().type();
                    convertibleFrom(V, U);
                  }
                }
              }
            }
          }
        }
      }
    }


    public void convertibleFrom(TypeDecl A, TypeDecl F) {
      //System.out.println("ConvertibleFrom called with " + A.fullName() + "(" + A.getClass().getName() + ")" + " and " + F.fullName() + "(" + F.getClass().getName() + ")");
      // If F does not involve a type parameter Tj then con constraint is implied on Tj
      if(!F.involvesTypeParameters())
        return;
      // If A is the type of null, no constraint is implied on Tj.
      else if(A.isNull())
        return;
      else if(F instanceof TypeVariable) {
        if(typeVariables.contains(F))
          addSubtypeConstraint(F, A);
      }
      else if(F.isArrayDecl()) {
        TypeDecl U = ((ArrayDecl)F).componentType();
        if(A.isArrayDecl()) {
          TypeDecl V = ((ArrayDecl)A).componentType();
          convertibleFrom(V, U);
        }
        else if(A.isTypeVariable()) {
          TypeVariable t = (TypeVariable)A;
          for(int i = 0; i < t.getNumTypeBound(); i++) {
            TypeDecl typeBound = t.getTypeBound(i).type();
            if(typeBound.isArrayDecl() && ((ArrayDecl)typeBound).componentType().isReferenceType()) {
              TypeDecl V = ((ArrayDecl)typeBound).componentType();
              convertibleFrom(V, U);
            }
          }
        }
      }
      else if(F instanceof ParTypeDecl && !F.isRawType() && A instanceof ParTypeDecl && !A.isRawType()) {
        ParTypeDecl PF = (ParTypeDecl)F;
        ParTypeDecl PA = (ParTypeDecl)A;
        TypeDecl G = PF.genericDecl();
        TypeDecl H = PA.genericDecl();
        for(int i = 0; i < PF.getNumArgument(); i++) {
          TypeDecl T = PF.getArgument(i).type();
          if(T.involvesTypeParameters()) {
            // If F has the form G<...,U,...> where U is a type expression that involves Tj
            if(!T.isWildcard()) {
              TypeDecl U = T;
              if(G.instanceOf(H)) {
                if(H != G) {
                  for(Iterator iter = parameterizedSupertypes(F).iterator(); iter.hasNext(); ) {
                    TypeDecl V = (TypeDecl)iter.next();
                    if(((ParTypeDecl)V).genericDecl() == H) {
                      if(F.instanceOf(V))
                        convertibleFrom(A, V);
                    }
                  }
                }
                else if(PF.getNumArgument() == PA.getNumArgument()) {
                  TypeDecl X = PA.getArgument(i).type();
                  if(!X.isWildcard()) {
                    TypeDecl W = X;
                    constraintEqual(W, U);
                  }
                  else if(X instanceof WildcardExtendsType) {
                    TypeDecl W = ((WildcardExtendsType)X).getAccess().type();
                    convertibleFrom(W, U);
                  }
                  else if(X instanceof WildcardSuperType) {
                    TypeDecl W = ((WildcardSuperType)X).getAccess().type();
                    convertibleTo(W, U);
                  }
                }
              }
            }
            else if(T instanceof WildcardExtendsType) {
              TypeDecl U = ((WildcardExtendsType)T).getAccess().type();
              if(G.instanceOf(H)) {
                if(H != G) {
                  for(Iterator iter = parameterizedSupertypes(F).iterator(); iter.hasNext(); ) {
                    TypeDecl V = (TypeDecl)iter.next();
                    if(((ParTypeDecl)V).genericDecl() == H) {
                      // replace type argument Un with ? extends Un in V
                      ArrayList list = new ArrayList();
                      for(int j = 0; j < ((ParTypeDecl)V).getNumArgument(); j++)
                        list.add(((ParTypeDecl)V).getArgument(j).type().asWildcardExtends());
                      V = ((GenericTypeDecl)H).lookupParTypeDecl(list);
                      convertibleFrom(A, V);
                    }
                  }
                }
                else if(PF.getNumArgument() == PA.getNumArgument()) {
                  TypeDecl X = PA.getArgument(i).type();
                  if(X instanceof WildcardExtendsType) {
                    TypeDecl W = ((WildcardExtendsType)X).getAccess().type();
                    convertibleFrom(W, U);
                  }
                }
              }
            }
            else if(T instanceof WildcardSuperType) {
              TypeDecl U = ((WildcardSuperType)T).getAccess().type();
              if(G.instanceOf(H)) {
                if(H != G) {
                  for(Iterator iter = parameterizedSupertypes(F).iterator(); iter.hasNext(); ) {
                    TypeDecl V = (TypeDecl)iter.next();
                    if(((ParTypeDecl)V).genericDecl() == H) {
                      // replace type argument Un with ? super Un in V
                      ArrayList list = new ArrayList();
                      for(int j = 0; j < ((ParTypeDecl)V).getNumArgument(); j++)
                        list.add(((ParTypeDecl)V).getArgument(j).type().asWildcardExtends());
                      V = ((GenericTypeDecl)H).lookupParTypeDecl(list);
                      convertibleFrom(A, V);
                    }
                  }
                }
                else if(PF.getNumArgument() == PA.getNumArgument()) {
                  TypeDecl X = PA.getArgument(i).type();
                  if(X instanceof WildcardSuperType) {
                    TypeDecl W = ((WildcardSuperType)X).getAccess().type();
                    convertibleTo(W, U);
                  }
                }
              }
            }
          }
        }
      }
    }

    public void constraintEqual(TypeDecl A, TypeDecl F) {
      //System.out.println("ConstraintEqual called with " + A.fullName() + "(" + A.getClass().getName() + ")" + " and " + F.fullName() + "(" + F.getClass().getName() + ")");
      // If F does not involve a type parameter Tj then con constraint is implied on Tj
      if(!F.involvesTypeParameters())
        return;
      // If A is the type of null, no constraint is implied on Tj.
      else if(A.isNull())
        return;
      else if(F instanceof TypeVariable) {
        if(typeVariables.contains(F))
          addEqualConstraint(F, A);
      }
      else if(F.isArrayDecl()) {
        TypeDecl U = ((ArrayDecl)F).componentType();
        if(A.isArrayDecl()) {
          TypeDecl V = ((ArrayDecl)A).componentType();
          constraintEqual(V, U);
        }
        else if(A.isTypeVariable()) {
          TypeVariable t = (TypeVariable)A;
          for(int i = 0; i < t.getNumTypeBound(); i++) {
            TypeDecl typeBound = t.getTypeBound(i).type();
            if(typeBound.isArrayDecl() && ((ArrayDecl)typeBound).componentType().isReferenceType()) {
              TypeDecl V = ((ArrayDecl)typeBound).componentType();
              constraintEqual(V, U);
            }
          }
        }
      }
      else if(F instanceof ParTypeDecl && !F.isRawType()) {
        if(A instanceof ParTypeDecl && !A.isRawType()) {
          ParTypeDecl PF = (ParTypeDecl)F;
          ParTypeDecl PA = (ParTypeDecl)A;
          if(PF.genericDecl() == PA.genericDecl()) {
            for(int i = 0; i < PF.getNumArgument(); i++) {
              TypeDecl T = PF.getArgument(i).type();
              if(T.involvesTypeParameters()) {
                if(!T.isWildcard()) {
                  TypeDecl U = T;
                  TypeDecl V = PA.getArgument(i).type();
                  constraintEqual(V, U);
                }
                else if(T instanceof WildcardExtendsType) {
                  TypeDecl U = ((WildcardExtendsType)T).getAccess().type();
                  TypeDecl S = PA.getArgument(i).type();
                  if(S instanceof WildcardExtendsType) {
                    TypeDecl V = ((WildcardExtendsType)S).getAccess().type();
                    constraintEqual(V, U);
                  }
                }
                else if(T instanceof WildcardSuperType) {
                  TypeDecl U = ((WildcardSuperType)T).getAccess().type();
                  TypeDecl S = PA.getArgument(i).type();
                  if(S instanceof WildcardSuperType) {
                    TypeDecl V = ((WildcardSuperType)S).getAccess().type();
                    constraintEqual(V, U);
                  }
                }
              }
            }
          }
        }
      }
    }
  }

  syn lazy TypeDecl LUBType.lub() {
    ArrayList list = new ArrayList();
    for(int i = 0; i < getNumTypeBound(); i++)
      list.add(getTypeBound(i).type());
    ArrayList bounds = new ArrayList();
    for(Iterator iter = MEC(list).iterator(); iter.hasNext(); ) {
      TypeDecl W = (TypeDecl)iter.next();
      TypeDecl C = W instanceof GenericTypeDecl ? lci(Inv(W, list), W) : W;
      bounds.add(C);
    }
    if(bounds.size() == 1)
      return (TypeDecl)bounds.iterator().next();
    return lookupLUBType(bounds);
  }

    // the erased candidate set for type parameter Tj, EC,
    // is the intersection of all the sets EST(U) for each
    // U in U1...Uk
    public HashSet LUBType.EC(ArrayList list) {
      HashSet result = new HashSet();
      boolean first = true;
      for(Iterator iter = list.iterator(); iter.hasNext(); ) {
        TypeDecl U = (TypeDecl)iter.next();
        // erased supertype set of U
        HashSet EST = EST(U); 
        if(first) {
          result.addAll(EST);
          first = false;
        }
        else
          result.retainAll(EST);
      }
      return result;
    }

    // The minimal erased candidate set for Tj
    // is MEC = {V | V in EC, forall  W != V in EC, not W <: V}
    public HashSet LUBType.MEC(ArrayList list) {
      HashSet EC = EC(list);
      if(EC.size() == 1)
        return EC;
      HashSet MEC = new HashSet();
      for(Iterator iter = EC.iterator(); iter.hasNext(); ) {
        TypeDecl V = (TypeDecl)iter.next();
        boolean keep = true;
        for(Iterator i2 = EC.iterator(); i2.hasNext(); ) {
          TypeDecl W = (TypeDecl)i2.next();
          if(!(V instanceof TypeVariable) && V != W && W.instanceOf(V))
            keep = false;
        }
        if(keep)
          MEC.add(V);
      }
      return MEC;
    }

    // relevant invocations of G, Inv(G)
    // Inv(G) = {V | 1 <= i <= k, V in ST(Ui), V = G<...>}
    public HashSet LUBType.Inv(TypeDecl G, ArrayList Us) {
      HashSet result = new HashSet();
      for(Iterator iter = Us.iterator(); iter.hasNext(); ) {
        TypeDecl U = (TypeDecl)iter.next();
        for(Iterator i2 = ST(U).iterator(); i2.hasNext(); ) {
          TypeDecl V = (TypeDecl)i2.next();
          if(V instanceof ParTypeDecl && !V.isRawType() && ((ParTypeDecl)V).genericDecl() == G)
            result.add(V);
        }
      }
      return result;
    }

    // least containing invocation (lci)
    public TypeDecl LUBType.lci(HashSet set, TypeDecl G) {
      ArrayList list = new ArrayList();
      boolean first = true;
      for(Iterator iter = set.iterator(); iter.hasNext(); ) {
        ParTypeDecl decl = (ParTypeDecl)iter.next();
        if(first) {
          first = false;
          for(int i = 0; i < decl.getNumArgument(); i++)
            list.add(decl.getArgument(i).type());
        }
        else {
          for(int i = 0; i < decl.getNumArgument(); i++)
            list.set(i, lcta((TypeDecl)list.get(i), decl.getArgument(i).type()));
        }
      }
      return ((GenericTypeDecl)G).lookupParTypeDecl(list);
    }

    // least containing type arguments
    public TypeDecl LUBType.lcta(TypeDecl X, TypeDecl Y) {
      //System.err.println("Computing lcta for " + X.typeName() + " and " + Y.typeName());
      if(!X.isWildcard() && !Y.isWildcard()) {
        TypeDecl U = X;
        TypeDecl V = Y;
        return U == V ? U : lub(U, V).asWildcardExtends();
      }
      else if(!X.isWildcard() && Y instanceof WildcardExtendsType) {
        TypeDecl U = X;
        TypeDecl V = ((WildcardExtendsType)Y).getAccess().type();
        return lub(U, V).asWildcardExtends();
      }
      else if(!X.isWildcard() && Y instanceof WildcardSuperType) {
        TypeDecl U = X;
        TypeDecl V = ((WildcardSuperType)Y).getAccess().type();
        ArrayList bounds = new ArrayList();
        bounds.add(U);
        bounds.add(V);
        return GLBTypeFactory.glb(bounds).asWildcardSuper();
      }
      else if(X instanceof WildcardExtendsType && Y instanceof WildcardExtendsType) {
        TypeDecl U = ((WildcardExtendsType)X).getAccess().type();
        TypeDecl V = ((WildcardExtendsType)Y).getAccess().type();
        return lub(U, V).asWildcardExtends();
      }
      else if(X instanceof WildcardExtendsType && Y instanceof WildcardSuperType) {
        TypeDecl U = ((WildcardExtendsType)X).getAccess().type();
        TypeDecl V = ((WildcardSuperType)Y).getAccess().type();
        return U == V ? U : U.typeWildcard();
      }
      else if(X instanceof WildcardSuperType && Y instanceof WildcardSuperType) {
        TypeDecl U = ((WildcardSuperType)X).getAccess().type();
        TypeDecl V = ((WildcardSuperType)Y).getAccess().type();
        ArrayList bounds = new ArrayList();
        bounds.add(U);
        bounds.add(V);
        return GLBTypeFactory.glb(bounds).asWildcardSuper();
      }
      else
        throw new Error("lcta not defined for (" + X.getClass().getName() + ", " + Y.getClass().getName());
    }

    public TypeDecl LUBType.lub(TypeDecl X, TypeDecl Y) {
      ArrayList list = new ArrayList(2);
      list.add(X);
      list.add(Y);
      return lub(list);
    }

    public TypeDecl LUBType.lub(ArrayList list) {
      return lookupLUBType(list);
    }

    // erased supertype set of T
    public HashSet LUBType.EST(TypeDecl t) {
      HashSet result = new HashSet();
      for(Iterator iter = ST(t).iterator(); iter.hasNext(); ) {
        TypeDecl typeDecl = (TypeDecl)iter.next();
        if(typeDecl instanceof TypeVariable)
          result.add(typeDecl);
        else
          result.add(typeDecl.erasure());
      }
      return result;
    }

    // supertype set of T
    public HashSet LUBType.ST(TypeDecl t) {
      HashSet result = new HashSet();
      addSupertypes(result, t);
      return result;
    }

    public void LUBType.addSupertypes(HashSet set, TypeDecl t) {
      set.add(t);
      if(t instanceof ClassDecl) {
        ClassDecl type = (ClassDecl)t;
        if(type.hasSuperclass()) {
          addSupertypes(set, type.superclass());
        }
        for(int i = 0; i < type.getNumImplements(); i++) {
          addSupertypes(set, type.getImplements(i).type());
        }
      }
      else if(t instanceof InterfaceDecl) {
        InterfaceDecl type = (InterfaceDecl)t;
        for(int i = 0; i < type.getNumSuperInterfaceId(); i++) {
          addSupertypes(set, type.getSuperInterfaceId(i).type());
        }
        if(type.getNumSuperInterfaceId() == 0)
          set.add(type.typeObject());
      }
      else if(t instanceof TypeVariable) {
        TypeVariable type = (TypeVariable)t;
        for(int i = 0; i < type.getNumTypeBound(); i++) {
          addSupertypes(set, type.getTypeBound(i).type());
        }
        if(type.getNumTypeBound() == 0)
          set.add(type.typeObject());
      }
      else if(t instanceof LUBType) {
        LUBType type = (LUBType)t;
        for(int i = 0; i < type.getNumTypeBound(); i++) {
          addSupertypes(set, type.getTypeBound(i).type());
        }
        if(type.getNumTypeBound() == 0)
          set.add(type.typeObject());
      }
      else
        throw new Error("Operation not supported for " + t.fullName() + ", " + t.getClass().getName());
    }

}