Issues with given prioritization change

[tgodzik]

With 3.7.0 the new given prioritization comes into effect, which might cause libraries like chimney or cats-effect to not work properly even if compiled with an earlier version.

So in essence:

1. Library gets compiled and tests with 3.3.5 LTS . It heavily uses the old priority of givens
2. Someone uses that library in 3.7.0 and the code doesn't work since the compiler behaviour changed.

Do we have a way to fix it for users? We could potentially use the source flag in the user code to revert to older priority, but that makes them unable to use any new features and stuck with 3.6.0.

We could also add a separate flag for that case, but that make everyone need to use that flag until cats reimplement the given resolution, which I am not even sure is doable.

Another, bad idea, is to cross compile pre and after 3.7.0, but that is not something we wanted to ever do.

Do we have any sensible solution to that problem? Cats-effect is one of the wider used libraries, so it would be great to be able to fix the issue even before the new priority comes into effect.

Since I don't know much about details it would be great to hear from someone who knows more details

CC
@armanbilge @lbialy @WojciechMazur

I think Wojciech and Łukasz were doing some tests, but not sure if they managed to find a conclusion.

I have limited knowledge here, so it's possible it's not an issue.

[tgodzik]

@odersky I wanted to discuss it during the previous core meeting since it was raised by a couple of open source contributors as a possible issue.

[djspiewak]

I'll let Arman speak to it since he probably remembers more of the context than I do, but he and I discussed this at length back when the SIP was going through its paces. Our conclusion at the time was that the new prioritization would have no effect on Cats Effect and probably wouldn't affect Cats either, but obviously this stuff tends to be subtle and surprising. There's basically no way to be sure outside of trying to compile a ton of downstream code.

The one place where I could see surprising user-facing things popping up is we tend to do some stuff which looks like this:

  def apply[F[_], E](implicit F: GenConcurrent[F, E]): F.type = F
  def apply[F[_]](implicit F: GenConcurrent[F, ?], d: DummyImplicit): F.type = F

These are the summoners for the Concurrent typeclass. Note that this is a bit different from how it's conventionally done in Cats, where the return type would just be GenConcurrent. We do the path-dependent thing here because we want to ensure that the specific type information is carried through from the inference. This in turn means that users can do Concurrent[F] and the type of that expression might be Async[F] (as an example). The new given priorities definitely don't break this mechanism, but I wonder if we've thought through all the source-level implications at the call site. As I said, it's really hard to tell.

The risk here is real though. Manipulating given prioritization in general requires tucking things into varying levels of the inheritance hierarchy, and so if we have a situation where compiling against 3.7 results in libraries outright breaking, it's possible (though not guaranteed) that we would have no way to fix this in a way which is binary compatible with previous library releases, to say nothing of source compatibility with previous Scala releases.

[bishabosha]

you can detect the tasty version of the symbol and change semantic (sounds evil)

[tgodzik]

The change in question didn't actually go through SIP process I think. I think it was deemed to be minor change, but in reality it might not be.

#19300

[djspiewak]

Ah my bad. Like I said, hazy memory. I was thinking of the PR.

[sjrd]

you can detect the tasty version of the symbol and change semantic (sounds evil)

No you can't. Candidate implicits can come from two sources, with both old and new semantics, but you have to pick one.

[lbialy]

We did in fact execute a spike into this problem. The motivation for this research was that:

a) there were some rather uncomfortable warnings present in the OCB log when the original blast radius analysis was done for this change. Initially the assumption was that these were all fine and the number of ambiguous clashes was very low in OCB so we assumed it's going to be fine.

b) @MateuszKubuszok gave us a hint that this change does break Chimney as it depends on a significance of typeclass hierarchy - namely for Transformer typeclass there's a super type Transformer.AutoDerived[A, B] that has instances generated by a macro and a subtype Transformer[A, B] that is left for user to provide for specific cases. Macro itself looks for Transformer instances only (only instances given by the user) and if there aren't any, attempts to derive instances recursively (by providing AutoDerived[A, B] for these types). This is done for reasons of macro efficiency, better error messages etc. Example of how this fails to compile under new rules can be seen here:

//> using scala 3.7.0-RC1

trait TypeClass[A] extends TypeClass.AutoDerived[A]
object TypeClass {
  trait AutoDerived[A]
  object AutoDerived {
    given [A]: AutoDerived[A] = new TypeClass[A] {}
  }
}

class Foo
object Foo {
  given TypeClass[Foo] = new TypeClass[Foo] {}
}

def use[A: TypeClass.AutoDerived]: Unit = println(summon[TypeClass.AutoDerived[A]])

@main def main = use[Foo]
//-- [E172] Type Error: ----------------------------------------------------------
//16 |@main def main = use[Foo]
//   |                         ^
//   |Ambiguous given instances: both given instance given_AutoDerived_A in object AutoDerived and given instance //given_TypeClass_Foo in object Foo match type TypeClass.AutoDerived[Foo] of a context parameter of method use
//1 error found

There is no way for this to be resolved under new rules and Chimney will have to deal with this by having two parallel major releases, on for scala 2.13 & 3.x where x < 7 and for 3.7+. To make Chimney possible for Scala 3.7+ a new macro combinator was introduced by @jchyb, summonIgnoring, that takes a list of symbols to ignore in implicit search which allows to encode the same logic of finding user-provided instances while ignoring the macro itself. This means however that the hierarchy has to be abolished altogether and that chimney for 3.7+ will only have Transformer[A, B] typeclass, hence new major release.

This realisation made us wonder if the same will happen to cats / cats-effect and typelevel ecosystem and given the potential blast radius of this possibility, we spent some time investigating. The result of our spike is that we haven't been able to find conclusive evidence of breakage of significance similar to the one in Chimney. We have explored three approaches:

1. first approach was to force all cats typeclasses to be resolved using new rules. To do that we had to declare them using givens. I forked cats and cats-effect with the goal of using these forks in OCB to find compile and runtime issues at scale. I replaced all implicit uses beside implicit conversions (things like implicit def f[F[_]: Constraint](a: A)(implicit F: Constraint[F]): FOps[F, A]) with givens, then did the same with cats-effect. This was a rather non-trivial piece of work given that there are some implicit patterns that are impossible to translate to givens (for example in some settings givens are final and overriding them is impossible) and that literal replacement of implicits with givens led to at least some cases of deadlocks on lazy vals (@WojciechMazur can elaborate on this). The farthest I was able to get with this was that main scope did compile and publish locally for both libraries (test scope did not however!). Execution on OCB with these forks did not yield any new and significant information about breakage from what I recall but it was also plagued with issues arising from problems orthogonal to the given priority change - breakage introduced by forks being subtly incompatible version of Cats/CE in comparison to versions used in OCB targets, difficulty in comprehensive replacement in imports for import cats.implicits.given etc (many places use specialized imports and it's quite difficult to correctly mark these imports as import given at scale), aforementioned lazy val deadlocks locking tests for things that did manage to compile etc.

Cats fork
Cats Effect fork

Disclaimer: these forks were in no way an attempt to port cats/CE to S3 givens in a sane and comprehensive way.

2. another approach was to leverage what compiler can do for us - @jchyb implemented a change to the dotty parser that made it treat all implicits as givens. This worked to some degree but also run into many limitations and orthogonal problems. No new breakage information was found using this approach.

3. in depth investigation of cases found in the original report by @WojciechMazur - prior to Scalar I tried to investigate the nature of warnings of code indicated as impacted in the gist and also of errors in cats/cats-effect test scopes. This was quite straightforward - I explored what is the structure of the typeclass hierarchy in cats for several positions highlighted as changing the resolved type in 3.7+ and tried to prove that it is in fact selecting a different concrete instance. In all cases I looked into there were several types in the hierarchy and just a single concrete instance that implemented them. Moreover, in most of these cases the warning was caused by user depending on the more general typeclass, old resolution rules providing instance matching lowest subtype of the typeclass and new rules providing instance matching the demanded general super type like in this case from gvolpe/trading:

      {
        "change": {
          "target": "cats.kernel.Eq[A]",
          "first": "cats.kernel.Order[A]",
          "second": "cats.kernel.Eq[A]",
          "currentChoice": "FirstAlternative",
          "newChoice": "SecondAlternative"
        },
        "count": 1
      }

The hierarchy is Eq[A] <- PartialOrder[A] <- Order[A], user demands Eq[A], the instance that exists implements Order (so transitively it also implements Eq), selection rules change from Order to Eq but in fact it is exactly the same concrete instance that is being resolved. This logic applied to all examples I have manually checked but that wasn't a huge number of cases. It did however manage to convince me that it's quite probable that we won't run into a catsastrophe as I feared with the release and subsequent migration of Cats/CE to new Scala 3 LTS version. There still remains the problem of issues with test scope in forks of Cats and CE where I did run into ambiguity errors. Short exploration of these issues made me think that these problems are related to how test instances are provided and that's why we didn't run into these issues when compiling code at scale in OCB. It would probably still be good if someone who is more intimately familiar with how cats/CE typeclasses are organized and implemented by concrete instances looked into these test scope compile failures in our forks.

[djspiewak]

@lbialy That's a wonderful bit of investigation thank you. I'll try to look at your forks at some point this week.

Your explanation did make me realize that we might have some problems related to this which wouldn't show up in functional testing. In particular, there are a bunch of places both in Cats and Cats Effect where a more specific instance of a typeclass overrides the definition of some concrete method with a more efficient implementation, basically leveraging the stricter guarantees it has available to it by being lower in the hierarchy. We actually even surface this information (internally) at runtime and use it to manually specialize certain things. In particular, look at Queue, as well as the overrides of GenConcurrent#deferred.

Now, for concrete types like IO there's really only one possible instance anyway (IO.asyncForIO), so it's basically fine, but anyone touching monad transformers (or Resource, which is really widely used) is going to get a whole slew of plausible derived instances, and specificity starts to really matter. Getting the most general derived instance would result in silent deoptimization of call sites. The exact order of magnitude of impact here is hard to predict, and it's very use-case specific, but in some benchmarks the more optimized Async-based Queue is 5-10x faster than the more generic Concurrent-based Queue (this is deceptive though because usually thread contention dominates). That sounds pretty bad, particularly since major libraries like Http4s do indeed heavily leverage monad transformers and Resource, but Queue itself isn't actually used heavily because Fs2 provides Channel (which has only a single implementation). Channel is based on Deferred though, which does do this kind of runtime specialization stuff.

So in other words… I do think there's probably some danger here. I really would be surprised if anything functionally breaks at compile- or runtime, but I could definitely see cases where performance is silently regressed by significant amounts.