better unification for compound types

[scabug]

See bug #1 in the context of this mailing list post:

http://groups.google.com/group/shapeless-dev/browse_thread/thread/1f26830027f3517

"1. It will not choose the correct implicit function for any type after
the first type in the destination disjunction."

The link below is an improved implementation that has the same bug, is less complex to follow, and thus if I am correct probably demonstrates that the problem is not peculiar to a simulated union type and rather general to implicits and compound type leaf nodes (i.e. those after the first with, e.g. the D[String] in D[D[Int] with D[String]]), when the implicit matching is in the contravariant direction. The neg implicit is chosen for D[D[Int]] but not for D[D[String]].

http://groups.google.com/group/shapeless-dev/browse_thread/thread/01f26830027f3517/7c1006ac6e638044?#7c1006ac6e638044

P.S. There is a duplicate syntax-highlighted version buried nearer to the bottom of the following stackoverflow answer:

http://stackoverflow.com/questions/3508077/does-scala-have-type-disjunction-union-types/7460312#7460312

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-5550?orig=1
Reporter: Shelby Moore III (shelby)

[scabug]

@adriaanm said:
sorry we do not have the resources to unearth bug reports from mailing list posts

a bug report like this should have a minimal code example that should compile but doesn't, or conversely, that does but shouldn't

[scabug]

Shelby Moore III (shelby) said (edited on Nov 7, 2012 3:51:56 PM UTC):
Hi Adriaan,

Here is the code example that does not compile.

class D[-A] (v: A) {
  def get[T <: A] = v match {
    case x: T => x
  }
}

implicit def neg[A](x: A) = new D[D[A]]( new D[A](x) )

def size(t: D[D[Int] with D[String]]) = t

size("")

error: type mismatch;
 found   : java.lang.String("")
 required: D[D[Int] with D[String]]
       size("")
            ^

Note that if we change the last line size("") to either of the following, then it does compile.

size(5)
res0: D[D[Int] with D[String]] = D@77d66

size("hi" : D[D[String]])
res1: D[D[Int] with D[String]] = D@a6bf88

So the problem is the implicit is not being found for the 2nd or greater leaf node in the input type, e.g.

D[D[Int] with D[String]]

Please let me know if this is insufficient to reopen this bug, and in such case, what further information you need from me.

[scabug]

Shelby Moore III (shelby) said:
See the code sample I added, which does not compile.

[scabug]

Shelby Moore III (shelby) said (edited on Nov 7, 2012 3:49:15 PM UTC):
I was able to find an alternative formulation for the size function, which avoids the bug. But it is less efficient, as it must call the implicit function neg twice.

def size[T](t: T)(implicit d: D[D[T]] <:< D[D[Int] with D[String]]) = (t: D[D[T]]) match {
  case x: D[D[Int]] => x.get[D[Int]].get[Int]
  case x: D[D[String]] => x.get[D[String]].get[String]
}

size(5)
res2: Any = 5

size("hi")
res4: Any = hi

It correctly fails to compile for input types that should not be allowed.

size(5.0)
error: could not find implicit value for parameter d: <:<[D[D[Double]],D[D[Int] with D[String]]]
       size(5.0)
           ^

[scabug]

Shelby Moore III (shelby) said (edited on Nov 8, 2012 8:57:41 AM UTC):
To combine the fix from the other bug report:

https://issues.scala-lang.org/browse/SI-5549?focusedCommentId=57261&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-57261

class D[-A] (v: A) { def get = (v : Any) }

class DD[-A >: D[Any]] (v: A) { def get = (v : Any) }

implicit def neg[A](x: A) = new DD[D[A]]( new D[A](x) )

def size[T](t: T)(implicit d: DD[D[T]] <:< DD[D[Int] with D[String]]) = t

scala> size(5)
res0: Int = 5

scala> size("")
res1: java.lang.String = 

scala> size(5.0)
error: could not find implicit value for parameter d: <:<[DD[D[Double]],DD[D[Int] with D[String]]]
       size(5.0)
           ^

scala> size(5.0 : Any)
error: could not find implicit value for parameter d: <:<[DD[D[Any]],DD[D[Int] with D[String]]]
       size(5.0 : Any)
           ^

[scabug]

Shelby Moore III (shelby) said (edited on Nov 8, 2012 1:45:38 PM UTC):
Note the workaround is not a solution for all cases, because this bug infects function definition sites that I can't edit, e.g. the apply method of object Array.

I was attempting to code with reduced noise and reduced tsuris of unboxed disjunctions.

scala> val test = Array[DD[D[Int] with D[Option[Nothing]]]](None, 1, 2, None, 3)
error: type mismatch;
 found   : None.type (with underlying type object None)
 required: DD[D[Int] with D[Option[Nothing]]]
       val test = Array[DD[D[Int] with D[Option[Nothing]]]](None, 1, 2, None, 3)
                                                            ^

scala> val test = Array[DD[D[Option[Nothing]] with D[Int]]](None, 1, 2, None, 3)
error: type mismatch;
 found   : Int(1)
 required: DD[D[Option[Nothing]] with D[Int]]
       val test = Array[DD[D[Option[Nothing]] with D[Int]]](None, 1, 2, None, 3)
                                                                  ^

I can avoid the bug by verbosely forcing the choice of implicit, thus verifying that this bug is culpable.

type None = Option[Nothing]

val test = Array[DD[D[None] with D[Int] with D[String]]]( None, 1 : DD[D[Int]], "two" : DD[D[String]] )

scala> test(0).get match {
  case x:D[_] => x.get match {
    case x:None => 1
    case x:Int => 2
    case x:String => 3
    case _ => 4
  }
}
res0: Int = 1

scala> test(1).get match {
  case x:D[_] => x.get match {
    case x:None => 1
    case x:Int => 2
    case x:String => 3
    case _ => 4
  }
}
res1: Int = 2

And even if I could edit the apply method, the sequence T* subsumes to Any before the implicit for the workaround is applied. So only the bug fix can help.

def apply[T](xs: T*)(implicit d: DD[D[T]] <:< DD[D[Int] with D[String]]) = xs

scala> apply(1)
res4: Int* = WrappedArray(1)

scala> apply("")
res5: java.lang.String* = WrappedArray()

scala> apply(1, "")
error: could not find implicit value for parameter d: <:<[DD[D[Any]],DD[D[Int] with D[String]]]
       apply(1, "")
            ^

[scabug]

Shelby Moore III (shelby) said (edited on Nov 8, 2012 2:26:20 PM UTC):
Perhaps this comment will be getting even further away from the actual bug, which is more general to unification of compound types.

I found a work-around for the prior comment that does not require writing down the types for each literal element.

type None = Option[Nothing]

class DArray[T >: D[Any]](val len: Int) {
  var array = new Array[DD[T]](len)
  var length = 0
  def apply[A](v: A)(implicit d: DD[D[A]] <:< DD[T]): DArray[T] = {
    array(length) = v : DD[D[A]]
    length += 1
    this
  }
}

val test = new DArray[D[None] with D[Int] with D[String]](3)

scala> test(None).apply(1).apply("two").array
res0: Array[DD[D[None] with D[Int] with D[String]]] = Array(DD@179eb02, DD@133e7a1, DD@ac0b08)

I was trying for a more concise version of the code below, but it can not be used because issue SI-6630 is not a bug.

scala> test(None)(1)("two")
error: type mismatch;
 found   : Int(1)
 required: <:<[DD[D[object scala.None]],DD[D[None] with D[Int] with D[String]]]
       test(None)(1)("two")
                  ^

[SethTisue]

I'm not able to make head or tail of what this was supposed to be about

[joroKr21]

The problem is about type inference of compound types.
The user expected neg to match in both cases but it doesn't because of type inference:

5: D[D[Int] with D[String]]
5: D[D[String] with D[Int]]