search

alexarchambault / scalacheck-shapeless

Generation of arbitrary case classes / ADTs instances with scalacheck and shapeless
Apache License 2.0
239 stars 35 forks source link

compilation goes on forever with shapeless 2.2.0-RC6 #7

Open meoyawn opened 9 years ago

meoyawn commented 9 years ago

https://github.com/adelnizamutdinov/shapeless-rc6-scalacheck Here's a sample project that compiles successfully with 2.2.0-RC4 but when I change that to 2.2.0-RC6, compilation goes on forever (though it sometimes finishes saying that it could not find an implicit Arbitrary)

milessabin commented 9 years ago

It appears that RC6 is having trouble with the ImageSize enumeration.

I'm still investigating the root cause, but in the meantime I think that providing an explicit Arbitrary instance for ImageSize should be a workaround.

milessabin commented 9 years ago

OK, I think I see what's happening here, although I don't entirely understand why the behaviour has changed between RC4 and RC6.

We can reproduce the problem with,

case class Foo(size: ImageSize)
implicitly[Arbitrary[Foo]]

The problem is with ScalaChecks definition of arbContainer2 ... this pattern will match an HList (with C[_, _] as ::[_, _] and the head and tail as T and U respectively). In context, T is ImageSize and U is HNil, ie. the generic representation of Foo.

In attempting to resolve the implicit arguments of arbContainer2 the typechecker will start by attempting to resolve an arbitrary instance for (ImageSize, HNil). Either directly or indirectly this will loop back through the generic derivation and attempt to derive an instance for ImageSize :: HNil :: HNil, which again matches arbContainer2 and we're off on a non-terminating regression.

I think it should be possible to fix this in scalacheck-shapeless somehow, probably by masking or deprioritizing arbContainer2 somehow. Most likely ScalaCheck could also be tweaked slightly to resolve the problem, but I don't think it would be reasonable to expect ScalaCheck to change to accommodate this scenario (/cc @rickynils)

The question for me is whether or not I can or should change shapeless to fix this. Ultimately that boils down to whether I can come up with a more sophisticated form of divergence checking which would catch this case without also excluding the kinds of recursion that we want to support. I don't currently have a clear idea of how to go about doing that.

I have, I suppose, been pretty much saying that using Lazy means you're sure that the implicit resolution will converge, hence divergence checking should be suspended. The risk is that if you call that wrong then typechecking can loop, and that's what's happened here.

Thoughts on how best to proceed would be very welcome ...

milessabin commented 9 years ago

FWIW, I think the fix in ScalaCheck would be to move the implicit argument a: Arbitrary[(T, U)] after the argument b: Buildable[(T,U),C[T,U]] in the definition of arbContainer2. b won't resolve because there's no Buildable for shapeless.:: (at least, I presume there isn't), so resolution of implicit arguments would stop there and not consider Arbitrary[(T, U)] at all. /cc @rickynils.

milessabin commented 9 years ago

In fact, that might be a clue to a fix in scalacheck-shapeless ... the fix might be to duplicate arbContainer2 in object Shapeless modified as described in my previous comment.

milessabin commented 9 years ago

@InTheNow has verified locally that my suggested change in ScalaCheck does resolve the problem. So the change in scalacheck-shapeless should be good too.

alexarchambault commented 9 years ago

Thanks for having looked at this @milessabin and @InTheNow ! (I was kind of busy with other projects of mine, I delayed looking at it). I'll try the workaround you suggest soon.

ghost commented 9 years ago

@alexarchambault np. Btw, The new release of scalacheck has even better scalajs support, as shapeless itself now has. Had you considered cross-compiling this project to support scalajs? As an example, you could start with machinest

alexarchambault commented 9 years ago

Added Foo and ImageSize to the tests here: https://github.com/alexarchambault/scalacheck-shapeless/tree/topic/issue7

I'd like to have a more careful look at that, but with cached implicits, I got no divergence / infinite loop, just failed implicit derivation without https://github.com/alexarchambault/scalacheck-shapeless/blob/topic/issue7/src/test/scala/org/scalacheck/Definitions.scala#L65-L66

@InTheNow I'll give scalajs a try if I can find some time to do it, looks like a good idea. (Thanks for the hint and the link.)