Clover coverage report - DynamicJava Test Coverage (dynamicjava-20130518-r5436)
Coverage timestamp: Sat May 18 2013 03:01:28 CDT
Overview   Package   File
    FRAMES   NO FRAMES  
file stats: LOC: 1,259   Methods: 225
NCLOC: 1,014   Classes: 12
 
 Source file Conditionals Statements Methods TOTAL
ExtendedTypeSystem.java 39.7% 51.4% 52% 49.5%
coverage coverage
 1    package edu.rice.cs.dynamicjava.symbol;
 2   
 3    import java.util.*;
 4    import edu.rice.cs.plt.tuple.Pair;
 5    import edu.rice.cs.plt.tuple.Option;
 6    import edu.rice.cs.plt.tuple.Wrapper;
 7    import edu.rice.cs.plt.recur.*;
 8    import edu.rice.cs.plt.lambda.*;
 9    import edu.rice.cs.plt.iter.IterUtil;
 10    import edu.rice.cs.plt.collect.CollectUtil;
 11    import edu.rice.cs.plt.collect.Order;
 12   
 13    import edu.rice.cs.dynamicjava.Options;
 14    import edu.rice.cs.dynamicjava.symbol.type.*;
 15   
 16    import static edu.rice.cs.plt.iter.IterUtil.map;
 17    import static edu.rice.cs.plt.iter.IterUtil.singleton;
 18    import static edu.rice.cs.plt.iter.IterUtil.collapse;
 19    import static edu.rice.cs.plt.collect.CollectUtil.maxList;
 20    import static edu.rice.cs.plt.collect.CollectUtil.minList;
 21    import static edu.rice.cs.plt.collect.CollectUtil.composeMaxLists;
 22    import static edu.rice.cs.plt.collect.CollectUtil.union;
 23    import static edu.rice.cs.plt.collect.CollectUtil.intersection;
 24    import static edu.rice.cs.plt.lambda.LambdaUtil.bindFirst;
 25    import static edu.rice.cs.plt.lambda.LambdaUtil.bindSecond;
 26    import static edu.rice.cs.plt.debug.DebugUtil.debug;
 27   
 28    public class ExtendedTypeSystem extends StandardTypeSystem {
 29   
 30    /** Whether the inference algorithm should attempt to pack capture variables that appear as inference results. */
 31    private final boolean _packCaptureVars;
 32   
 33  2 public ExtendedTypeSystem(Options opt) { this(opt, true, true, true, true); }
 34   
 35  2 public ExtendedTypeSystem(Options opt, boolean packCaptureVars, boolean boxingInMostSpecific,
 36    boolean useExplicitTypeArgs, boolean strictClassEquality) {
 37  2 super(opt, boxingInMostSpecific, useExplicitTypeArgs, strictClassEquality);
 38  2 _packCaptureVars = packCaptureVars;
 39    }
 40   
 41    /** Determine if the type is well-formed. */
 42  2199 public boolean isWellFormed(Type t) {
 43  2199 return new WellFormedChecker().contains(t);
 44    }
 45   
 46    /**
 47    * Tests well-formedness for normalized types. Due to its use of internal state, unrelated (and possibly parallel)
 48    * invocations should use distinct instances.
 49    */
 50    private class WellFormedChecker extends TypeAbstractVisitor<Boolean> implements Predicate<Type> {
 51    RecursionStack<Type> _stack = new RecursionStack<Type>(Wrapper.<Type>factory());
 52  2709 public boolean contains(Type t) { return t.apply(this); }
 53   
 54  1179 @Override public Boolean defaultCase(Type t) { return true; }
 55  116 @Override public Boolean forArrayType(ArrayType t) { return t.ofType().apply(this); }
 56  1429 @Override public Boolean forSimpleClassType(SimpleClassType t) {
 57  1429 return IterUtil.isEmpty(SymbolUtil.allTypeParameters(t.ofClass()));
 58    }
 59  2 @Override public Boolean forRawClassType(RawClassType t) {
 60  2 return !IterUtil.isEmpty(SymbolUtil.allTypeParameters(t.ofClass()));
 61    }
 62  510 @Override public Boolean forParameterizedClassType(ParameterizedClassType t) {
 63  510 Iterable<? extends Type> args = t.typeArguments();
 64  510 if (IterUtil.and(args, this)) {
 65  508 Iterable<VariableType> params = SymbolUtil.allTypeParameters(t.ofClass());
 66  508 if (IterUtil.sizeOf(params) == IterUtil.sizeOf(args)) {
 67  508 Iterable<Type> captArgs = captureTypeArgs(args, params);
 68  508 for (Pair<Type, Type> pair : IterUtil.zip(args, captArgs)) {
 69  0 if (pair.first() != pair.second() && !pair.second().apply(this)) { return false; }
 70    }
 71  508 return inBounds(params, captArgs);
 72    }
 73    }
 74  2 return false;
 75    }
 76  0 @Override public Boolean forBoundType(BoundType t) {
 77  0 return IterUtil.and(t.ofTypes(), this);
 78    }
 79  305 @Override public Boolean forVariableType(final VariableType t) {
 80  305 Thunk<Boolean> checkVar = new Thunk<Boolean>() {
 81  305 public Boolean value() { return checkBoundedSymbol(t.symbol()); }
 82    };
 83  305 return _stack.apply(checkVar, true, t);
 84    }
 85  54 @Override public Boolean forWildcard(Wildcard w) {
 86  54 return checkBoundedSymbol(w.symbol());
 87    }
 88  359 private boolean checkBoundedSymbol(BoundedSymbol s) {
 89  359 Type lower = s.lowerBound();
 90  359 Type upper = s.upperBound();
 91  359 return lower.apply(this) && upper.apply(this) && isSubtype(lower, upper);
 92    }
 93    }
 94   
 95    /** Determine if the given types may be treated as equal. This is recursive, transitive, and symmetric. */
 96  781 public boolean isEqual(Type t1, Type t2) {
 97    //debug.logStart(new String[]{"t1","t2"}, wrap(t1), wrap(t2)); try {
 98   
 99  677 if (t1.equals(t2)) { return true; }
 100    else {
 101  104 NormSubtyper sub = new NormSubtyper();
 102  104 Normalizer norm = new Normalizer(sub);
 103  104 Type t1Norm = norm.value(t1);
 104  104 Type t2Norm = norm.value(t2);
 105  104 return sub.contains(t1Norm, t2Norm) && sub.contains(t2Norm, t1Norm);
 106    }
 107   
 108    //} finally { debug.logEnd(); }
 109    }
 110   
 111    /**
 112    * Determine if {@code subT} is a subtype of {@code superT}. This is a recursive
 113    * (in terms of {@link #isEqual}), transitive relation.
 114    */
 115  4195 public boolean isSubtype(Type subT, Type superT) {
 116  4195 NormSubtyper sub = new NormSubtyper();
 117  4195 Normalizer norm = new Normalizer(sub);
 118  4195 return sub.contains(norm.value(subT), norm.value(superT));
 119    }
 120   
 121    /**
 122    * Tests subtyping for normalized types. Due to its use of internal state, unrelated (and possibly parallel)
 123    * invocations should use distinct instances.
 124    */
 125    private class NormSubtyper implements Order<Type>, Lambda2<Type, Type, Boolean> {
 126    RecursionStack2<Type, Type> _stack = new RecursionStack2<Type, Type>(Pair.<Type, Type>factory());
 127   
 128  0 public Boolean value(Type subT, Type superT) { return contains(subT, superT); }
 129   
 130  8 public Predicate<Type> supertypes(Type sub) { return bindFirst((Order<Type>) this, sub); }
 131   
 132  1263 public Predicate<Type> subtypes(Type sup) { return bindSecond((Order<Type>) this, sup); }
 133   
 134  45083 public boolean contains(final Type subT, final Type superT) {
 135    //debug.logStart(new String[]{"subT", "superT"}, wrap(subT), wrap(superT)); try {
 136   
 137  6171 if (subT.equals(superT)) { return true; } // what follows assumes the types are not syntactically equal
 138   
 139    // Handle easy superT cases; return null if subT cases need to be considered, too
 140  38912 Boolean result = superT.apply(new TypeAbstractVisitor<Boolean>() {
 141  38737 public Boolean defaultCase(Type superT) { return null; }
 142   
 143  167 @Override public Boolean forVariableType(final VariableType superT) {
 144  167 return subT.apply(new TypeAbstractVisitor<Boolean>() {
 145  167 @Override public Boolean defaultCase(final Type subT) {
 146  167 Thunk<Boolean> checkLowerBound = new Thunk<Boolean>() {
 147  167 public Boolean value() {
 148  167 Type bound = new Normalizer(NormSubtyper.this).value(superT.symbol().lowerBound());
 149  167 return NormSubtyper.this.contains(subT, bound);
 150    }
 151    };
 152  167 Thunk<Boolean> checkInfinite = new Thunk<Boolean>() {
 153  0 public Boolean value() { return NormSubtyper.this.contains(subT, NULL); }
 154    };
 155  167 return _stack.apply(checkLowerBound, checkInfinite, subT, superT);
 156    }
 157  0 @Override public Boolean forVariableType(VariableType subT) {
 158  0 return defaultCase(subT) ? true : null;
 159    }
 160  0 @Override public Boolean forIntersectionType(IntersectionType subT) {
 161  0 return defaultCase(subT) ? true : null;
 162    }
 163  0 @Override public Boolean forUnionType(UnionType subT) { return null; }
 164  0 @Override public Boolean forBottomType(BottomType subT) { return true; }
 165    });
 166    }
 167   
 168  0 @Override public Boolean forIntersectionType(final IntersectionType superT) {
 169  0 return subT.apply(new TypeAbstractVisitor<Boolean>() {
 170  0 @Override public Boolean defaultCase(Type subT) {
 171  0 return IterUtil.and(superT.ofTypes(), supertypes(subT));
 172    }
 173  0 @Override public Boolean forUnionType(UnionType subT) { return null; }
 174  0 @Override public Boolean forBottomType(BottomType subT) { return true; }
 175    });
 176    }
 177   
 178  8 @Override public Boolean forUnionType(final UnionType superT) {
 179  8 return subT.apply(new TypeAbstractVisitor<Boolean>() {
 180  8 @Override public Boolean defaultCase(Type t) {
 181  8 return IterUtil.or(superT.ofTypes(), supertypes(subT));
 182    }
 183  0 @Override public Boolean forVariableType(VariableType t) { return defaultCase(subT) ? true : null; }
 184  0 @Override public Boolean forIntersectionType(IntersectionType t) { return null; }
 185  0 @Override public Boolean forUnionType(UnionType t) { return null; }
 186  0 @Override public Boolean forBottomType(BottomType t) { return true; }
 187    });
 188    }
 189   
 190  0 @Override public Boolean forTopType(TopType superT) { return true; }
 191    });
 192   
 193  175 if (result != null) { return result; }
 194   
 195    // Handle subT-based cases:
 196  38737 return subT.apply(new TypeAbstractVisitor<Boolean>() {
 197   
 198  32 @Override public Boolean defaultCase(Type t) { return false; }
 199   
 200  13 @Override public Boolean forCharType(CharType subT) {
 201  13 return superT.apply(new TypeAbstractVisitor<Boolean>() {
 202  5 public Boolean defaultCase(Type superT) { return false; }
 203  0 @Override public Boolean forCharType(CharType superT) { return true; }
 204  2 @Override public Boolean forIntType(IntType superT) { return true; }
 205  2 @Override public Boolean forLongType(LongType superT) { return true; }
 206  4 @Override public Boolean forFloatingPointType(FloatingPointType superT) { return true; }
 207    });
 208    }
 209   
 210  15 @Override public Boolean forByteType(ByteType subT) {
 211  15 return superT.apply(new TypeAbstractVisitor<Boolean>() {
 212  8 public Boolean defaultCase(Type superT) { return false; }
 213  7 @Override public Boolean forIntegerType(IntegerType superT) { return true; }
 214  0 @Override public Boolean forFloatingPointType(FloatingPointType superT) { return true; }
 215    });
 216    }
 217   
 218  15 @Override public Boolean forShortType(ShortType subT) {
 219  15 return superT.apply(new TypeAbstractVisitor<Boolean>() {
 220  8 public Boolean defaultCase(Type superT) { return false; }
 221  0 @Override public Boolean forShortType(ShortType superT) { return true; }
 222  7 @Override public Boolean forIntType(IntType superT) { return true; }
 223  0 @Override public Boolean forLongType(LongType superT) { return true; }
 224  0 @Override public Boolean forFloatingPointType(FloatingPointType superT) { return true; }
 225    });
 226    }
 227   
 228  244 @Override public Boolean forIntType(IntType subT) {
 229  244 return superT.apply(new TypeAbstractVisitor<Boolean>() {
 230  243 public Boolean defaultCase(Type superT) { return false; }
 231  0 @Override public Boolean forIntType(IntType superT) { return true; }
 232  0 @Override public Boolean forLongType(LongType superT) { return true; }
 233  1 @Override public Boolean forFloatingPointType(FloatingPointType superT) { return true; }
 234    });
 235    }
 236   
 237  9 @Override public Boolean forLongType(LongType subT) {
 238  9 return superT.apply(new TypeAbstractVisitor<Boolean>() {
 239  9 public Boolean defaultCase(Type superT) { return false; }
 240  0 @Override public Boolean forLongType(LongType superT) { return true; }
 241  0 @Override public Boolean forFloatingPointType(FloatingPointType superT) { return true; }
 242    });
 243    }
 244   
 245  44 @Override public Boolean forFloatType(FloatType subT) { return superT instanceof FloatingPointType; }
 246   
 247  1091 @Override public Boolean forNullType(NullType subT) { return isReference(superT); }
 248   
 249  8 @Override public Boolean forSimpleArrayType(SimpleArrayType subT) { return handleArrayType(subT); }
 250   
 251  0 @Override public Boolean forVarargArrayType(VarargArrayType subT) { return handleArrayType(subT); }
 252   
 253  8 private Boolean handleArrayType(final ArrayType subT) {
 254  8 return superT.apply(new TypeAbstractVisitor<Boolean>() {
 255  2 public Boolean defaultCase(Type superT) { return false; }
 256   
 257  4 @Override public Boolean forArrayType(ArrayType superT) {
 258  4 if (isPrimitive(subT.ofType())) {
 259    // types may be inequal if one is vararg and the other is not
 260  2 return subT.ofType().equals(superT.ofType());
 261    }
 262  2 else { return NormSubtyper.this.contains(subT.ofType(), superT.ofType()); }
 263    }
 264   
 265  2 @Override public Boolean forClassType(ClassType superT) {
 266  2 return NormSubtyper.this.contains(CLONEABLE_AND_SERIALIZABLE, superT);
 267    }
 268   
 269    });
 270    }
 271   
 272    /**
 273    * Recur on {@code newSub}, a class's parent type. {@code newSub} may be null, as in
 274    * {@code immediateSupertype()}.
 275    */
 276  39462 private Boolean recurOnClassParent(final Type newSub) {
 277  13590 if (newSub == null) { return false; }
 278    else {
 279  25872 Thunk<Boolean> recurOnParent = new Thunk<Boolean>() {
 280  25780 public Boolean value() {
 281  25780 Type newSubNorm = new Normalizer(NormSubtyper.this).value(newSub);
 282  25780 return NormSubtyper.this.contains(newSubNorm, superT);
 283    }
 284    };
 285  25872 return _stack.apply(recurOnParent, false, newSub, superT);
 286    }
 287    }
 288   
 289  21850 @Override public Boolean forSimpleClassType(final SimpleClassType subT) {
 290  21850 return superT.apply(new TypeAbstractVisitor<Boolean>() {
 291  71 public Boolean defaultCase(Type superT) { return false; }
 292  21779 @Override public Boolean forClassType(final ClassType superT) {
 293  21779 return recurOnClassParent(immediateSupertype(subT));
 294    }
 295  14729 @Override public Boolean forSimpleClassType(final SimpleClassType superT) {
 296  14729 return sameClass(subT, superT) || forClassType(superT);
 297    }
 298    });
 299    }
 300   
 301  9079 @Override public Boolean forRawClassType(final RawClassType subT) {
 302  9079 return superT.apply(new TypeAbstractVisitor<Boolean>() {
 303  1 public Boolean defaultCase(Type superT) { return false; }
 304  9078 @Override public Boolean forClassType(final ClassType superT) {
 305  9078 return recurOnClassParent(immediateSupertype(subT));
 306    }
 307  1154 @Override public Boolean forRawClassType(final RawClassType superT) {
 308  1154 return sameClass(subT, superT) || forClassType(superT);
 309    }
 310  2873 @Override public Boolean forParameterizedClassType(final ParameterizedClassType superT) {
 311  2873 if (sameClass(subT, superT)) {
 312  92 return recurOnClassParent(parameterize(subT)) || forClassType(superT);
 313    }
 314  2781 else { return forClassType(superT); }
 315    }
 316    });
 317    }
 318   
 319  4836 @Override public Boolean forParameterizedClassType(final ParameterizedClassType subT) {
 320  4836 return superT.apply(new TypeAbstractVisitor<Boolean>() {
 321  11 public Boolean defaultCase(Type superT) { return false; }
 322  4663 @Override public Boolean forClassType(ClassType superT) {
 323  4663 return recurOnClassParent(immediateSupertype(subT)) || recurOnClassParent(erase(subT));
 324    }
 325  1671 @Override public Boolean forParameterizedClassType(final ParameterizedClassType superT) {
 326  1671 if (sameClass(subT, superT)) {
 327  342 boolean containedArgs = true;
 328  342 ParameterizedClassType subCapT = capture(subT);
 329  342 for (final Pair<Type, Type> args : IterUtil.zip(subCapT.typeArguments(),
 330    superT.typeArguments())) {
 331  342 containedArgs &= args.second().apply(new TypeAbstractVisitor<Boolean>() {
 332  209 public Boolean defaultCase(Type superArg) {
 333  209 Type subArg = args.first();
 334  209 return NormSubtyper.this.contains(subArg, superArg) &&
 335    NormSubtyper.this.contains(superArg, subArg);
 336    }
 337  133 @Override public Boolean forWildcard(Wildcard superArg) {
 338  133 Type subArg = args.first();
 339  133 return NormSubtyper.this.contains(superArg.symbol().lowerBound(), subArg) &&
 340    NormSubtyper.this.contains(subArg, superArg.symbol().upperBound());
 341    }
 342    });
 343  180 if (!containedArgs) { break; }
 344    }
 345  342 return containedArgs || forClassType(superT);
 346    }
 347  1329 else { return forClassType(superT); }
 348    }
 349    });
 350    }
 351   
 352  238 @Override public Boolean forVariableType(final VariableType subT) {
 353  238 Thunk<Boolean> checkUpperBound = new Thunk<Boolean>() {
 354  238 public Boolean value() {
 355  238 Type bound = new Normalizer(NormSubtyper.this).value(subT.symbol().upperBound());
 356  238 return NormSubtyper.this.contains(bound, superT);
 357    }
 358    };
 359  238 Thunk<Boolean> checkInfinite = new Thunk<Boolean>() {
 360  0 public Boolean value() { return NormSubtyper.this.contains(OBJECT, superT); }
 361    };
 362  238 return _stack.apply(checkUpperBound, checkInfinite, subT, superT);
 363    }
 364   
 365  1214 @Override public Boolean forIntersectionType(IntersectionType subT) {
 366  1214 return IterUtil.or(subT.ofTypes(), subtypes(superT));
 367    }
 368   
 369  49 @Override public Boolean forUnionType(UnionType subT) {
 370  49 return IterUtil.and(subT.ofTypes(), subtypes(superT));
 371    }
 372   
 373  0 public Boolean forBottomType(BottomType subT) { return true; }
 374    });
 375   
 376    //} finally { debug.logEnd(); }
 377    }
 378    };
 379   
 380    /**
 381    * Converts the type to a normalized form:<ul>
 382    * <li>Unions are minimal, have at least two elements, and contain no nested unions.</li>
 383    * <li>Intersections are minimal, have at least two elements, and contain no nested unions or intersections.</li>
 384    * <li>All component types are normalized. (Wildcard bounds are "component types"; variable bounds and
 385    * class supertypes are not.)</li>
 386    */
 387    private final class Normalizer extends TypeUpdateVisitor {
 388   
 389    /**
 390    * Subtyper to preserve stack during circular dependencies between normalization and subtyping.
 391    * Note that the results from this subtyper may be different than the results from a fresh
 392    * subtyper, and any use should be an optimization, not something essential to correctness.
 393    */
 394    private final NormSubtyper _subtyper;
 395  31301 public Normalizer(NormSubtyper subtyper) { _subtyper = subtyper; }
 396   
 397  3490 @Override public Type forIntersectionTypeOnly(IntersectionType t, Iterable<? extends Type> normTypes) {
 398    //debug.logStart(new String[]{"t","normTypes"}, wrap(t), wrap(normTypes)); try {
 399  3490 Type result = new NormMeeter(_subtyper).value(normTypes);
 400  3490 return t.equals(result) ? t : result;
 401    //} finally { debug.logEnd(); }
 402    }
 403  360 @Override public Type forUnionTypeOnly(UnionType t, Iterable<? extends Type> normTypes) {
 404  360 Type result = new NormJoiner(_subtyper).value(normTypes);
 405  360 return t.equals(result) ? t : result;
 406    }
 407  192 @Override public Type forWildcardOnly(Wildcard w) {
 408    // we assume wildcards don't contain themselves in this type system
 409  192 BoundedSymbol b = w.symbol();
 410  192 Type newUpper = recur(b.upperBound());
 411  192 Type newLower = recur(b.lowerBound());
 412  192 if (newUpper == b.upperBound() && newLower == b.lowerBound()) { return w; }
 413  0 else { return new Wildcard(new BoundedSymbol(new Object(), newUpper, newLower)); }
 414    }
 415    };
 416   
 417  0 public Type join(Iterable<? extends Type> ts) {
 418  0 NormSubtyper sub = new NormSubtyper();
 419  0 return new NormJoiner(sub).value(map(ts, new Normalizer(sub)));
 420    }
 421   
 422    /** Produce the normalized union of normalized types (may return a union or some other form). */
 423    private class NormJoiner implements Lambda<Iterable<? extends Type>, Type> {
 424    /**
 425    * Subtyper to preserve stack during circular dependencies between normalization and subtyping.
 426    * Note that the results from this subtyper may be different than the results from a fresh
 427    * subtyper, and so any use should be an optimization, not something essential to correctness.
 428    */
 429    private final NormSubtyper _subtyper;
 430  479 public NormJoiner(NormSubtyper subtyper) { _subtyper = subtyper; }
 431  479 public Type value(Iterable<? extends Type> elements) {
 432  479 List<Type> disjuncts = maxList(collapse(map(elements, DISJUNCTS)), _subtyper);
 433  479 switch (disjuncts.size()) {
 434  0 case 0: return BOTTOM;
 435  421 case 1: return disjuncts.get(0);
 436  58 default: return new UnionType(disjuncts);
 437    }
 438    }
 439    };
 440   
 441  0 public Type meet(Iterable<? extends Type> ts) {
 442  0 NormSubtyper sub = new NormSubtyper();
 443  0 return new NormMeeter(sub).value(map(ts, new Normalizer(sub)));
 444    }
 445   
 446    /** Produce the normalized intersection of normalized types (may return a union, intersection, or some other form). */
 447    private class NormMeeter implements Lambda<Iterable<? extends Type>, Type> {
 448    /**
 449    * Subtyper to preserve stack during circular dependencies between normalization and subtyping.
 450    * Note that the results from this subtyper may be different than the results from a fresh
 451    * subtyper, and so any use should be an optimization, not something essential to correctness.
 452    */
 453    private final NormSubtyper _subtyper;
 454  3609 public NormMeeter(NormSubtyper subtyper) { _subtyper = subtyper; }
 455   
 456  3583 public Type value(Iterable<? extends Type> elements) {
 457  3583 if (IterUtil.or(elements, bindSecond(LambdaUtil.INSTANCE_OF, UnionType.class))) {
 458  0 final NormJoiner joiner = new NormJoiner(_subtyper);
 459    // elements contain at least one union
 460  0 Iterable<Iterable<Type>> posElements = map(elements, new Lambda<Type, Iterable<Type>>() {
 461  0 public Iterable<Type> value(Type element) {
 462    // convert sum-of-products (normalized) form to product-of-sums
 463    // javac 1.5/1.6 requires explicit type args
 464  0 return IterUtil.<Type, Type, Type, Type, Iterable<Type>>
 465    distribute(element, DISJUNCTS, CONJUNCTS, joiner, LambdaUtil.<Iterable<Type>>identity());
 466    }
 467    });
 468    // each element of conjuncts is atomic or a union of atomics
 469  0 List<Type> conjuncts = minList(collapse(posElements), new NormSubtyper());
 470    // convert back to sum-of-products
 471    // javac 1.5/1.6 requires explicit type args
 472  0 return IterUtil.<Iterable<Type>, Type, Type, Type, Type>
 473    distribute(conjuncts, LambdaUtil.<Iterable<Type>>identity(), DISJUNCTS, _meetAtomic, joiner);
 474    }
 475  3583 else { return _meetAtomic.value(collapse(map(elements, CONJUNCTS))); }
 476    }
 477   
 478    /** Produce the normalized intersection of atomic (not union or intersection) types. */
 479    private final Lambda<Iterable<? extends Type>, Type> _meetAtomic =
 480    new Lambda<Iterable<? extends Type>, Type>() {
 481  3583 public Type value(Iterable<? extends Type> atoms) {
 482  3583 List<Type> conjuncts = minList(atoms, _subtyper);
 483  3583 switch (conjuncts.size()) {
 484  0 case 0: return TOP;
 485  2371 case 1: return conjuncts.get(0);
 486  1212 default: return new IntersectionType(conjuncts);
 487    }
 488    }
 489    };
 490    }
 491   
 492    private final TypeVisitorLambda<Iterable<? extends Type>> DISJUNCTS =
 493    new TypeAbstractVisitor<Iterable<? extends Type>>() {
 494  1841 @Override public Iterable<? extends Type> forValidType(ValidType t) { return singleton(t); }
 495  50 @Override public Iterable<? extends Type> forUnionType(UnionType t) { return t.ofTypes(); }
 496    };
 497   
 498    private final TypeVisitorLambda<Iterable<? extends Type>> CONJUNCTS =
 499    new TypeAbstractVisitor<Iterable<? extends Type>>() {
 500  15360 @Override public Iterable<? extends Type> forValidType(ValidType t) { return singleton(t); }
 501  0 @Override public Iterable<? extends Type> forIntersectionType(IntersectionType t) { return t.ofTypes(); }
 502    };
 503   
 504  792 protected Iterable<Type> captureTypeArgs(Iterable<? extends Type> targs,
 505    Iterable<? extends VariableType> params) {
 506    // Create uninitialized placeholders for capture variables and normalized capture variables
 507  792 List<VariableType> captureVars = new LinkedList<VariableType>();
 508  792 List<VariableType> normCaptureVars = new LinkedList<VariableType>();
 509  792 List<Type> newArgs = new LinkedList<Type>();
 510  792 List<Type> normNewArgs = new LinkedList<Type>();
 511  792 for (Type arg : targs) {
 512  792 if (arg instanceof Wildcard) {
 513  336 VariableType var = new VariableType(new BoundedSymbol(new Object()));
 514  336 VariableType normVar = new VariableType(new BoundedSymbol(new Object()));
 515  336 captureVars.add(var);
 516  336 newArgs.add(var);
 517  336 normCaptureVars.add(normVar);
 518  336 normNewArgs.add(normVar);
 519    }
 520  456 else { newArgs.add(arg); normNewArgs.add(arg); }
 521    }
 522   
 523    // Initialize bounds of captureVars
 524  792 final SubstitutionMap sigma = new SubstitutionMap(params, newArgs);
 525  792 Iterator<VariableType> captureVarsI = captureVars.iterator();
 526  792 for (Pair<VariableType, Type> p : IterUtil.zip(params, targs)) {
 527  792 Type arg = p.second();
 528  792 if (arg instanceof Wildcard) {
 529  336 Wildcard argW = (Wildcard) arg;
 530  336 Type argU = argW.symbol().upperBound();
 531  336 Type argL = argW.symbol().lowerBound();
 532  336 VariableType param = p.first();
 533  336 Type paramU = substitute(param.symbol().upperBound(), sigma);
 534  336 Type paramL = substitute(param.symbol().lowerBound(), sigma);
 535  336 Type captureU = new IntersectionType(IterUtil.make(argU, paramU));
 536  336 Type captureL = new UnionType(IterUtil.make(argL, paramL));
 537  336 VariableType captureVar = captureVarsI.next();
 538  336 captureVar.symbol().initializeUpperBound(captureU);
 539  336 captureVar.symbol().initializeLowerBound(captureL);
 540    }
 541    }
 542   
 543    // Initialize bounds of normCaptureVars by normalizing captureVars bounds (must be done
 544    // in a second stage because we can't perform subtype checks on uninstantiated variables).
 545  792 Normalizer norm = new Normalizer(new NormSubtyper());
 546  792 SubstitutionMap sigmaNorm = new SubstitutionMap(captureVars, normCaptureVars);
 547  792 for (Pair<VariableType, VariableType> p : IterUtil.zip(captureVars, normCaptureVars)) {
 548  336 Type upper = substitute(norm.value(p.first().symbol().upperBound()), sigmaNorm);
 549  336 Type lower = substitute(norm.value(p.first().symbol().lowerBound()), sigmaNorm);
 550  336 p.second().symbol().initializeUpperBound(upper);
 551  336 p.second().symbol().initializeLowerBound(lower);
 552    }
 553   
 554  792 return normNewArgs;
 555    }
 556   
 557    private abstract class ConstraintFormula {
 558    public abstract boolean isSatisfiable();
 559    public abstract boolean isEmpty();
 560    public abstract Iterable<ConstraintScenario> scenarios();
 561    public abstract ConstraintFormula and(ConstraintFormula that);
 562   
 563  11 public ConstraintFormula or(ConstraintFormula that) {
 564  11 List<ConstraintScenario> scenarios = composeMaxLists(scenarios(), that.scenarios(), SCENARIO_IMPLICATION);
 565  0 if (scenarios.isEmpty()) { return FALSE; }
 566  11 else if (scenarios.size() == 1) { return scenarios.get(0); }
 567  0 else { return new DisjunctiveConstraint(scenarios); }
 568    }
 569   
 570   
 571  0 public String toString() {
 572  0 if (isEmpty()) { return "{}"; }
 573  0 else if (!isSatisfiable()) { return "{ false }"; }
 574    else {
 575  0 TypePrinter printer = typePrinter();
 576  0 StringBuilder result = new StringBuilder();
 577  0 boolean firstScenario = true;
 578  0 for (ConstraintScenario s : scenarios()) {
 579  0 if (!firstScenario) { result.append(" | "); }
 580  0 firstScenario = false;
 581  0 result.append("{ ");
 582  0 boolean firstVar = true;
 583  0 for (VariableType var : s.boundVariables()) {
 584  0 if (!firstVar) { result.append(", "); }
 585  0 firstVar = false;
 586  0 result.append(printer.print(s.lowerBound(var)));
 587  0 result.append(" <: ");
 588  0 result.append(var.symbol().name());
 589  0 result.append(" <: ");
 590  0 result.append(printer.print(s.upperBound(var)));
 591    }
 592  0 result.append(" }");
 593    }
 594  0 return result.toString();
 595    }
 596    }
 597   
 598    }
 599    private class ConstraintScenario extends ConstraintFormula {
 600    // all bounds are normalized and within range null <: T <: Object
 601    private final Map<VariableType, Type> _lowerBounds;
 602    private final Map<VariableType, Type> _upperBounds;
 603   
 604  183 protected ConstraintScenario() {
 605  183 _lowerBounds = new HashMap<VariableType, Type>();
 606  183 _upperBounds = new HashMap<VariableType, Type>();
 607    }
 608   
 609  25 protected ConstraintScenario(VariableType var, Type upper) {
 610  25 this();
 611  25 _upperBounds.put(var, upper);
 612    }
 613   
 614  37 protected ConstraintScenario(Type lower, VariableType var) {
 615  37 this();
 616  37 _lowerBounds.put(var, lower);
 617    }
 618   
 619  142 public boolean isSatisfiable() { return true; }
 620  34 public boolean isEmpty() { return _lowerBounds.isEmpty() && _upperBounds.isEmpty(); }
 621  176 public Iterable<ConstraintScenario> scenarios() { return singleton(this); }
 622   
 623  119 public ConstraintFormula and(ConstraintFormula that) {
 624  119 ConstraintFormula result = FALSE;
 625  119 for (ConstraintScenario s : that.scenarios()) {
 626  119 result = result.or(Option.unwrap(this.and(s), FALSE));
 627    }
 628  119 return result;
 629    }
 630   
 631  119 public Option<ConstraintScenario> and(ConstraintScenario that) {
 632  119 ConstraintScenario result = new ConstraintScenario();
 633  119 NormSubtyper sub = new NormSubtyper();
 634  119 NormJoiner join = new NormJoiner(sub);
 635  119 NormMeeter meet = new NormMeeter(sub);
 636  119 for (VariableType var : union(_lowerBounds.keySet(), that._lowerBounds.keySet())) {
 637  119 result._lowerBounds.put(var, join.value(IterUtil.make(lowerBound(var), that.lowerBound(var))));
 638    }
 639  119 for (VariableType var : union(_upperBounds.keySet(), that._upperBounds.keySet())) {
 640  93 result._upperBounds.put(var, meet.value(IterUtil.make(upperBound(var), that.upperBound(var))));
 641    }
 642  119 return result.isWellFormed() ? Option.some(result) : Option.<ConstraintScenario>none();
 643    }
 644   
 645  0 public Set<VariableType> boundVariables() {
 646  0 return union(_lowerBounds.keySet(), _upperBounds.keySet());
 647    }
 648   
 649  302 public Type upperBound(VariableType var) {
 650  302 Type result = _upperBounds.get(var);
 651  302 return (result == null) ? OBJECT : result;
 652    }
 653   
 654  377 public Type lowerBound(VariableType var) {
 655  377 Type result = _lowerBounds.get(var);
 656  377 return (result == null) ? NULL : result;
 657    }
 658   
 659    /** Test whether all variables have compatible bounds. */
 660  119 protected boolean isWellFormed() {
 661  119 NormSubtyper sub = new NormSubtyper();
 662  119 for (VariableType var : intersection(_lowerBounds.keySet(), _upperBounds.keySet())) {
 663  2 if (!sub.contains(lowerBound(var), upperBound(var))) { return false; }
 664    }
 665  117 return true;
 666    }
 667    }
 668   
 669    private class DisjunctiveConstraint extends ConstraintFormula {
 670    private final Iterable<ConstraintScenario> _scenarios;
 671  0 protected DisjunctiveConstraint(Iterable<ConstraintScenario> scenarios) { _scenarios = scenarios; }
 672   
 673  0 public boolean isSatisfiable() { return true; }
 674  0 public boolean isEmpty() { return false; }
 675  0 public Iterable<ConstraintScenario> scenarios() { return _scenarios; }
 676   
 677  0 public ConstraintFormula and(ConstraintFormula that) {
 678  0 Lambda<ConstraintFormula, Iterable<ConstraintScenario>> scenarios =
 679    new Lambda<ConstraintFormula, Iterable<ConstraintScenario>>() {
 680  0 public Iterable<ConstraintScenario> value(ConstraintFormula f) { return f.scenarios(); }
 681    };
 682  0 Lambda<Iterable<ConstraintScenario>, Option<ConstraintScenario>> conjunction =
 683    new Lambda<Iterable<ConstraintScenario>, Option<ConstraintScenario>>() {
 684  0 public Option<ConstraintScenario> value(Iterable<ConstraintScenario> scenarios) {
 685  0 Option<ConstraintScenario> result = Option.some(TRUE);
 686  0 for (ConstraintScenario s : scenarios) { // loop invariant: result is a some
 687  0 result = result.unwrap().and(s);
 688  0 if (result.isNone()) { break; }
 689    }
 690  0 return result;
 691    }
 692    };
 693  0 Iterable<Option<ConstraintScenario>> disjuncts =
 694    IterUtil.distribute(IterUtil.make(this, that), scenarios, conjunction);
 695  0 ConstraintFormula result = FALSE;
 696  0 for (Option<ConstraintScenario> s : disjuncts) {
 697  0 if (s.isSome()) { result = result.or(s.unwrap()); }
 698    }
 699  0 return result;
 700    }
 701   
 702    }
 703   
 704    // Constraint primitives: only the values/methods below should be used to create new base ConstraintFormulas.
 705   
 706    private ConstraintScenario TRUE = new ConstraintScenario();
 707   
 708    private ConstraintFormula FALSE = new ConstraintFormula() {
 709  2 public boolean isSatisfiable() { return false; }
 710  22 public boolean isEmpty() { return false; }
 711  13 public Iterable<ConstraintScenario> scenarios() { return IterUtil.empty(); }
 712  0 public ConstraintFormula and(ConstraintFormula that) { return this; }
 713  164 @Override public ConstraintFormula or(ConstraintFormula that) { return that; }
 714    };
 715   
 716  37 private ConstraintFormula lowerBound(VariableType var, Type lower) {
 717  37 NormSubtyper sub = new NormSubtyper();
 718  37 if (sub.contains(NULL, lower) && sub.contains(lower, OBJECT)) { return new ConstraintScenario(lower, var); }
 719  0 else { return FALSE; }
 720    }
 721   
 722  25 private ConstraintFormula upperBound(VariableType var, Type upper) {
 723  25 NormSubtyper sub = new NormSubtyper();
 724  25 if (sub.contains(NULL, upper) && sub.contains(upper, OBJECT)) { return new ConstraintScenario(var, upper); }
 725  0 else { return FALSE; }
 726    }
 727   
 728    /** True when one scenario implies another: any substitution satisfying the antecedent satisfies the consequent. */
 729    private Order<ConstraintScenario> SCENARIO_IMPLICATION = new Order<ConstraintScenario>() {
 730  0 public boolean contains(ConstraintScenario ant, ConstraintScenario cons) {
 731  0 NormSubtyper sub = new NormSubtyper();
 732  0 for (VariableType var : cons.boundVariables()) {
 733  0 if (!sub.contains(ant.upperBound(var), cons.upperBound(var))) { return false; }
 734  0 if (!sub.contains(cons.lowerBound(var), ant.lowerBound(var))) { return false; }
 735    }
 736  0 return true;
 737    }
 738    };
 739   
 740   
 741    /**
 742    * Top-level entry point for type inference. Produces the set of types corresponding to the given
 743    * type parameters, given that {@code args} were provided where {@code params} were expected
 744    * ({@code args} and {@code params} are assumed to have the same length), and {@code returned} will
 745    * be returned where {@code expected} is expected.
 746    *
 747    * @return A set of inferred type arguments for {@code tparams}, or {@code null} if the parameters
 748    * are over-constrained
 749    */
 750  25 protected Iterable<Type> inferTypeArguments(Iterable<? extends VariableType> tparams,
 751    Iterable<? extends Type> params, Type returned,
 752    Iterable<? extends Type> args, Option<Type> expected) {
 753    //debug.logValues("Beginning inferTypeArguments",
 754    // new String[]{ "tparams", "params", "returned", "args", "expected" },
 755    // wrap(tparams), wrap(params), wrap(returned), wrap(args), wrap(expected));
 756   
 757  25 Inferencer inf = new Inferencer(CollectUtil.makeSet(tparams));
 758   
 759    // perform inference for args and returned
 760  25 ConstraintFormula constraints = TRUE;
 761  25 NormSubtyper sub = new NormSubtyper();
 762  25 Normalizer norm = new Normalizer(sub);
 763  25 for (Pair<Type, Type> pair : IterUtil.zip(IterUtil.map(args, norm), IterUtil.map(params, norm))) {
 764  26 constraints = constraints.and(inf.subtypeNorm(pair.first(), pair.second()));
 765  0 if (!constraints.isSatisfiable()) { break; }
 766    }
 767  25 if (expected.isSome() && constraints.isSatisfiable()) {
 768  25 constraints = constraints.and(inf.supertypeNorm(norm.value(expected.unwrap()), norm.value(returned)));
 769    }
 770   
 771    // transitivity constraints: inferred bounds must be sub/super-types of declared bounds
 772    // (used to improve results where the variable has a self-referencing bound)
 773  25 ConstraintFormula transConstraints = FALSE;
 774  25 for (ConstraintScenario s : constraints.scenarios()) {
 775  23 ConstraintFormula cf = s;
 776  23 for (VariableType param : tparams) {
 777  23 cf = cf.and(inf.subtypeNorm(s.lowerBound(param), norm.value(param.symbol().upperBound())));
 778  0 if (!cf.isSatisfiable()) { break; }
 779  23 cf = cf.and(inf.supertypeNorm(s.upperBound(param), norm.value(param.symbol().lowerBound())));
 780  0 if (!cf.isSatisfiable()) { break; }
 781    }
 782  23 transConstraints = transConstraints.or(cf);
 783  0 if (transConstraints.isEmpty()) { break; }
 784    }
 785   
 786    //debug.logValue("constraints", constraints);
 787  2 if (!transConstraints.isSatisfiable()) { return null; }
 788   
 789  23 final Set<VariableType> inputTParams = new HashSet<VariableType>();
 790  23 for (VariableType tparam : tparams) {
 791  23 for (Type t : params) {
 792  14 if (containsVar(t, tparam)) { inputTParams.add(tparam); break; }
 793    }
 794    }
 795   
 796    // try to use packed bounds
 797  23 if (_packCaptureVars) {
 798  23 for (final ConstraintScenario s : transConstraints.scenarios()) {
 799  23 Iterable<Type> result = IterUtil.mapSnapshot(tparams, new Lambda<VariableType, Type>() {
 800  23 public Type value(VariableType param) {
 801  23 Type result = s.lowerBound(param);
 802    // use upper bound for input variables with a null lower bound
 803  23 if (result.equals(NULL) && inputTParams.contains(param)) {
 804  0 result = s.upperBound(param);
 805  0 while (result instanceof VariableType && ((VariableType) result).symbol().generated()) {
 806  0 result = ((VariableType) result).symbol().lowerBound();
 807    }
 808    }
 809    else {
 810  23 while (result instanceof VariableType && ((VariableType) result).symbol().generated()) {
 811  0 result = ((VariableType) result).symbol().upperBound();
 812    }
 813    }
 814  23 return result;
 815    }
 816    });
 817  23 if (inBounds(tparams, result)) { return result; }
 818    }
 819    }
 820   
 821    // packed bounds don't work, try to use bounds
 822  0 for (final ConstraintScenario s : transConstraints.scenarios()) {
 823  0 Iterable<Type> result = IterUtil.mapSnapshot(tparams, new Lambda<VariableType, Type>() {
 824  0 public Type value(VariableType param) {
 825  0 Type result = s.lowerBound(param);
 826    // use upper bound for input variables with a null lower bound
 827  0 if (result.equals(NULL) && inputTParams.contains(param)) { result = s.upperBound(param); }
 828  0 return result;
 829    }
 830    });
 831  0 if (inBounds(tparams, result)) { return result; }
 832    }
 833   
 834    // bounds don't work, try to use capture variables
 835  0 for (ConstraintScenario s : transConstraints.scenarios()) {
 836  0 List<Wildcard> constraintWs = new LinkedList<Wildcard>();
 837  0 for (VariableType param : tparams) {
 838  0 BoundedSymbol sym = new BoundedSymbol(new Object(), s.upperBound(param), s.lowerBound(param));
 839  0 constraintWs.add(new Wildcard(sym));
 840    }
 841  0 Iterable<Type> result = captureTypeArgs(constraintWs, tparams);
 842  0 if (IterUtil.and(result, new WellFormedChecker())) { return result; }
 843    }
 844   
 845    // give up
 846  0 return null;
 847    }
 848   
 849    private class Inferencer {
 850    private final Set<? extends VariableType> _vars;
 851    private final RecursionStack2<Type, Type> _subStack;
 852    private final RecursionStack2<Type, Type> _supStack;
 853    private final NormSubtyper _subtyper;
 854   
 855  25 public Inferencer(Set<? extends VariableType> vars) {
 856  25 _vars = vars;
 857  25 _subStack = new RecursionStack2<Type, Type>(Pair.<Type, Type>factory());
 858  25 _supStack = new RecursionStack2<Type, Type>(Pair.<Type, Type>factory());
 859  25 _subtyper = new NormSubtyper();
 860    }
 861   
 862  60 public ConstraintFormula subtypeNorm(final Type arg, final Type param) {
 863    //debug.logValues(new String[]{ "arg", "param" }, wrap(arg), wrap(param));
 864  23 if (!param.apply(_containsVar)) { return _subtyper.contains(arg, param) ? TRUE : FALSE; }
 865    else {
 866  37 return param.apply(new TypeAbstractVisitor<ConstraintFormula>() {
 867   
 868    class ArgVisitor extends TypeAbstractVisitor<ConstraintFormula> {
 869  0 @Override public ConstraintFormula defaultCase(Type arg) { return FALSE; }
 870  0 @Override public ConstraintFormula forNullType(NullType arg) { return TRUE; }
 871  0 @Override public ConstraintFormula forBottomType(BottomType arg) { return TRUE; }
 872   
 873  0 @Override public ConstraintFormula forVariableType(final VariableType arg) {
 874  0 Thunk<ConstraintFormula> recurOnBound = new Thunk<ConstraintFormula>() {
 875  0 public ConstraintFormula value() {
 876  0 return subtypeNorm(new Normalizer(_subtyper).value(arg.symbol().upperBound()), param);
 877    }
 878    };
 879  0 Thunk<ConstraintFormula> infiniteCase = new Thunk<ConstraintFormula>() {
 880  0 public ConstraintFormula value() { return subtypeNorm(OBJECT, param); }
 881    };
 882  0 return _subStack.apply(recurOnBound, infiniteCase, arg, param);
 883    }
 884   
 885  0 @Override public ConstraintFormula forIntersectionType(IntersectionType arg) {
 886  0 ConstraintFormula result = FALSE;
 887  0 for (Type supArg : arg.ofTypes()) {
 888  0 result = result.or(subtypeNorm(supArg, param));
 889  0 if (result.isEmpty()) { break; }
 890    }
 891  0 return result;
 892    }
 893   
 894  0 @Override public ConstraintFormula forUnionType(UnionType arg) {
 895  0 ConstraintFormula result = TRUE;
 896  0 for (Type subArg : arg.ofTypes()) {
 897  0 result = result.and(subtypeNorm(subArg, param));
 898  0 if (!result.isSatisfiable()) { break; }
 899    }
 900  0 return result;
 901    }
 902    }
 903   
 904  0 public ConstraintFormula defaultCase(Type param) { throw new IllegalArgumentException(); }
 905   
 906  0 @Override public ConstraintFormula forArrayType(final ArrayType param) {
 907  0 return arg.apply(new ArgVisitor() {
 908  0 @Override public ConstraintFormula forArrayType(ArrayType arg) {
 909  0 if (isPrimitive(arg.ofType())) { return equivalentNorm(arg.ofType(), param.ofType()); }
 910  0 else { return subtypeNorm(arg.ofType(), param.ofType()); }
 911    }
 912    });
 913    }
 914   
 915  0 @Override public ConstraintFormula forParameterizedClassType(final ParameterizedClassType param) {
 916  0 return arg.apply(new ArgVisitor() {
 917   
 918  0 @Override public ConstraintFormula forArrayType(ArrayType arg) {
 919  0 return subtypeNorm(CLONEABLE_AND_SERIALIZABLE, param);
 920    }
 921   
 922  0 @Override public ConstraintFormula forClassType(ClassType arg) {
 923  0 Type argSuper = immediateSupertype(arg);
 924  0 if (argSuper == null) { return FALSE; }
 925  0 else { return subtypeNorm(argSuper, param); }
 926    }
 927   
 928  0 @Override public ConstraintFormula forRawClassType(RawClassType arg) {
 929  0 if (sameClass(arg, param)) { return subtypeNorm(parameterize(arg), param); }
 930  0 else { return forClassType(arg); }
 931    }
 932   
 933  0 @Override public ConstraintFormula forParameterizedClassType(final ParameterizedClassType arg) {
 934  0 ConstraintFormula cf = FALSE;
 935  0 if (sameClass(param, arg)) {
 936  0 Thunk<ConstraintFormula> recurOnTargs = new Thunk<ConstraintFormula>() {
 937  0 public ConstraintFormula value() {
 938  0 ParameterizedClassType argCap = capture(arg);
 939  0 ConstraintFormula result = TRUE;
 940  0 for (Pair<Type, Type> pair : IterUtil.zip(argCap.typeArguments(), param.typeArguments())) {
 941  0 final Type argArg = pair.first();
 942  0 final Type paramArg = pair.second();
 943  0 result = result.and(paramArg.apply(new TypeAbstractVisitor<ConstraintFormula>() {
 944  0 public ConstraintFormula defaultCase(Type paramArg) {
 945  0 return equivalentNorm(argArg, paramArg);
 946    }
 947  0 @Override public ConstraintFormula forWildcard(Wildcard paramArg) {
 948  0 ConstraintFormula wildResult = supertypeNorm(argArg, paramArg.symbol().lowerBound());
 949  0 if (wildResult.isSatisfiable()) {
 950  0 wildResult = wildResult.and(subtypeNorm(argArg, paramArg.symbol().upperBound()));
 951    }
 952  0 return wildResult;
 953    }
 954    }));
 955  0 if (!result.isSatisfiable()) { break; }
 956    }
 957  0 return result;
 958    }
 959    };
 960  0 cf = _subStack.apply(recurOnTargs, FALSE, arg, param);
 961    }
 962  0 if (!cf.isEmpty()) { cf = cf.or(forClassType(arg)); }
 963  0 return cf;
 964    }
 965    });
 966    }
 967   
 968  37 @Override public ConstraintFormula forVariableType(final VariableType param) {
 969    // Note that this might be a capture variable with an inference-variable bound
 970  37 if (_vars.contains(param)) { return lowerBound(param, arg); }
 971    else {
 972  0 return arg.apply(new ArgVisitor() {
 973   
 974  0 @Override public ConstraintFormula defaultCase(final Type arg) {
 975  0 Thunk<ConstraintFormula> recurOnBound = new Thunk<ConstraintFormula>() {
 976  0 public ConstraintFormula value() {
 977  0 return subtypeNorm(arg, new Normalizer(_subtyper).value(param.symbol().lowerBound()));
 978    }
 979    };
 980  0 Thunk<ConstraintFormula> infiniteCase = new Thunk<ConstraintFormula>() {
 981  0 public ConstraintFormula value() { return subtypeNorm(arg, NULL); }
 982    };
 983  0 return _subStack.apply(recurOnBound, infiniteCase, arg, param);
 984    }
 985   
 986  0 @Override public ConstraintFormula forVariableType(VariableType arg) {
 987  0 ConstraintFormula result = super.forVariableType(arg);
 988  0 if (!result.isEmpty()) { result = result.or(defaultCase(arg)); }
 989  0 return result;
 990    }
 991   
 992  0 @Override public ConstraintFormula forIntersectionType(IntersectionType arg) {
 993  0 ConstraintFormula result = super.forIntersectionType(arg);
 994  0 if (!result.isEmpty()) { result = result.or(defaultCase(arg)); }
 995  0 return result;
 996    }
 997   
 998    });
 999    }
 1000    }
 1001   
 1002  0 @Override public ConstraintFormula forIntersectionType(final IntersectionType param) {
 1003  0 return arg.apply(new ArgVisitor() {
 1004  0 @Override public ConstraintFormula defaultCase(Type arg) {
 1005  0 ConstraintFormula result = TRUE;
 1006  0 for (Type supParam : param.ofTypes()) {
 1007  0 result = result.and(subtypeNorm(arg, supParam));
 1008  0 if (!result.isSatisfiable()) { break; }
 1009    }
 1010  0 return result;
 1011    }
 1012  0 @Override public ConstraintFormula forVariableType(VariableType arg) { return defaultCase(arg); }
 1013  0 @Override public ConstraintFormula forIntersectionType(IntersectionType arg) { return defaultCase(arg); }
 1014    });
 1015    }
 1016   
 1017  0 @Override public ConstraintFormula forUnionType(final UnionType param) {
 1018  0 return arg.apply(new ArgVisitor() {
 1019  0 @Override public ConstraintFormula defaultCase(Type arg) {
 1020  0 ConstraintFormula result = FALSE;
 1021  0 for (Type subParam : param.ofTypes()) {
 1022  0 result = result.or(subtypeNorm(arg, subParam));
 1023  0 if (result.isEmpty()) { break; }
 1024    }
 1025  0 return result;
 1026    }
 1027  0 @Override public ConstraintFormula forVariableType(VariableType arg) {
 1028  0 ConstraintFormula result = super.forVariableType(arg);
 1029  0 if (!result.isEmpty()) { result = result.or(defaultCase(arg)); }
 1030  0 return result;
 1031    }
 1032  0 @Override public ConstraintFormula forIntersectionType(IntersectionType arg) { return defaultCase(arg); }
 1033    });
 1034    }
 1035   
 1036    });
 1037    }
 1038    }
 1039   
 1040  92 public ConstraintFormula supertypeNorm(final Type arg, final Type param) {
 1041    //debug.logValues(new String[]{ "arg", "param" }, wrap(arg), wrap(param));
 1042  34 if (!param.apply(_containsVar)) { return new NormSubtyper().contains(param, arg) ? TRUE : FALSE; }
 1043    else {
 1044  58 return param.apply(new TypeAbstractVisitor<ConstraintFormula>() {
 1045   
 1046    class ArgVisitor extends TypeAbstractVisitor<ConstraintFormula> {
 1047  0 @Override public ConstraintFormula defaultCase(Type arg) { return FALSE; }
 1048  0 @Override public ConstraintFormula forTopType(TopType arg) { return TRUE; }
 1049   
 1050  0 @Override public ConstraintFormula forVariableType(final VariableType arg) {
 1051  0 Thunk<ConstraintFormula> recurOnBound = new Thunk<ConstraintFormula>() {
 1052  0 public ConstraintFormula value() {
 1053  0 return supertypeNorm(new Normalizer(_subtyper).value(arg.symbol().lowerBound()), param);
 1054    }
 1055    };
 1056  0 Thunk<ConstraintFormula> infiniteCase = new Thunk<ConstraintFormula>() {
 1057  0 public ConstraintFormula value() { return supertypeNorm(NULL, param); }
 1058    };
 1059  0 return _subStack.apply(recurOnBound, infiniteCase, arg, param);
 1060    }
 1061   
 1062  0 @Override public ConstraintFormula forIntersectionType(IntersectionType arg) {
 1063  0 ConstraintFormula result = TRUE;
 1064  0 for (Type supArg : arg.ofTypes()) {
 1065  0 result = result.and(supertypeNorm(supArg, param));
 1066  0 if (!result.isSatisfiable()) { break; }
 1067    }
 1068  0 return result;
 1069    }
 1070   
 1071  0 @Override public ConstraintFormula forUnionType(UnionType arg) {
 1072  0 ConstraintFormula result = FALSE;
 1073  0 for (Type subArg : arg.ofTypes()) {
 1074  0 result = result.or(supertypeNorm(subArg, param));
 1075  0 if (result.isEmpty()) { break; }
 1076    }
 1077  0 return result;
 1078    }
 1079    }
 1080   
 1081  0 public ConstraintFormula defaultCase(Type param) { throw new IllegalArgumentException(); }
 1082   
 1083  0 @Override public ConstraintFormula forArrayType(final ArrayType param) {
 1084  0 return arg.apply(new ArgVisitor() {
 1085  0 @Override public ConstraintFormula forArrayType(ArrayType arg) {
 1086  0 if (isPrimitive(arg.ofType())) { return equivalentNorm(arg.ofType(), param.ofType()); }
 1087  0 else { return supertypeNorm(arg.ofType(), param.ofType()); }
 1088    }
 1089  0 @Override public ConstraintFormula forClassType(ClassType arg) {
 1090  0 return supertypeNorm(arg, CLONEABLE_AND_SERIALIZABLE);
 1091    }
 1092    });
 1093    }
 1094   
 1095  33 @Override public ConstraintFormula forParameterizedClassType(final ParameterizedClassType param) {
 1096  33 return arg.apply(new ArgVisitor() {
 1097   
 1098  33 @Override public ConstraintFormula forClassType(ClassType arg) {
 1099  33 Type paramSuper = immediateSupertype(param);
 1100  0 if (paramSuper == null) { return FALSE; }
 1101  33 else { return supertypeNorm(arg, paramSuper); }
 1102    }
 1103   
 1104  0 @Override public ConstraintFormula forRawClassType(RawClassType arg) {
 1105  0 if (sameClass(arg, param)) { return TRUE; }
 1106  0 else { return forClassType(arg); }
 1107    }
 1108   
 1109  33 @Override public ConstraintFormula forParameterizedClassType(final ParameterizedClassType arg) {
 1110  33 ConstraintFormula cf = FALSE;
 1111  33 if (sameClass(param, arg)) {
 1112  11 Thunk<ConstraintFormula> recurOnTargs = new Thunk<ConstraintFormula>() {
 1113  11 public ConstraintFormula value() {
 1114  11 ParameterizedClassType paramCap = capture(param);
 1115  11 ConstraintFormula result = TRUE;
 1116  11 for (Pair<Type, Type> pair : IterUtil.zip(arg.typeArguments(), paramCap.typeArguments())) {
 1117  11 final Type argArg = pair.first();
 1118  11 final Type paramArg = pair.second();
 1119  11 result = result.and(argArg.apply(new TypeAbstractVisitor<ConstraintFormula>() {
 1120  11 public ConstraintFormula defaultCase(Type argArg) {
 1121  11 return equivalentNorm(argArg, paramArg);
 1122    }
 1123  0 @Override public ConstraintFormula forWildcard(Wildcard argArg) {
 1124  0 ConstraintFormula wildResult = subtypeNorm(argArg.symbol().lowerBound(), paramArg);
 1125  0 if (wildResult.isSatisfiable()) {
 1126  0 wildResult = wildResult.and(supertypeNorm(argArg.symbol().upperBound(), paramArg));
 1127    }
 1128  0 return wildResult;
 1129    }
 1130    }));
 1131  0 if (!result.isSatisfiable()) { break; }
 1132    }
 1133  11 return result;
 1134    }
 1135    };
 1136  11 cf = _supStack.apply(recurOnTargs, FALSE, arg, param);
 1137    }
 1138  33 if (!cf.isEmpty()) { cf = cf.or(forClassType(arg)); }
 1139  33 return cf;
 1140    }
 1141   
 1142    });
 1143    }
 1144   
 1145  25 @Override public ConstraintFormula forVariableType(final VariableType param) {
 1146    // Note that this might be a capture variable with an inference-variable bound
 1147  25 if (_vars.contains(param)) { return upperBound(param, arg); }
 1148    else {
 1149  0 return arg.apply(new ArgVisitor() {
 1150   
 1151  0 @Override public ConstraintFormula defaultCase(final Type arg) {
 1152  0 Thunk<ConstraintFormula> recurOnBound = new Thunk<ConstraintFormula>() {
 1153  0 public ConstraintFormula value() {
 1154  0 return supertypeNorm(arg, new Normalizer(_subtyper).value(param.symbol().upperBound()));
 1155    }
 1156    };
 1157  0 Thunk<ConstraintFormula> infiniteCase = new Thunk<ConstraintFormula>() {
 1158  0 public ConstraintFormula value() { return supertypeNorm(arg, OBJECT); }
 1159    };
 1160  0 return _supStack.apply(recurOnBound, infiniteCase, arg, param);
 1161    }
 1162   
 1163  0 @Override public ConstraintFormula forVariableType(VariableType arg) {
 1164  0 ConstraintFormula result = defaultCase(arg);
 1165  0 if (!result.isEmpty()) { result = result.or(super.forVariableType(arg)); }
 1166  0 return result;
 1167    }
 1168   
 1169  0 @Override public ConstraintFormula forUnionType(UnionType arg) {
 1170  0 ConstraintFormula result = defaultCase(arg);
 1171  0 if (!result.isEmpty()) { result = result.or(super.forUnionType(arg)); }
 1172  0 return result;
 1173    }
 1174   
 1175    });
 1176    }
 1177    }
 1178   
 1179  0 @Override public ConstraintFormula forIntersectionType(final IntersectionType param) {
 1180  0 return arg.apply(new ArgVisitor() {
 1181  0 @Override public ConstraintFormula defaultCase(Type arg) {
 1182  0 ConstraintFormula result = FALSE;
 1183  0 for (Type supParam : param.ofTypes()) {
 1184  0 result = result.or(supertypeNorm(arg, supParam));
 1185  0 if (result.isEmpty()) { break; }
 1186    }
 1187  0 return result;
 1188    }
 1189  0 @Override public ConstraintFormula forVariableType(VariableType arg) {
 1190  0 ConstraintFormula result = defaultCase(arg);
 1191  0 if (!result.isEmpty()) { result = result.or(super.forVariableType(arg)); }
 1192  0 return result;
 1193    }
 1194  0 @Override public ConstraintFormula forUnionType(UnionType arg) { return defaultCase(arg); }
 1195    });
 1196    }
 1197   
 1198  0 @Override public ConstraintFormula forUnionType(final UnionType param) {
 1199  0 return arg.apply(new ArgVisitor() {
 1200  0 @Override public ConstraintFormula defaultCase(Type arg) {
 1201  0 ConstraintFormula result = TRUE;
 1202  0 for (Type subParam : param.ofTypes()) {
 1203  0 result = result.and(supertypeNorm(arg, subParam));
 1204  0 if (!result.isSatisfiable()) { break; }
 1205    }
 1206  0 return result;
 1207    }
 1208  0 @Override public ConstraintFormula forVariableType(VariableType arg) { return defaultCase(arg); }
 1209  0 @Override public ConstraintFormula forIntersectionType(IntersectionType arg) { return defaultCase(arg); }
 1210  0 @Override public ConstraintFormula forUnionType(UnionType arg) { return defaultCase(arg); }
 1211    });
 1212    }
 1213   
 1214    });
 1215    }
 1216    }
 1217   
 1218  11 public ConstraintFormula equivalentNorm(final Type arg, final Type param) {
 1219  11 ConstraintFormula result = subtypeNorm(arg, param);
 1220  11 if (result.isSatisfiable()) { result = result.and(supertypeNorm(arg, param)); }
 1221  11 return result;
 1222    }
 1223   
 1224    private final TypeVisitorLambda<Boolean> _containsVar = new TypeAbstractVisitor<Boolean>() {
 1225    private final RecursionStack<Type> _stack = new RecursionStack<Type>(Wrapper.<Type>factory());
 1226  57 public Boolean defaultCase(Type t) { return false; }
 1227  0 @Override public Boolean forArrayType(ArrayType t) { return t.ofType().apply(this); }
 1228  33 @Override public Boolean forParameterizedClassType(ParameterizedClassType t) {
 1229  33 return checkList(t.typeArguments());
 1230    }
 1231  0 @Override public Boolean forBoundType(BoundType t) { return checkList(t.ofTypes()); }
 1232  95 @Override public Boolean forVariableType(VariableType t) {
 1233  95 return _vars.contains(t) || checkBoundedSymbol(t, t.symbol());
 1234    }
 1235  0 @Override public Boolean forWildcard(Wildcard w) { return checkBoundedSymbol(w, w.symbol()); }
 1236   
 1237  33 private Boolean checkList(Iterable<? extends Type> types) {
 1238  33 for (Type t : types) {
 1239  33 if (t.apply(this)) { return true; }
 1240    }
 1241  0 return false;
 1242    }
 1243   
 1244  0 private Boolean checkBoundedSymbol(Type t, final BoundedSymbol s) {
 1245  0 final TypeVisitor<Boolean> visitor = this; // handles this shadowing
 1246    // wildcards here aren't recursive, so don't need to be handled with a stack,
 1247    // but it doesn't hurt to cover the more general case
 1248  0 Thunk<Boolean> handleBounds = new Thunk<Boolean>() {
 1249  0 public Boolean value() {
 1250  0 return s.lowerBound().apply(visitor) || s.upperBound().apply(visitor);
 1251    }
 1252    };
 1253  0 return _stack.apply(handleBounds, false, t);
 1254    }
 1255   
 1256    };
 1257    }
 1258   
 1259    }
 
CloverReport generated by Clover Code Coverage v1.3.14
Sat May 18 2013 03:01:28 CDT.		   Open Source License registered to the DrJava Project. This license of Clover is provided to support the development of DrJava only.