1.1 --- a/src/share/classes/com/sun/tools/javac/comp/Infer.java Tue Apr 10 23:19:26 2012 -0700
1.2 +++ b/src/share/classes/com/sun/tools/javac/comp/Infer.java Wed Apr 11 10:50:11 2012 +0100
1.3 @@ -32,7 +32,6 @@
1.4 import com.sun.tools.javac.util.List;
1.5 import com.sun.tools.javac.code.*;
1.6 import com.sun.tools.javac.code.Type.*;
1.7 -import com.sun.tools.javac.code.Type.ForAll.ConstraintKind;
1.8 import com.sun.tools.javac.code.Symbol.*;
1.9 import com.sun.tools.javac.comp.Resolve.InapplicableMethodException;
1.10 import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode;
1.11 @@ -122,84 +121,21 @@
1.12
1.13 /** A mapping that turns type variables into undetermined type variables.
1.14 */
1.15 - Mapping fromTypeVarFun = new Mapping("fromTypeVarFun") {
1.16 - public Type apply(Type t) {
1.17 - if (t.tag == TYPEVAR) return new UndetVar(t);
1.18 - else return t.map(this);
1.19 - }
1.20 - };
1.21 -
1.22 - /** A mapping that returns its type argument with every UndetVar replaced
1.23 - * by its `inst' field. Throws a NoInstanceException
1.24 - * if this not possible because an `inst' field is null.
1.25 - * Note: mutually referring undertvars will be left uninstantiated
1.26 - * (that is, they will be replaced by the underlying type-variable).
1.27 - */
1.28 -
1.29 - Mapping getInstFun = new Mapping("getInstFun") {
1.30 - public Type apply(Type t) {
1.31 - switch (t.tag) {
1.32 - case UNKNOWN:
1.33 - throw ambiguousNoInstanceException
1.34 - .setMessage("undetermined.type");
1.35 - case UNDETVAR:
1.36 - UndetVar that = (UndetVar) t;
1.37 - if (that.inst == null)
1.38 - throw ambiguousNoInstanceException
1.39 - .setMessage("type.variable.has.undetermined.type",
1.40 - that.qtype);
1.41 - return isConstraintCyclic(that) ?
1.42 - that.qtype :
1.43 - apply(that.inst);
1.44 - default:
1.45 - return t.map(this);
1.46 + List<Type> makeUndetvars(List<Type> tvars) {
1.47 + List<Type> undetvars = Type.map(tvars, fromTypeVarFun);
1.48 + for (Type t : undetvars) {
1.49 + UndetVar uv = (UndetVar)t;
1.50 + uv.hibounds = types.getBounds((TypeVar)uv.qtype);
1.51 + }
1.52 + return undetvars;
1.53 + }
1.54 + //where
1.55 + Mapping fromTypeVarFun = new Mapping("fromTypeVarFun") {
1.56 + public Type apply(Type t) {
1.57 + if (t.tag == TYPEVAR) return new UndetVar(t);
1.58 + else return t.map(this);
1.59 }
1.60 - }
1.61 -
1.62 - private boolean isConstraintCyclic(UndetVar uv) {
1.63 - Types.UnaryVisitor<Boolean> constraintScanner =
1.64 - new Types.UnaryVisitor<Boolean>() {
1.65 -
1.66 - List<Type> seen = List.nil();
1.67 -
1.68 - Boolean visit(List<Type> ts) {
1.69 - for (Type t : ts) {
1.70 - if (visit(t)) return true;
1.71 - }
1.72 - return false;
1.73 - }
1.74 -
1.75 - public Boolean visitType(Type t, Void ignored) {
1.76 - return false;
1.77 - }
1.78 -
1.79 - @Override
1.80 - public Boolean visitClassType(ClassType t, Void ignored) {
1.81 - if (t.isCompound()) {
1.82 - return visit(types.supertype(t)) ||
1.83 - visit(types.interfaces(t));
1.84 - } else {
1.85 - return visit(t.getTypeArguments());
1.86 - }
1.87 - }
1.88 - @Override
1.89 - public Boolean visitWildcardType(WildcardType t, Void ignored) {
1.90 - return visit(t.type);
1.91 - }
1.92 -
1.93 - @Override
1.94 - public Boolean visitUndetVar(UndetVar t, Void ignored) {
1.95 - if (seen.contains(t)) {
1.96 - return true;
1.97 - } else {
1.98 - seen = seen.prepend(t);
1.99 - return visit(t.inst);
1.100 - }
1.101 - }
1.102 - };
1.103 - return constraintScanner.visit(uv);
1.104 - }
1.105 - };
1.106 + };
1.107
1.108 /***************************************************************************
1.109 * Mini/Maximization of UndetVars
1.110 @@ -210,13 +146,15 @@
1.111 */
1.112 void maximizeInst(UndetVar that, Warner warn) throws NoInstanceException {
1.113 List<Type> hibounds = Type.filter(that.hibounds, errorFilter);
1.114 - if (that.inst == null) {
1.115 + if (that.eq.isEmpty()) {
1.116 if (hibounds.isEmpty())
1.117 that.inst = syms.objectType;
1.118 else if (hibounds.tail.isEmpty())
1.119 that.inst = hibounds.head;
1.120 else
1.121 that.inst = types.glb(hibounds);
1.122 + } else {
1.123 + that.inst = that.eq.head;
1.124 }
1.125 if (that.inst == null ||
1.126 that.inst.isErroneous())
1.127 @@ -224,27 +162,6 @@
1.128 .setMessage("no.unique.maximal.instance.exists",
1.129 that.qtype, hibounds);
1.130 }
1.131 - //where
1.132 - private boolean isSubClass(Type t, final List<Type> ts) {
1.133 - t = t.baseType();
1.134 - if (t.tag == TYPEVAR) {
1.135 - List<Type> bounds = types.getBounds((TypeVar)t);
1.136 - for (Type s : ts) {
1.137 - if (!types.isSameType(t, s.baseType())) {
1.138 - for (Type bound : bounds) {
1.139 - if (!isSubClass(bound, List.of(s.baseType())))
1.140 - return false;
1.141 - }
1.142 - }
1.143 - }
1.144 - } else {
1.145 - for (Type s : ts) {
1.146 - if (!t.tsym.isSubClass(s.baseType().tsym, types))
1.147 - return false;
1.148 - }
1.149 - }
1.150 - return true;
1.151 - }
1.152
1.153 private Filter<Type> errorFilter = new Filter<Type>() {
1.154 @Override
1.155 @@ -258,7 +175,7 @@
1.156 */
1.157 void minimizeInst(UndetVar that, Warner warn) throws NoInstanceException {
1.158 List<Type> lobounds = Type.filter(that.lobounds, errorFilter);
1.159 - if (that.inst == null) {
1.160 + if (that.eq.isEmpty()) {
1.161 if (lobounds.isEmpty())
1.162 that.inst = syms.botType;
1.163 else if (lobounds.tail.isEmpty())
1.164 @@ -270,21 +187,8 @@
1.165 throw ambiguousNoInstanceException
1.166 .setMessage("no.unique.minimal.instance.exists",
1.167 that.qtype, lobounds);
1.168 - // VGJ: sort of inlined maximizeInst() below. Adding
1.169 - // bounds can cause lobounds that are above hibounds.
1.170 - List<Type> hibounds = Type.filter(that.hibounds, errorFilter);
1.171 - Type hb = null;
1.172 - if (hibounds.isEmpty())
1.173 - hb = syms.objectType;
1.174 - else if (hibounds.tail.isEmpty())
1.175 - hb = hibounds.head;
1.176 - else
1.177 - hb = types.glb(hibounds);
1.178 - if (hb == null ||
1.179 - hb.isErroneous())
1.180 - throw ambiguousNoInstanceException
1.181 - .setMessage("incompatible.upper.bounds",
1.182 - that.qtype, hibounds);
1.183 + } else {
1.184 + that.inst = that.eq.head;
1.185 }
1.186 }
1.187
1.188 @@ -313,21 +217,7 @@
1.189 public Type instantiateExpr(ForAll that,
1.190 Type to,
1.191 Warner warn) throws InferenceException {
1.192 - List<Type> undetvars = Type.map(that.tvars, fromTypeVarFun);
1.193 - for (List<Type> l = undetvars; l.nonEmpty(); l = l.tail) {
1.194 - UndetVar uv = (UndetVar) l.head;
1.195 - TypeVar tv = (TypeVar)uv.qtype;
1.196 - ListBuffer<Type> hibounds = new ListBuffer<Type>();
1.197 - for (Type t : that.getConstraints(tv, ConstraintKind.EXTENDS)) {
1.198 - hibounds.append(types.subst(t, that.tvars, undetvars));
1.199 - }
1.200 -
1.201 - List<Type> inst = that.getConstraints(tv, ConstraintKind.EQUAL);
1.202 - if (inst.nonEmpty() && inst.head.tag != BOT) {
1.203 - uv.inst = inst.head;
1.204 - }
1.205 - uv.hibounds = hibounds.toList();
1.206 - }
1.207 + List<Type> undetvars = that.undetvars();
1.208 Type qtype1 = types.subst(that.qtype, that.tvars, undetvars);
1.209 if (!types.isSubtype(qtype1,
1.210 qtype1.tag == UNDETVAR ? types.boxedTypeOrType(to) : to)) {
1.211 @@ -335,41 +225,72 @@
1.212 .setMessage("infer.no.conforming.instance.exists",
1.213 that.tvars, that.qtype, to);
1.214 }
1.215 - for (List<Type> l = undetvars; l.nonEmpty(); l = l.tail)
1.216 - maximizeInst((UndetVar) l.head, warn);
1.217 - // System.out.println(" = " + qtype1.map(getInstFun));//DEBUG
1.218
1.219 - // check bounds
1.220 - List<Type> targs = Type.map(undetvars, getInstFun);
1.221 - if (Type.containsAny(targs, that.tvars)) {
1.222 - //replace uninferred type-vars
1.223 - targs = types.subst(targs,
1.224 + List<Type> insttypes;
1.225 + while (true) {
1.226 + boolean stuck = true;
1.227 + insttypes = List.nil();
1.228 + for (Type t : undetvars) {
1.229 + UndetVar uv = (UndetVar)t;
1.230 + if (uv.inst == null && (uv.eq.nonEmpty() || !Type.containsAny(uv.hibounds, that.tvars))) {
1.231 + maximizeInst((UndetVar)t, warn);
1.232 + stuck = false;
1.233 + }
1.234 + insttypes = insttypes.append(uv.inst == null ? uv.qtype : uv.inst);
1.235 + }
1.236 + if (!Type.containsAny(insttypes, that.tvars)) {
1.237 + //all variables have been instantiated - exit
1.238 + break;
1.239 + } else if (stuck) {
1.240 + //some variables could not be instantiated because of cycles in
1.241 + //upper bounds - provide a (possibly recursive) default instantiation
1.242 + insttypes = types.subst(insttypes,
1.243 that.tvars,
1.244 instantiateAsUninferredVars(undetvars, that.tvars));
1.245 + break;
1.246 + } else {
1.247 + //some variables have been instantiated - replace newly instantiated
1.248 + //variables in remaining upper bounds and continue
1.249 + for (Type t : undetvars) {
1.250 + UndetVar uv = (UndetVar)t;
1.251 + uv.hibounds = types.subst(uv.hibounds, that.tvars, insttypes);
1.252 + }
1.253 + }
1.254 }
1.255 - return that.inst(targs, types);
1.256 + return that.inst(insttypes, types);
1.257 }
1.258 - //where
1.259 +
1.260 + /**
1.261 + * Infer cyclic inference variables as described in 15.12.2.8.
1.262 + */
1.263 private List<Type> instantiateAsUninferredVars(List<Type> undetvars, List<Type> tvars) {
1.264 Assert.check(undetvars.length() == tvars.length());
1.265 - ListBuffer<Type> new_targs = ListBuffer.lb();
1.266 - //step 1 - create synthetic captured vars
1.267 + ListBuffer<Type> insttypes = ListBuffer.lb();
1.268 + ListBuffer<Type> todo = ListBuffer.lb();
1.269 + //step 1 - create fresh tvars
1.270 for (Type t : undetvars) {
1.271 UndetVar uv = (UndetVar)t;
1.272 - Type newArg = new CapturedType(t.tsym.name, t.tsym, uv.inst, syms.botType, null);
1.273 - new_targs = new_targs.append(newArg);
1.274 + if (uv.inst == null) {
1.275 + TypeSymbol fresh_tvar = new TypeSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner);
1.276 + fresh_tvar.type = new TypeVar(fresh_tvar, types.makeCompoundType(uv.hibounds), null);
1.277 + todo.append(uv);
1.278 + uv.inst = fresh_tvar.type;
1.279 + }
1.280 + insttypes.append(uv.inst);
1.281 }
1.282 - //step 2 - replace synthetic vars in their bounds
1.283 + //step 2 - replace fresh tvars in their bounds
1.284 List<Type> formals = tvars;
1.285 - for (Type t : new_targs.toList()) {
1.286 - CapturedType ct = (CapturedType)t;
1.287 - ct.bound = types.subst(ct.bound, tvars, new_targs.toList());
1.288 - WildcardType wt = new WildcardType(syms.objectType, BoundKind.UNBOUND, syms.boundClass);
1.289 - wt.bound = (TypeVar)formals.head;
1.290 - ct.wildcard = wt;
1.291 + for (Type t : todo) {
1.292 + UndetVar uv = (UndetVar)t;
1.293 + TypeVar ct = (TypeVar)uv.inst;
1.294 + ct.bound = types.glb(types.subst(types.getBounds(ct), tvars, insttypes.toList()));
1.295 + if (ct.bound.isErroneous()) {
1.296 + //report inference error if glb fails
1.297 + reportBoundError(uv, BoundErrorKind.BAD_UPPER);
1.298 + }
1.299 formals = formals.tail;
1.300 }
1.301 - return new_targs.toList();
1.302 + return insttypes.toList();
1.303 }
1.304
1.305 /** Instantiate method type `mt' by finding instantiations of
1.306 @@ -384,7 +305,7 @@
1.307 final boolean useVarargs,
1.308 final Warner warn) throws InferenceException {
1.309 //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
1.310 - List<Type> undetvars = Type.map(tvars, fromTypeVarFun);
1.311 + final List<Type> undetvars = makeUndetvars(tvars);
1.312
1.313 final List<Type> capturedArgs =
1.314 rs.checkRawArgumentsAcceptable(env, undetvars, argtypes, mt.getParameterTypes(),
1.315 @@ -419,7 +340,7 @@
1.316 undettypes.append(uv.inst);
1.317 }
1.318 }
1.319 - checkWithinBounds(tvars, undettypes.toList(), warn);
1.320 + checkWithinBounds(tvars, undetvars, insttypes.toList(), warn);
1.321
1.322 mt = (MethodType)types.subst(mt, tvars, insttypes.toList());
1.323
1.324 @@ -430,18 +351,8 @@
1.325 final List<Type> all_tvars = tvars; //this is the wrong tvars
1.326 return new UninferredMethodType(env.tree.pos(), msym, mt, restvars.toList()) {
1.327 @Override
1.328 - List<Type> getConstraints(TypeVar tv, ConstraintKind ck) {
1.329 - for (Type t : restundet.toList()) {
1.330 - UndetVar uv = (UndetVar)t;
1.331 - if (uv.qtype == tv) {
1.332 - switch (ck) {
1.333 - case EXTENDS: return uv.hibounds.appendList(types.subst(types.getBounds(tv), all_tvars, inferredTypes));
1.334 - case SUPER: return uv.lobounds;
1.335 - case EQUAL: return uv.inst != null ? List.of(uv.inst) : List.<Type>nil();
1.336 - }
1.337 - }
1.338 - }
1.339 - return List.nil();
1.340 + List<Type> undetvars() {
1.341 + return restundet.toList();
1.342 }
1.343 @Override
1.344 void instantiateReturnType(Type restype, List<Type> inferred, Types types) throws NoInstanceException {
1.345 @@ -453,7 +364,7 @@
1.346 warn.clear();
1.347 checkArgumentsAcceptable(env, capturedArgs, owntype.getParameterTypes(), allowBoxing, useVarargs, warn);
1.348 // check that inferred bounds conform to their bounds
1.349 - checkWithinBounds(all_tvars,
1.350 + checkWithinBounds(all_tvars, undetvars,
1.351 types.subst(inferredTypes, tvars, inferred), warn);
1.352 qtype = chk.checkMethod(owntype, msym, env, TreeInfo.args(env.tree), capturedArgs, useVarargs, warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED));
1.353 }
1.354 @@ -525,7 +436,7 @@
1.355
1.356 abstract void instantiateReturnType(Type restype, List<Type> inferred, Types types);
1.357
1.358 - abstract List<Type> getConstraints(TypeVar tv, ConstraintKind ck);
1.359 + abstract List<Type> undetvars();
1.360
1.361 class UninferredReturnType extends ForAll {
1.362 public UninferredReturnType(List<Type> tvars, Type restype) {
1.363 @@ -541,8 +452,8 @@
1.364 return UninferredMethodType.this.qtype.getReturnType();
1.365 }
1.366 @Override
1.367 - public List<Type> getConstraints(TypeVar tv, ConstraintKind ck) {
1.368 - return UninferredMethodType.this.getConstraints(tv, ck);
1.369 + public List<Type> undetvars() {
1.370 + return UninferredMethodType.this.undetvars();
1.371 }
1.372 }
1.373 }
1.374 @@ -559,43 +470,94 @@
1.375 }
1.376 }
1.377
1.378 - /** Try to instantiate argument type `that' to given type `to'.
1.379 - * If this fails, try to insantiate `that' to `to' where
1.380 - * every occurrence of a type variable in `tvars' is replaced
1.381 - * by an unknown type.
1.382 + /** check that type parameters are within their bounds.
1.383 */
1.384 - private Type instantiateArg(ForAll that,
1.385 - Type to,
1.386 - List<Type> tvars,
1.387 - Warner warn) throws InferenceException {
1.388 - List<Type> targs;
1.389 - try {
1.390 - return instantiateExpr(that, to, warn);
1.391 - } catch (NoInstanceException ex) {
1.392 - Type to1 = to;
1.393 - for (List<Type> l = tvars; l.nonEmpty(); l = l.tail)
1.394 - to1 = types.subst(to1, List.of(l.head), List.of(syms.unknownType));
1.395 - return instantiateExpr(that, to1, warn);
1.396 + void checkWithinBounds(List<Type> tvars,
1.397 + List<Type> undetvars,
1.398 + List<Type> arguments,
1.399 + Warner warn)
1.400 + throws InvalidInstanceException {
1.401 + List<Type> args = arguments;
1.402 + for (Type t : undetvars) {
1.403 + UndetVar uv = (UndetVar)t;
1.404 + uv.hibounds = types.subst(uv.hibounds, tvars, arguments);
1.405 + uv.lobounds = types.subst(uv.lobounds, tvars, arguments);
1.406 + uv.eq = types.subst(uv.eq, tvars, arguments);
1.407 + checkCompatibleUpperBounds(uv, tvars);
1.408 + if (args.head.tag != TYPEVAR || !args.head.containsAny(tvars)) {
1.409 + Type inst = args.head;
1.410 + for (Type u : uv.hibounds) {
1.411 + if (!types.isSubtypeUnchecked(inst, types.subst(u, tvars, undetvars), warn)) {
1.412 + reportBoundError(uv, BoundErrorKind.UPPER);
1.413 + }
1.414 + }
1.415 + for (Type l : uv.lobounds) {
1.416 + if (!types.isSubtypeUnchecked(types.subst(l, tvars, undetvars), inst, warn)) {
1.417 + reportBoundError(uv, BoundErrorKind.LOWER);
1.418 + }
1.419 + }
1.420 + for (Type e : uv.eq) {
1.421 + if (!types.isSameType(inst, types.subst(e, tvars, undetvars))) {
1.422 + reportBoundError(uv, BoundErrorKind.EQ);
1.423 + }
1.424 + }
1.425 + }
1.426 + args = args.tail;
1.427 }
1.428 }
1.429
1.430 - /** check that type parameters are within their bounds.
1.431 - */
1.432 - void checkWithinBounds(List<Type> tvars,
1.433 - List<Type> arguments,
1.434 - Warner warn)
1.435 - throws InvalidInstanceException {
1.436 - for (List<Type> tvs = tvars, args = arguments;
1.437 - tvs.nonEmpty();
1.438 - tvs = tvs.tail, args = args.tail) {
1.439 - if (args.head instanceof UndetVar ||
1.440 - tvars.head.getUpperBound().isErroneous()) continue;
1.441 - List<Type> bounds = types.subst(types.getBounds((TypeVar)tvs.head), tvars, arguments);
1.442 - if (!types.isSubtypeUnchecked(args.head, bounds, warn))
1.443 - throw invalidInstanceException
1.444 - .setMessage("inferred.do.not.conform.to.bounds",
1.445 - args.head, bounds);
1.446 + void checkCompatibleUpperBounds(UndetVar uv, List<Type> tvars) {
1.447 + // VGJ: sort of inlined maximizeInst() below. Adding
1.448 + // bounds can cause lobounds that are above hibounds.
1.449 + ListBuffer<Type> hiboundsNoVars = ListBuffer.lb();
1.450 + for (Type t : Type.filter(uv.hibounds, errorFilter)) {
1.451 + if (!t.containsAny(tvars)) {
1.452 + hiboundsNoVars.append(t);
1.453 + }
1.454 }
1.455 + List<Type> hibounds = hiboundsNoVars.toList();
1.456 + Type hb = null;
1.457 + if (hibounds.isEmpty())
1.458 + hb = syms.objectType;
1.459 + else if (hibounds.tail.isEmpty())
1.460 + hb = hibounds.head;
1.461 + else
1.462 + hb = types.glb(hibounds);
1.463 + if (hb == null || hb.isErroneous())
1.464 + reportBoundError(uv, BoundErrorKind.BAD_UPPER);
1.465 + }
1.466 +
1.467 + enum BoundErrorKind {
1.468 + BAD_UPPER() {
1.469 + @Override
1.470 + InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
1.471 + return ex.setMessage("incompatible.upper.bounds", uv.qtype, uv.hibounds);
1.472 + }
1.473 + },
1.474 + UPPER() {
1.475 + @Override
1.476 + InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
1.477 + return ex.setMessage("inferred.do.not.conform.to.upper.bounds", uv.inst, uv.hibounds);
1.478 + }
1.479 + },
1.480 + LOWER() {
1.481 + @Override
1.482 + InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
1.483 + return ex.setMessage("inferred.do.not.conform.to.lower.bounds", uv.inst, uv.lobounds);
1.484 + }
1.485 + },
1.486 + EQ() {
1.487 + @Override
1.488 + InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
1.489 + return ex.setMessage("inferred.do.not.conform.to.eq.bounds", uv.inst, uv.eq);
1.490 + }
1.491 + };
1.492 +
1.493 + abstract InapplicableMethodException setMessage(InferenceException ex, UndetVar uv);
1.494 + }
1.495 + //where
1.496 + void reportBoundError(UndetVar uv, BoundErrorKind bk) {
1.497 + throw bk.setMessage(uv.inst == null ? ambiguousNoInstanceException : invalidInstanceException, uv);
1.498 }
1.499
1.500 /**
