Infinite macro expansion regression on 2.12.3/2.12.4

[djspiewak]

I haven't yet minimized this; it's definitely a weird one.

I have a pair of sources which compile just fine on 2.11.11 (and 2.11.8), 2.12.0, 2.12.1 and 2.12.2. When I attempt to compile them on 2.12.3 or 2.12.4, the compiler goes into what appears to be an infinitely looping macro expansion (judging by stack dumps). Based on the fact that the stack does grow, albeit quite slowly, I'm guessing the compiler will eventually crash. I let it run for a little over 10 minutes before giving up and calling it a day.

The reproducer can be found on the shims project, and was specifically tested with commit a47b95c. To reproduce:

1. sbt clean compile
2. sbt test:compile

You could also do coreJVM/test:compile if you want to factor out scala.js. You should see the compiler spin forever on the two test sources. Word of warning: this project seems to trigger some unrelated bugs in Zinc (this is sbt 0.13.16), and incremental compilation is not to be trusted with it.

There are three macros in the project (all variations of each other), and all of them are implicit. You can find their definitions in macros.scala, and their declaration points in capture.scala. If I had to guess, I would say that what is probably happening is the compiler is macro-expanding to a tree which somehow triggers implicit search to expand the same macro recursively on the generated tree. This is happening slow enough that the stack doesn't bottom out instantly (since macro compilation and re-typechecking is relatively slow). That's just a guess though.

[retronym]

Implicit macros that call inferImplicitValue are self-responsible for tracking and preventing divergence.

This is sufficient to demonstrate the divergence in 2.12.3+

package shims

import scalaz.std.option._

object MonadConversionSpecs {
  cats.Invariant[Option]
}

util.this.Capture.materialize[cats.Monad[Option]]
  inferImplicitValue(cats.Monad[Option])
    shims.this.`package`.monadToScalaz[Option](implicitly[shims.util.Capture[cats.Monad[Option]]])
      util.this.Capture.materialize[cats.Monad[Option]]

It would be interesting to find out what changed between 2.12.2 and 2.12.3 to change the behaviour, but I believe the macro is treading in very dangerous territory. If I'm correct in assuming that materializeCapture is derived from similar macro implementations in Shapeless, I'd suggest looking for any improvements over there that need to be be ported over.

[djspiewak]

So the purpose of the macro, ironically, is to work around another bug in scalac (one which I don't think I have reported yet). This other bug relates to divergence checking, and it's basically the fact that divergence errors override successful derivations along other branches in the implicit search space. This is unique among errors during implicit search, as others (including ambiguities) will be eaten by successful matches.

What this means in practice is that you cannot form an implicit which could diverge in cases where another branch of the implicit search space would be successful and unambiguous. I have a pretty trivial reproduction for this issue as well. Dotty does not exhibit the same behavior.

To work around that flaw in the implicit search tri-logic, this macro calls implicit search directly and catches any errors, rewriting them into something that is not a divergence error. As non-divergences are handled differently from divergences, this rewriting allows the compiler to proceed forward and find the valid branch, rather than immediately dropping the whole type on the floor. As a matter of convenience, the macro also handles a subtype negation test which was previously resolved in a separate implicit.

At any rate…  The trick is unique to shims, I believe, but the materialization of the type in question and the call to inferImplicitValue were copied from the Cached implicit in shapeless. Cached is pretty trivial, but it does include a piece of global state which (unsoundly) memoizes implicit results. If I had to guess, I would suppose that this state is also voiding the divergence. Either that, or divergent cases simply haven't been tested. The shims implicit scope does by definition include cycles; this is why I need to have the subtype negation check.

I would guess that the difference between 2.12.2 and 2.12.3 has to do with the order in which branches are attempted during implicit search. The legitimately cyclic branch is being tried ahead of the other branches, and notably its cyclic child tree is also being tried before the branch itself gets nulled out. I can probably resolve this by stuffing some global state into materializeCapture and trying to piece together if and when the macro is hit twice consecutively with the exact same type. It's hard to say how reliable that would be though.

I would much rather simply not have to work around the invalid tri-value logic in implicit search, but due to the nature of shims, I really need it to be functional on 2.11 and 2.12, which is why I didn't first explore a bugfix in the compiler. Perhaps there's a better workaround than what I'm currently doing?

Edit f1fdc1901cb29c34277e230d1547f800072ea818 seems somewhat suspicious on the "what changed here?" front.

[djspiewak]

Ok, so I've implemented a workaround in CaptureMacros: djspiewak/shims@689837c It's not great, but it seems to work.