Treat implicit by-name arguments as lazy values

With the previous rules, the two test cases produce a
diverging implicit expansion. We avoid this by creating
for every implicit by-name argument of type T a lazy implicit
value of the same type. The implicit value is visible for all
nested implicit searches of by-name arguments. That way,
we tie the knot and obtain a recursive lazy value instead of
a diverging expansion.

4 files changed, 150 insertions, 0 deletions

diff --git a/tests/run/lazy-implicit-lists.check b/tests/run/lazy-implicit-lists.check
new file mode 100644
index 000000000..60e3225b1
--- /dev/null
+++ b/tests/run/lazy-implicit-lists.check
@@ -0,0 +1,4 @@
+List()
+List(1, 2, 3)
+List()
+List(1, 2, 3)
diff --git a/tests/run/lazy-implicit-lists.scala b/tests/run/lazy-implicit-lists.scala
new file mode 100644
index 000000000..72099d0b2
--- /dev/null
+++ b/tests/run/lazy-implicit-lists.scala
@@ -0,0 +1,87 @@
+trait L
+case class C(hd: Int, tl: L) extends L
+case object N extends L
+
+trait Sum[+S1, +S2]
+case class Fst[+F](x: F) extends Sum[F, Nothing]
+case class Snd[+S](x: S) extends Sum[Nothing, S]
+
+case class Prod[+P1, +P2](fst: P1, snd: P2)
+
+trait shaped[SH1, SH2] {
+  def toShape(x: SH1): SH2
+  def fromShape(x: SH2): SH1
+}
+
+object Test {
+
+  type LShape = Sum[Prod[Int, L], Unit]
+
+  implicit def LShape: L `shaped` LShape =
+    new (L `shaped` LShape) {
+      def toShape(xs: L) = xs match {
+        case C(x, xs1) => Fst(Prod(x, xs1))
+        case N => Snd(())
+      }
+      def fromShape(sh: LShape) = sh match {
+        case Fst(Prod(x, xs1)) => C(x, xs1)
+        case Snd(()) => N
+      }
+    }
+
+  trait Listable[T] {
+    def toList(x: T): List[Int]
+  }
+
+  implicit def ShapedListable[T, U](implicit
+    ev1: T shaped U,
+    ev2: Listable[U]
+  ): Listable[T] =
+    new Listable[T] {
+      def toList(x: T) = ev2.toList(ev1.toShape(x))
+    }
+
+  implicit def SumListable[T, U](implicit
+    ev1: => Listable[T],
+    ev2: => Listable[U]
+  ): Listable[Sum[T, U]] =
+    new Listable[Sum[T, U]] {
+      def toList(s: Sum[T, U]) = s match {
+        case Fst(x) => ev1.toList(x)
+        case Snd(x) => ev2.toList(x)
+      }
+    }
+
+  implicit def ProdListable[T, U](implicit
+    ev1: Listable[T],
+    ev2: Listable[U]
+  ): Listable[Prod[T, U]] =
+    new Listable[Prod[T, U]] {
+      def toList(p: Prod[T, U]) = ev1.toList(p.fst) ++ ev2.toList(p.snd)
+    }
+
+  implicit def IntListable: Listable[Int] =
+    new Listable[Int] {
+      def toList(n: Int) = n :: Nil
+    }
+
+
+  implicit def UnitListable: Listable[Unit] =
+    new Listable[Unit] {
+      def toList(u: Unit) = Nil
+    }
+
+  def toList[T, U >: T](x: T)(implicit ev1: Listable[U]) = ev1.toList(x)
+
+  def main(args: Array[String]) = {
+    locally { // with specialized Listable
+      implicit lazy val LListable: Listable[L] = ShapedListable
+      println(toList(N))
+      println(toList(C(1, C(2, C(3, N)))))
+    }
+    locally { // without specialized Listable
+      println(toList(N))
+      println(toList(C(1, C(2, C(3, N)))))
+    }
+  }
+}
diff --git a/tests/run/lazy-implicit-nums.check b/tests/run/lazy-implicit-nums.check
new file mode 100644
index 000000000..00750edc0
--- /dev/null
+++ b/tests/run/lazy-implicit-nums.check
@@ -0,0 +1 @@
+3
diff --git a/tests/run/lazy-implicit-nums.scala b/tests/run/lazy-implicit-nums.scala
new file mode 100644
index 000000000..967472735
--- /dev/null
+++ b/tests/run/lazy-implicit-nums.scala
@@ -0,0 +1,58 @@
+trait Nat
+case class S(x: Nat) extends Nat
+case class Z() extends Nat
+
+trait Sum[+S1, +S2]
+case class Fst[+F](x: F) extends Sum[F, Nothing]
+case class Snd[+S](x: S) extends Sum[Nothing, S]
+
+trait shaped[SH1, SH2] {
+  def toShape(x: SH1): SH2
+  def fromShape(x: SH2): SH1
+}
+
+object Test {
+
+  type NatShape = Sum[Nat, Z]
+
+  implicit def natShape: Nat `shaped` NatShape =
+    new (Nat `shaped` NatShape) {
+      def toShape(n: Nat) = n match {
+        case S(m) => Fst(m)
+        case Z() => Snd(Z())
+      }
+      def fromShape(s: NatShape) = s match {
+        case Fst(n) => S(n)
+        case Snd(_) => Z()
+      }
+    }
+
+  trait Countable[T] {
+    def count(x: T): Int
+  }
+
+  implicit def ShapedCountable[T, U](implicit
+    ev1: T shaped U,
+    ev2: Countable[U]
+  ): Countable[T] =
+    new Countable[T] {
+      def count(x: T) = ev2.count(ev1.toShape(x))
+    }
+
+  implicit def SumCountable[T, U](implicit
+    ev1: => Countable[T]
+  ): Countable[Sum[T, U]] =
+    new Countable[Sum[T, U]] {
+      def count(s: Sum[T, U]) = s match {
+        case Fst(x) => ev1.count(x) + 1
+        case Snd(_) => 0
+      }
+    }
+
+  def count[T, U >: T](x: T)(implicit ev1: Countable[U]) = ev1.count(x)
+
+  def main(args: Array[String]) = {
+    println(
+      count(S(S(S(Z())))))
+  }
+}