I'm confused. When can this happen? If bound0.isHigherKinded shouldn't it be a PolyType and not a TypeRef? Also checking the size of type parameters might not be enough. Basically we care only if the bound is F[x, y, z[_]] <: G[x, y, z], but it could be F[x, y, z[_]] <: G[z, x, y] or F[x, y, z[_]] <: G[x, y, List].

I can't remember the scenario now. It's possible that it's something that came up with incorrect code.

When would it be necessary to flip the bounds?

Flip the bounds depending on whether the param is co/inv vs. contra variant.

up depends on the variance of tparam and the variance of tparam2 shouldn't matter I think.

I'd like to be convinced of that :-)

Check for NoType?

addBound checks for NoType

Just added a check for NoType returned from toInst.

I'm not convinced of this part. Subtyping only moves to arguments once the type constructors are equal, not just in some subtype relation. You'd have to do something like relating F's type args with C.baseType(F).typeArgs, but we don't support doing that stuff on type vars. Can you show with an example that this code path is crucial, and how it works?

I feel like we're talking about the same thing over and over. This was my concern to begin with. For example:

• Nil.type <:< List[x] but they don't have the same type constructor
• Map[k, v] <:< Traversable[(k, v)] but they don't have the same type arguments

I tried to be on the safer side by doing a kind conformance check, but as you noted it's not a 100% guarantee and it's costly.

Propagating the type arguments is necessary for t7289_status_quo. Otherwise implicitly[Ext[_ <: List[List[Int]]]] and implicitly[ExtCov[List[List[Int]]]] are ambiguous.

In any case we have type variables on both sides so in the worst case we will infer something that doesn't respect the bounds and it will fail to compile when we check them. I couldn't find an example that compiled before and would fail with the more aggressive propagation, but if you can find one, that would be awesome.

Thanks for bearing with me, this is tricky stuff and it's core to the type checker, so we need to take our time to understand the change and make sure it's right.

I don't see how this step propagates the constraints to the right type args, since addBound will still be constraining the type var that was originally bounded by the applied type constructor, and now we are recursing on its args without changing the type var that addBound works on.

Even if we did propagate those args to the right type var somehow, I'm not sure it would help. When evaluating the progress made in the test, it's important to keep in mind the actual types inferred using -Xprint:typer. In the covariant case (and equivalents) we just end up with Nothing. In the example, this seems to be an accident, because the type args in bounds of CC end up constraining CC itself. (Turn the debugLog in addBound into a println to see the trace.)

@adriaanm you're right, we are propagating constraints to the type var currently under consideration. We're getting those constraints from bounds on other type variables that it appears in.

For instance, consider def foo[A <: List[B], B](x: A): Option[B] = None where A is solved as List[Int] (see, test/files/pos/bounds-propagation.scala). Now when we come to solve for B we inspect the bounds that B appears in, here the bound on A. From that we can infer an Int bound on B and so solve B as Int. With the status quo we don't consider B's occurrence in other bounds so the best we get is Nothing.

Apropos the use of baseType in this context, at least one of the participants will be an unsolved type var, so we'll not get anything useful out of it. As @joroKr21 says we'll be checking for within bounds later anyway, so I don't think there's a problem here.

Why not do a foreach2(tparams, tvars)(propagateBounds) below, so that tparam2.tpeHK.instantiateTypeParams(tparams, tvars) can simply become tvar2? The tpeHK of a type parameter tparam2 is TypeRef(NoPrefix, tparam2, Nil), upon which we subst that to the corresponding tvar...

I realize you didn't write this code, but now that we're all on this crazy ride down the rabbit hole...

(This one is 13 years deep!)

@adriaanm I'm not quite following what you're suggesting ... propagateBounds takes a single argument, so it doesn't fit as an argument to foreach2. We do already have tparams.foreach(propagateBounds) and propagateBounds closes over tvars.

I agree, also in that case instantiate doesn't need to be a by-name parameter.

I pushed a cleanup of the existing code that I see as uncontroversial: https://github.com/adriaanm/scala/tree/review/6127. I would be grateful if you could rebase your PR on top of this. I know this has already been a lot of work, but I'd be more comfortable if we move slowly here.

Ahh ... OK, got it. Trying that now.

My commit has that refactoring already in place. The remaining bit would be to dive into higher-order args, and peel off eta-expansion.

Flippin' 'eck ... the solver has barely been touched in 13 years!?!

Yup... All the more reason to be weary of users having come to depend on its precise (mal)functioning.... Experience over the years has shown that touching old code is bound to upset users. As I said before, 2.13 is focused on library changes, so we must be especially careful as we're counting on spending our "breakage budget" on the collections rework.