Implicit lookup failure in return type aliases

[scabug]

For some reason, implicit lookup fails when type-alias is used in return types:

class ImplicitVsTypeAliasTezt {

    class Monad[m[_]] {
        type For[a] = _For[m, a]
        implicit def toFor[a](m: m[a]): For[a] = throw new Error("todo") // lookup fails
//        implicit def toFor[a](m: m[a]): _For[m, a] = throw new Error("todo") // fine.
    }

    trait _For[m[_], a] {
        def map[b](p: a => b): m[b]
    }

    def useMonad[m[_], a](m: m[a])(implicit i: Monad[m]): Unit = {
        import i._

        // value map is not a member of type parameter m[a]
        for {
            x <- m
        } yield x.toString
    }
}

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-5070?orig=1
Reporter: @okomok
Affected Versions: 2.9.1

[scabug]

@paulp said:
Boy, I was sure based on the description I would dash this one off in five seconds. No such luck.

[scabug]

@retronym said (edited on May 20, 2012 7:16:05 PM UTC):
Minimized some. Curious.

object ImplicitVsTypeAlias {

  trait For {
    val map = 0
  }

  type _For = For

  class M {
    type __For = For

    // 1.
    implicit def toFor: __For = ???

    // 2.
    // implicit def toFor: _For = ???
    // 3.
    // implicit def toFor: For = ???
  }

  def use1(m1: M) {
    import m1.toFor
    // Fails with 1, works with 2 and 3
    implicitly[{def map: Int}]

    // works with 1, 2 and 3.
    implicitly[For]
  }

  val m2: M = ???
  def use2 {
    import m2.toFor
    // works with 1, 2 and 3.
    implicitly[{def map: Int}]

    // works with 1, 2 and 3.
    implicitly[For]
  }
}

[scabug]

@retronym said (edited on May 20, 2012 8:41:41 PM UTC):
The bug is in Implicits#depoly. It uses ApproximateDependentMap to type to wildcard away dependent type prefixes based on parameter values. But it goes too far, and ends up converting the result type of toFor from:

=> m1.__For

to:

"=> ?#__For"

It only affects the use1, because of m's coincidental position in an enclosing parameter list.

This mapped type no longer conforms to the expected type, AnyRef{ def map: Int}.

How can we be more discriminating here? We only want to find types that are dependent on a method parameter in the method that provides the candiate implicit.

...

Oh, just found this:

    // more precise conceptually, but causes cyclic errors:    (paramss exists (_ contains sym))
    override def isImmediatelyDependent = (sym ne NoSymbol) && (sym.owner.isMethod && sym.isValueParameter)

[scabug]

@adriaanm said:
the cyclic errors may have resulted from other uses of the ApproximateDependentMap
maybe we could try using the more precise criterion in depoly?

[scabug]

@adriaanm said:
https://github.com/adriaanm/scala/tree/ticket-5070

[scabug]

@adriaanm said:
changing implicit resolution is too risky in a minor release

[scabug]

@retronym said (edited on Feb 21, 2015 3:41:57 AM UTC):
The overeager depoly is also to blame for this implicit search failure.

trait Web {
  type LocalName
}
trait Companion1[A]
trait WebDSL[W <: Web] {
  trait LocalNameCompanion extends Companion1[W#LocalName] {
    type A = String
  }
  implicit val LocalName: LocalNameCompanion
}
object Test {
  def t[W <: Web](implicit webDSL: WebDSL[W]): Unit = {
    import webDSL._
    implicitly[LocalNameCompanion] // succeeds
    implicitly[Companion1[W#LocalName]] // fails
  }
}

LocalName's type is incorrectly approximated to => ?#LocalNameCompanion, which does not conform to the expected type Companion1[W#LocalName]

As reported https://groups.google.com/forum/#!topic/scala-user/Wvh8q85gFAs

[scabug]

@odersky said:
I checked with dotc; it looks like it handles this case correctly.

[scabug]

@retronym said (edited on Feb 21, 2015 12:09:02 PM UTC):
@odersky However, you don't typecheck the program described in the comments of depoly. That comment was written by @adriaanm in scala/scala@e557acb9#diff-7c03397456d3b987549fd039d6b639c6R237

trait A {
  type T
}

object O {
  implicit def b(implicit x: A): x.T = error("")
}

class Test {
  import O._
  implicit val a: A = new A {}
  implicitly[a.T]       // works in scalac, not in dotty

  implicitly[a.T](b(a)) // works
}

% qscalac sandbox/test.scala
warning: there was one deprecation warning; re-run with -deprecation for details
one warning found

% ../dotty/bin/dotc sandbox/test.scala
sandbox/test.scala:12: error: no implicit argument of type Test.this.a.T found for parameter e of method implicitly in object Predef$
  implicitly[a.T]       // works in scalac, not in dotty
                 ^
one error found

With regards to the bugs above, my hunch is that scalac could be fixed by using a BoundedWildcardType in ApproximateDependentType, rather than a WildcardType.

[scabug]

@retronym said:
Forget that hunch.

This seems more promising: https://github.com/retronym/scala/compare/ticket/5070?expand=1

I think we can do better than:

    // more precise conceptually, but causes cyclic errors:    (paramss exists (_ contains sym))
    override def isImmediatelyDependent = (sym ne NoSymbol) && (sym.owner.isMethod && sym.isValueParameter)

.. from within implicit search, as we know the the current implicit method in question, and need only check that the type is not dependent on one of its parameters.