Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

better unification for compound types #5550

Open
scabug opened this issue Mar 5, 2012 · 9 comments
Open

better unification for compound types #5550

scabug opened this issue Mar 5, 2012 · 9 comments

Comments

@scabug
Copy link

scabug commented Mar 5, 2012

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
Copy link
Author

scabug commented Mar 5, 2012

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

@scabug
Copy link
Author

scabug commented May 3, 2012

@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
Copy link
Author

scabug commented May 3, 2012

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
Copy link
Author

scabug commented May 3, 2012

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

@scabug
Copy link
Author

scabug commented May 3, 2012

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
Copy link
Author

scabug commented Nov 7, 2012

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
Copy link
Author

scabug commented Nov 7, 2012

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
Copy link
Author

scabug commented Nov 8, 2012

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")
                  ^

@scabug
Copy link
Author

scabug commented Jul 10, 2013

@adriaanm said:
Unassigning and rescheduling to M6 as previous deadline was missed.

@scabug scabug added this to the Backlog milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant