Typer hangs with implicits that return TypeTags (regression from 2.10)

[scabug]

Scala 2.11 can't type this over night, but 2.10 runs quickly.

import scala.reflect.runtime.universe.TypeTag

trait Minimized {

  type Rep[+T]

  def abs(__arg0: Rep[Double]): Rep[Double] = infix_abs(Math,__arg0)

  object Math

  def infix_abs(self: Math.type, __arg0: Rep[Double]): Rep[Double]
  def infix_abs[T:Arith](self: Rep[DenseVector[T]]): Rep[DenseVector[T]]

  //trait Arith[T] // works
  //type Arith[T] = Manifest[T] // hangs / takes forever
  type Arith[T] = TypeTag[T] // hangs / takes forever

  type DenseVector[T]
  implicit def m_DenseVector[T:Arith]: Arith[DenseVector[T]]

  implicit def tupleToDense2[A:Arith,B](t: Tuple2[A,B]): Rep[DenseVector[A]]

  type Tup2[A,B]
  implicit def m_Tup2[A:Arith,B:Arith]: Arith[Tup2[A,B]]
  type Tup3[A,B,C]
  implicit def m_Tup3[A:Arith,B:Arith,C:Arith]: Arith[Tup3[A,B,C]]
  type Tup4[A,B,C,D]
  implicit def m_Tup4[A:Arith,B:Arith,C:Arith,D:Arith]: Arith[Tup4[A,B,C,D]]
  type Tup5[A,B,C,D,E]
  implicit def m_Tup5[A:Arith,B:Arith,C:Arith,D:Arith,E:Arith]: Arith[Tup5[A,B,C,D,E]]
  type Tup6[A,B,C,D,E,F]
  implicit def m_Tup6[A:Arith,B:Arith,C:Arith,D:Arith,E:Arith,F:Arith]: Arith[Tup6[A,B,C,D,E,F]]
  type Tup7[A,B,C,D,E,F,G]
  implicit def m_Tup7[A:Arith,B:Arith,C:Arith,D:Arith,E:Arith,F:Arith,G:Arith]: Arith[Tup7[A,B,C,D,E,F,G]]
  type Tup8[A,B,C,D,E,F,G,H]
  implicit def m_Tup8[A:Arith,B:Arith,C:Arith,D:Arith,E:Arith,F:Arith,G:Arith,H:Arith]: Arith[Tup8[A,B,C,D,E,F,G,H]]
  type Tup9[A,B,C,D,E,F,G,H,I]
  implicit def m_Tup9[A:Arith,B:Arith,C:Arith,D:Arith,E:Arith,F:Arith,G:Arith,H:Arith,I:Arith]: Arith[Tup9[A,B,C,D,E,F,G,H,I]]
}

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-8992?orig=1 Reporter: @TiarkRompf Affected Versions: 2.11.2, 2.11.4

[scabug]

@xeno-by said: Hi, sorry didn't have time to look into this issue yet. How urgent is is for you?

[scabug]

@TiarkRompf said: Hi Eugene, currently this is a blocker for switching Delite to 2.11, so it would be nice to have a fix soonish. Since it seems to be a regression from 2.10 I was hoping this would be an easy one. Thanks!

[scabug]

@TiarkRompf said: If this could be fixed for 2.11.5, that would be great.

[scabug]

@xeno-by said (edited on Dec 6, 2014 10:40:20 PM UTC): The exponential cascade of implicit searches is the result of the change introduced in #3346.

When trying to resolve the overload for infix_abs(Math,_arg0), scalac tries to see whether def infix_abs[T:Arith](self: Rep[DenseVector[T]]): Rep[DenseVector[T]] is applicable. It sees an implicit conversion from Tuple2 to Rep[DenseVector], and goes for it, packing Math and _arg0 into a tuple and then trying to typecheck the application of the said conversion (implicit def tupleToDense2[A:Arith,B](t: Tuple2[A,B]): Rep[DenseVector[A]]) to (Math,_arg0).

What happens then is caused by the aforementioned bugfix. In 2.10.x, tupleToDense2 implicit candidate is triaged without resolving implicit arguments (the A: Arith context bound), whereas in 2.11.x typedImplicit1 is changed to resolve implicit arguments during triaging. Therefore in 2.11.x, the mere fact of considering tupleToDense2 as an implicit conversion, will launch an implicit search for Arith[A].

Now, a bunch of implicit methods provide Arith[Something], and, what's worse, triaging those implicit methods will cause other Something: Arith context bounds to be resolved, launching more and more implicit searches for Arith[Something]. That quickly gets out of hand.

Do you think it would be possible for you to restructure the code so that this avalanche of implicit lookups doesn't get spawned?

[scabug]

@TiarkRompf said: Thanks for the analysis!

This particular case with Math is easy to work around but unfortunately this bug tends to show up unexpectedly, and in very different places. So difficult to restructure globally. It's also very hard to debug for non-compiler experts because scalac just hangs without any error message.