infertc.scala

/** This should properly be a 'pos' test - all of it should compile.
 *  As usual it's in neg so as to alert the media if the behavior changes.
 */

package p1 {
  trait Foo[+A]
  trait Bar[+A] extends Foo[A]
  class Good() extends Foo[Int] // directly inherits Foo[Int]
  class Bad() extends Bar[Int]  // indirectly inherits Foo[Int]

  class A {
    trait Imp[+A]
    implicit object intImp extends Imp[Foo[Int]]
  }

  class ReprTest extends A {
    // If the method doesn't decompose the incoming type into type constructor and
    // type argument, then it will infer the type which has no visible type arg and
    // always fail to find the implicit.
    def f[Repr](xs: Repr)(implicit ob: Imp[Repr]) = null

    f(new Bad())                         // fail - could not find Imp[Bad]
    f(new Bad(): Bar[Int] with Foo[Int]) // fail - could not find Imp[Bar[Int] with Foo[Int]]
    f(new Bad(): Foo[Int] with Bar[Int]) // fail - could not find Imp[Foo[Int] with Bar[Int]]
    f(new Bad(): Bar[Int])               // fail - could not find Imp[Bar[Int]]
    f(new Bad(): Foo[Int])               // ok

    f(new Good())                        // fail - could not find Imp[Good]
    f(new Good(): Foo[Int])              // ok
  }

  class GenericTest extends A {
    // If the method does decompose, then it will find an implicit if there
    // is one corresponding to the first parent encountered with the right arity.
    // All other base types are ignored. Notice it finds the implicit if the
    // type is ascribed "Foo[Int] with Bar[Int]" but not the other way around.
    // This is (apparently) because type constructor inference stops as soon
    // as it finds a plausible parent, even if there are other equally plausible
    // immediate parents.
    //
    // It's especially bizarre in this case because Bar[Int] extends Foo[Int]
    // so it will always precede Foo in the linearization - but by ascribing
    // the type as Foo[Int] with Bar[Int], Foo can stick its head out long enough
    // for the implicit to be discovered.
    def f[A, CC[X]](xs: CC[A])(implicit ob: Imp[CC[A]]) = null

    f(new Bad())                         // fail - could not find Imp[Bar[Int]]
    f(new Bad(): Bar[Int] with Foo[Int]) // fail - could not find Imp[Bar[Int]]
    f(new Bad(): Foo[Int] with Bar[Int]) // ok
    f(new Bad(): Bar[Int])               // fail - could not find Imp[Bar[Int]]
    f(new Bad(): Foo[Int])               // ok

    f(new Good())                        // ok
    f(new Good(): Foo[Int])              // ok
  }
}

/** An alternate universe where Foo and Bar have no subclass relationship.
 *  Consider the impact on one's ability to reason about code when any
 *  detail of the linearization may have such far-reaching impact.
 */
package p2 {
  trait Foo[+A]
  trait Bar[+A]
  class Good() extends Foo[Int]                // Foo[Int] is only parent
  class Bad1() extends Foo[Int] with Bar[Int]  // Bar[Int] later than Foo[Int]
  class Bad2() extends Bar[Int] with Foo[Int]  // Foo[Int] later than Bar[Int]

  class A {
    trait Imp[+A]
    implicit object intImp extends Imp[Foo[Int]]
  }
  // Poor Bad2 fails without ascription despite having Foo[Int] as a direct parent
  class GenericTest extends A {
    def f[A, CC[X]](xs: CC[A])(implicit ob: Imp[CC[A]]) = null

    f(new Bad1())                         // ok
    f(new Bad1(): Bar[Int] with Foo[Int]) // fail - could not find Imp[Bar[Int]]
    f(new Bad1(): Foo[Int] with Bar[Int]) // ok
    f(new Bad1(): Bar[Int])               // fail - could not find Imp[Bar[Int]]
    f(new Bad1(): Foo[Int])               // ok

    f(new Bad2())                         // fail - could not find Imp[Bar[Int]]
    f(new Bad2(): Bar[Int] with Foo[Int]) // fail - could not find Imp[Bar[Int]]
    f(new Bad2(): Foo[Int] with Bar[Int]) // ok
    f(new Bad2(): Bar[Int])               // fail - could not find Imp[Bar[Int]]
    f(new Bad2(): Foo[Int])               // ok
  }
}

Related bugs, for those after context:

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

And, sort of related:

https://issues.scala-lang.org/browse/SI-2712

I'm pretty sure that backtracking our way up the base types to find a type constructor that fits the bill (ie has implicit witnesses available) is likely to be super expensive.

I think that in practical terms you can't have all three from 1) type constructor polymorphism, 2) tcpoly inference, and 3) subtyping. Scala concedes 2.

BTW, I was also pretty suprised when I saw that tcoply unification proceeds in parents order rather than linearization order. That's why the addition of AbstractSeq changed inference.

Looks like you and @adriaanm cooked that up back in:

scala/scala@683af58#diff-af14896ae025c1c3aa1bab7745fa01dcR2392

Innocent victim here. I was pretty surprised too.