the implicit arguments of implicit conversions do not guide type inference

[scabug]

object Test {
  class Rep[T](x : T)
 
  class SomeOps[T](x : Rep[T]) { def foo = 1 }
  implicit def mkOps[X, T](x : X)(implicit conv: X => Rep[T]) : SomeOps[T] = new SomeOps(conv(x))

  val a: Rep[Int] = error("")
  a.foo // infers mkOps(a).foo but rejects it because the types don't work out
// mkOps(a) will have type SomeOps[T] where T hasn't been instantiated because 
// the implicit search for mkOps's implicit argument hasn't been performed yet
}

relevant code from Implicits.scala

    /** The type parameters to instantiate */
    val undetParams = if (isView) List() else context.outer.undetparams // TODO: why the empty list for a view? why is this a val?

          if (itree2.tpe.isError) SearchFailure
          else if (hasMatchingSymbol(itree1)) {
            val tvars = undetParams map freshVar
            println("matchesPt??: "+(undetParams, context.undetparams, context.outer.undetparams)) // note that they are different!
            if (matchesPt(itree2.tpe /* itree2.tpe may contain typeparams from context.undetparams that will get instantiated later (during 2nd-order implicit search)*/, 
              pt.instantiateTypeParams(undetParams, tvars), undetParams)) {

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-3346?orig=1
Reporter: @adriaanm
Blocks #5592
Attachments:

• tvars.txt (created on Jan 12, 2012 5:52:53 PM UTC, 117455 bytes)

[scabug]

@adriaanm said:
(In r21692) see #3346: tentative fix that keeps type parameters in undetParams during and after implicit search

[scabug]

@adriaanm said:
in branch topic/embeddings

duplicate: #3270

[scabug]

@retronym said:
Is this the same problem:

http://gist.github.com/444680

I want one of the implicit conversions to be rejected as it results in a type that can't satisfy the context bound. But maybe I'm asking too much :)

This is the motivating example from Scalaz:

trait Identity[A] {
  def mapply[F[_], B](f: F[A => B])(implicit ftr: Functor[F]): F[B] = f ∘ (_(value))
}

scala> 1.mapply(Seq((_: Int) * 2))               
res5: Seq[Int] = List(2)

scala> 1.mapply[Identity, Int]((_: Int) * 2)
res6: scalaz.Identity[Int] = 2

scala> 1 mapply ((_: Int) * 2)              
<console>:12: error: type mismatch;
 found   : (Int) => Int
 required: ?F[ (Int) => ?B ]
Note that implicit conversions are not applicable because they are ambiguous:
 both method IdentityTo in trait Identitys of type [A](x: A)scalaz.Identity[A]
 and method any2ArrowAssoc in object Predef of type [A](x: A)ArrowAssoc[A]
 are possible conversion functions from (Int) => Int to ?F[ (Int) => ?B ]
       1 mapply ((_: Int) * 2)
         ^

[scabug]

@adriaanm said:
I haven't had time to try it yet, but here's my branch with the dependent method type refactoring + implicit search improvements: https://github.com/adriaanm/scala/tree/topic/retire_debruijn_depmet

[scabug]

@adriaanm said:
see also #3201

[scabug]

@adriaanm said:
{code}

[scabug]

@paulp said:
See also #4613.

[scabug]

@szeiger said:
This has been dormant for over a year now. Is there any chance of getting it into trunk for 2.10? I'm constantly running into this problem with the fundep-based type transformations in ScalaQuery, and in some cases there is no usable work-around available.

[scabug]

@retronym said:
Yeah, this would be really great for Scalaz7, as it would let us workaround #2712.

Here's how.

https://gist.github.com/1343005

[scabug]

maxime.levesque said:

This could be another incarnation of it :

http://gist.github.com/1405479

[scabug]

@adriaanm said:
another use case for this: toFM2 from http://ideone.com/ePUHG

I really want to fix this, but it's quite the tightrope walk over the jagged teeth of backwards compatibility, performance, and spec conformance.

[scabug]

@paulp said:
Hey, I was working on this this morning.

See attached by the way, look at all those typevars coming from those zipped functions. This seems bad performancewise.

[scabug]

@paulp said:
Oh, and that output is from compiling the code at the ideone.com link (after uncommenting the failing part.)

[scabug]

@milessabin said:
Another instance of the same problem reported here,

trait Foo[A]
implicit def fooString: Foo[String] = null

implicit def value[A](implicit foo: Foo[A]) = 5

implicitly[Int] // OK

Whereas ...

implicit def conversion[A](x: Int)(implicit foo: Foo[A]) = new {
  def aMethod = 5
}

1.aMethod       // Error: could not find implicit value for parameter foo: test.Foo[A]

[scabug]

@Blaisorblade said:
@adriaan Moors, the link you gave is no longer accessible:
https://github.com/adriaanm/scala/tree/topic/retire_debruijn_depmet

It seems that this branch (https://github.com/adriaanm/scala/tree/ticket/implicitly_depmet), the only one with a similar name, is quite unrelated.

And you write:

I really want to fix this, but it's quite the tightrope walk over the jagged teeth of backwards compatibility, performance, and spec conformance.
Is your prototyped fix available somewhere to understand the impact reconsider it? I guess/hope that at some point you're going to incorporate a rewrite of type inference, accept breaking some edge cases and change the spec?

[scabug]

@adriaanm said:
Paolo, sorry, hadn't seen this comment. I'm not sure anymore where I put these commits...
In any case, I'd still like to fix this, and yes, maybe break some edge cases.
I think it's going to have to be after 2.10.x, though.

[scabug]

@Blaisorblade said:
Well, good to know. Thanks for your answer!

[scabug]

@gkossakowski said:
Here's another instance of this problem: sbt/sbt#799

It leads to a very confusing error messages as demonstrated in sbt ticket.

[scabug]

@xeno-by said (edited on Jul 24, 2013 9:01:49 PM UTC):
I wonder whether something as simple as this could be a fix: scalamacros/kepler@54e9669. Let's see whether Jenkins agrees with me: https://scala-webapps.epfl.ch/jenkins/job/scala-checkin-manual/962/console.

Just for the record. Apart those scaladoc tests failing and blocking the build, we have only three failing tests in the main test suite, all coming from neg:

22:58 ~/Projects/Kepler_7692 (ticket/7692)$ t

Testing individual files
testing: [...]/files/neg/divergent-implicit.scala                     [FAILED]
testing: [...]/files/neg/t5578.scala                                  [FAILED]
--- divergent-implicit-neg.log
+++ divergent-implicit.check
@@ -9,10 +9,8 @@
                                     ^
-divergent-implicit.scala:14: error: type mismatch;
- found   : Test2.Foo
- required: Test2.Bar
+divergent-implicit.scala:14: error: diverging implicit expansion for type Test2.Baz => Test2.Bar
+starting with method baz2bar in object Test2
   val x: Bar = new Foo
                ^
-divergent-implicit.scala:15: error: type mismatch;
- found   : Test2.Baz
- required: Test2.Bar
+divergent-implicit.scala:15: error: diverging implicit expansion for type Test2.Foo => Test2.Bar
+starting with method foo2bar in object Test2
   val y: Bar = new Baz--- t5578-neg.log
+++ t5578.check
@@ -1,5 +1,2 @@
-t5578.scala:33: error: type mismatch;
- found   : NumericOpsExp.this.Plus[T]
- required: NumericOpsExp.this.Rep[T]
-    (which expands to)  NumericOpsExp.this.Exp[T]
+t5578.scala:33: error: No Manifest available for T.
   def plus[T: Numeric](x: Rep[T], y: Rep[T]): Rep[T] = Plus[T](x,y)
testing: [...]/files/neg/t5845.scala                                  [FAILED]

[scabug]

@paulp said:
It is inherent in the design of implicits that new implicits becoming eligible will break existing code, because the new implicits can introduce ambiguity in formerly working situations. For instance, here is a modified version of your submission in #7692 which compiles under current trunk. I assume this will stop compiling, possibly after modifying the implicit locations since I can't remember the specificity rules.

object Test extends App {
  trait Fundep[T, U]
  class C { def y = "x" }
  implicit val FundepStringC = new Fundep[String, C]{}
  implicit def foo[T, U](x: T)(implicit y: Fundep[T, U]): U = ???
  implicit def bar[T](x: T)(implicit y: Fundep[T, C]): C = ???
  println("x".y)
}

[scabug]

@xeno-by said (edited on Jul 24, 2013 9:15:36 PM UTC):
I agree, but the change looks to be valuable enough (e.g. solely from the feedback in this discussion thread). Do you think that justifies potential breakages?

Also, from what I can see, only a couple scaladoc tests + some neg tests have broken (of these only the divergence is arguable though making sense, the others just started working as they should), which gives hope that my provisional fix might need just a bit more polishing. What do you think? /cc @retronym @adriaanm.

[scabug]

@hubertp said:
From experience I can say that neg/divergent-implicit.scala ain't so easy to "just fix". As Paul noted any changes will need to be carefully reviewed because things will definitely break.

[scabug]

@paulp said:
"Do you think that justifies potential breakages?"

I no longer have an opinion on such tradeoffs.

[scabug]

@xeno-by said (edited on Jul 24, 2013 9:42:55 PM UTC):
@hubert I'm sorry if I seemed overeager. The right formulation would be "does the general approach outlined in the patch linked above look okay, or I'm overlooking something essential?".

The divergence test failure does make sense. Previously the offending views were selected by implicit search and then subsequent typechecking caused resolution of their implicit parameters, which led to divergence. Now divergence happens during implicit search, which simply invalidates given views and the error says "expected X, got Y" meaning that no suitable implicit conversions were found. At a glance this makes sense to me. Does it to you?

[scabug]

@Blaisorblade said:
Eugene, I'd like to offer a long +1 to (carefully reviewed) breaking changes here. I know you weren't asking me, but I think I can contribute my 2 cents here.

The following has some assumption on the change: it should make the actual Scalac behavior simpler to describe. Try documenting the current behavior (bugs included), try documenting the behavior with the patch, verify the latter is much simpler and actually understandable; in particular, the latter should be more declarative.

Because of such bugs, Scalac typechecker's behavior feels random. To see a discussion of them, look no further than this blog post:
http://yz.mit.edu/wp/true-scala-complexity/

(I also wonder whether something in there has to do with this bug, maybe seq2richseq? There's a comment from Adriaan Moors about another relation. But don't take me too seriously here, the details are a vague recollection from ages ago; my point is about why such bugs are bad).

Moreover, it seems that the code which will break is (arguably) buggy anyway, even though without a fixed Scalac this is probably hard to see.

And changes which fix implicit resolution and break code have gone in as late as 2.10 (IIRC). If wanted, one could support the transition somehow: make the new behavior optional and controlled by an option, or add a warning in 2.11 for code which will break (hard) and make the change for 2.12 (though I'd like things to go faster).

Overall, I think we need a way to fix bugs which make (buggy) code compile. C++ compilers often broke buggy code, I don't think Scala needs better bug-to-bug compatibility.

(Sorry for the length).

[scabug]

@xeno-by said:
scala/scala#2822

[scabug]

@xeno-by said:
scala/scala@210dbc7