Fetch breaks on Cats 2.7.0 due to Traverse implementation detail

[sloshy]

Noticed that CI for upgrading to Cats Effect 3.3.x has been failing recently and after looking into it, it seems the reason it fails is due to calls to .traverse in tests not working as before. This is in tests that use .traverse in some way, such as assuming it will auto-batch requests.

Root cause of problem

We're detecting batches based on calls to map2, product, and productR in our Monad[Fetch] implementation to optimize for batches, but now it seems as of Cats 2.7.0 (transitive dependency of Cats Effect 3.3.x) map2 is not guaranteed to be called. This can be demonstrated by changing the version of Cats and noticing that the same tests fail as in the current CI pipelines for Cats Effect upgrade PRs.

More details

In our tests we have a helper function one that fetches some pure value. If we have a test that fetches, in order, in a for-comprehension the following values as-written:

• one(1)
• one(2)
• one(3)
• List(1, 2, 3).traverse(one(_))

On Cats Effect 3.2.x it correctly batches the List(1, 2, 3) calls together under-the-hood. However, starting with Cats Effect 3.3.x it is now based on Cats 2.7 which appears to have changed the underlying implementation of .traverse.

To test this I added print-debugging statements to the Monad[Fetch] instance to see what methods were being called. Batch-detection is only done when certain methods are called such a map2 or product, which traverse had historically used before. Now, it appears it is only calling map and flatMap instead.

Here is a sample of my print debugs from a test that is running on Cats 2.6.x:

Called map2 with:
blocked RequestMap(Map(16 -> (fetch.TestHelper$One$$anon$1@1e,BlockedRequest(FetchOne(2,fetch.TestHelper$One$@10),CombinationLeaf(<function1>))))) and blocked RequestMap(Map(16 -> (fetch.TestHelper$One$$anon$1@1d,BlockedRequest(FetchOne(3,fetch.TestHelper$One$@10),CombinationLeaf(<function1>)))))

combining...

Called map2 with:
blocked RequestMap(Map(16 -> (fetch.TestHelper$One$$anon$1@1f,BlockedRequest(FetchOne(1,fetch.TestHelper$One$@10),CombinationLeaf(<function1>))))) and blocked RequestMap(Map(16 -> (fetch.TestHelper$One$$anon$1@1d,BlockedRequest(Batch(NonEmptyList(2, 3),fetch.TestHelper$One$@10),CombinationSuspend(<function1>)))))

combining...

Called map with:
blocked RequestMap(Map(16 -> (fetch.TestHelper$One$$anon$1@1d,BlockedRequest(Batch(NonEmptyList(1, 2, 3),fetch.TestHelper$One$@10),CombinationSuspend(<function1>)))))

Called map with:
blocked RequestMap(Map(16 -> (fetch.TestHelper$One$$anon$1@1d,BlockedRequest(Batch(NonEmptyList(1, 2, 3),fetch.TestHelper$One$@10),CombinationSuspend(<function1>)))))

Called flatMap with:
blocked RequestMap(Map(16 -> (fetch.TestHelper$One$$anon$1@1d,BlockedRequest(Batch(NonEmptyList(1, 2, 3),fetch.TestHelper$One$@10),CombinationSuspend(<function1>)))))

Called map with:
value 3

Called map2 with:
values 2 and List(3)

Called map2 with:
values 1 and List(2, 3)

Called map with:
value List(1, 2, 3)

This is how it is resolving a Fetch[F, List[Int]] under-the-hood. To break it down, first it is combining the fetch for 2 and 3, into a fetch for NonEmptyList(2, 3), and then it is combining that with the fetch for 1, which turns it into a Batch(NonEmptyList(1, 2, 3)). It's then able to run these batches and get the final list as expected, but only making one fetch for these three values.

On Cats 2.7.0, however, map2 is never called. Instead, it appear to only ever call map and flatMap. Since map2 or product or productR are the only methods that can detect and optimize for a batch like this, the tests that depend on this implementation detail of traverse will fail.

Thoughts

This makes sense to me given my understanding of the laws of the type classes we are depending on. There is nothing about .traverse that says it has to be done using .map2. We should look into determining what should be batched some other way if possible, or representing the intent in a more obvious way.

Given List(a, b, c).traverse(f) should, in my mind, be equivalent to f(a).flatMap(fa => f(b).flatMap(fb => f(c).map(fc => List(fa, fb, fc)))) it does not seem readily apparent how to extract from that the intent to batch without asking the user, anyway. Though I might be missing something.

[fedefernandez]

Thanks, @sloshy. I agree with you. We probably want to add a way to explicitly mark a series of operations to be potentially processed as a batch (if it doesn't exist yet), update the traverse tests to do not rely on map2, and release a version marked with breaking changes. Those are my thoughts but looking for other opinions as well.

[cb372]

Thanks for the thorough investigation and clear writeup @sloshy. I agree, a breaking API change to allow users to make the desire for batching explicit is the way to go. Even if we hadn't run into this issue, having batching happen automatically and invisibly like this is a bit too magical for my liking.