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

Jump to bottom

"amb prefix" printed to stdout as the implicit scope excludes implicits in a companion available via two different prefixes #5340

Closed
scabug opened this issue Dec 27, 2011 · 4 comments
Closed

"amb prefix" printed to stdout as the implicit scope excludes implicits in a companion available via two different prefixes #5340

scabug opened this issue Dec 27, 2011 · 4 comments
Assignees
@milessabin
Labels
dependent types has PR implicit infer
Milestone
2.13.0-M3

Comments

@scabug
Copy link

scabug commented Dec 27, 2011 •
edited by retronym

In the context of a computer algebra project, implicits are used to implement automatic conversion (coercion) of polynomial coefficients to polynomials, as in x+1, with x = polynomial over the integers. The code below produces a strange error message in the standard output when compiled with scalac.

trait Ring {
  type E <: Element
  def zero: E
  trait Element {
    def +(that: E): E
  }
}

class Poly[C <: Ring](val ring: C) extends Ring {
  type E = Element
  def zero = apply(ring.zero)
  class Element(val value: ring.E) extends super.Element {
    def +(that: E) = apply(this.value+that.value)
    override def toString = value.toString
  }
  object Element {
    implicit def coef2poly[D <% ring.E](value: D) = apply(value)
  }
  def apply(value: ring.E): E = new Element(value)
}

object BigInt extends Ring {
  type E = Element
  def zero = apply(0)
  class Element(val value: Int) extends super.Element {
    def +(that: E) = apply(this.value+that.value)
    override def toString = value.toString
  }
  object Element {
    implicit def int2bigInt(value: Int) = apply(value)
  }
  def apply(value: Int): E = new Element(value)
}

object MyApp extends App {
  val r = new Poly(BigInt)
  val s = new Poly(r)
  val a = BigInt(1)
  val b = r(a)
  s.zero+a // works fine
  s.zero+b // compilation fails with error below
}

The error message:

amb prefix: MyApp.s.type#class Element MyApp.r.type#class Element
amb prefix: MyApp.s.type#class Element MyApp.r.type#class Element
amb prefix: MyApp.r.type#class Element MyApp.s.type#class Element
amb prefix: MyApp.r.type#class Element MyApp.s.type#class Element
MyApp.scala:6: error: type mismatch;
 found   : MyApp.r.E
 required: MyApp.s.E
  s.zero+b
         ^
one error found

The involved code is in scala/tools/nsc/typechecker/Implicits.scala

    /** Produce an implicict info map, i.e. a map from the class symbols C of all parts of this type to 
     *  the implicit infos in the companion objects of these class symbols C.
     * The parts of a type is the smallest set of types that contains
     *    - the type itself
     *    - the parts of its immediate components (prefix and argument)
     *    - the parts of its base types
     *    - for alias types and abstract types, we take instead the parts
     *    - of their upper bounds.
     *  @return For those parts that refer to classes with companion objects that
     *  can be accessed with unambiguous stable prefixes, the implicits infos
     *  which are members of these companion objects.
     */
    private def companionImplicitMap(tp: Type): InfoMap = {
        
      /** Populate implicit info map by traversing all parts of type `tp`.
       *  Parameters as for `getParts`.  
       */
      def getClassParts(tp: Type)(implicit infoMap: InfoMap, seen: mutable.Set[Type], pending: Set[Symbol]) = tp match {
        case TypeRef(pre, sym, args) =>
          infoMap get sym match {
            case Some(infos1) =>
              if (infos1.nonEmpty && !(pre =:= infos1.head.pre.prefix)) {
                println("amb prefix: "+pre+"#"+sym+" "+infos1.head.pre.prefix+"#"+sym)
                infoMap(sym) = List() // ambiguous prefix - ignore implicit members 
              }
            case None =>
@scabug
Copy link
Author

scabug commented Dec 27, 2011

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

@scabug
Copy link
Author

scabug commented May 8, 2012

@retronym said (edited on May 8, 2012 9:30:14 PM UTC):
Minimized further:

class Poly {
  class E
  object E {
    implicit def conv(value: Any): E = sys.error("")
  }
}

object MyApp {
  val r: Poly = sys.error("")
  val s: Poly = sys.error("")
  val b: r.E = sys.error("")

  // okay
  s.E.conv(b): s.E

  // compilation fails with error below
  println(b: s.E)

  // amb prefix: MyApp.s.type#class E MyApp.r.type#class E
  // amb prefix: MyApp.s.type#class E MyApp.r.type#class E
  // ../test/pending/run/t5310.scala:17: error: type mismatch;
  //  found   : MyApp.r.E
  //  required: MyApp.s.E
  //   println(b: s.E)
  //           ^
}

@scabug
Copy link
Author

scabug commented Jan 13, 2013

@retronym said:
scala/scala#1889

@scabug scabug closed this as completed Jan 14, 2013
@scabug scabug added this to the 2.10.1 milestone Apr 7, 2017
@scabug scabug mentioned this issue Apr 7, 2017
Closed
This was referenced Jul 24, 2017
Closed
Merged
@milessabin
Copy link

PR: scala/scala#6010

@milessabin milessabin modified the milestones: 2.13.0-M3, 2.10.1 Jul 27, 2017
retronym pushed a commit to retronym/scala that referenced this issue Jan 13, 2018
@milessabin @retronym
Fixes over aggressive pruning of implicit scope.
b3d4d01 
When the implicit scope is constructed an initial pruning phase attempts to
discard implicit members which it is believed would later be rejected as
ambiguous. Members of a companion are discarded if they can be reached via
more than one prefix, on the assumption that being visible via two or more
paths means that the multiple values must conflict with one another. However,
this does not take into account the possibility that the implicit members
might depend on the prefix in a way which renders them non-ambiguous. This
scenario is illustrated in scala/bug#4947 and
scala/bug#5340. This PR address that by only pruning
implicits which are independent of the prefix.

Whilst this PR tries to stay as close as possible to the current behaviour, I
believe that it would be desirable to drop the early pruning of even the
prefix-independent implicits. If we do that then we get improved error
messages reporting ambiguity rather the ambiguous members being silently
ignored which leads to otherwise unexplained failures of implicit resolution.
For instance in the case of `test/files/neg/t5340.scala` which currently
reports,

```
t5340.scala:15: error: type mismatch;
 found   : Quux[MyApp.r.E,MyApp.s.E]
 required: Int
  (new Quux[r.E, s.E]): Int // fails due to pre-stripping implicits which
   ^
one error found
```

we would get the following report,

```
t5340.scala:15: error: type mismatch;
 found   : Quux[MyApp.r.E,MyApp.s.E]
 required: Int
Note that implicit conversions are not applicable because they are ambiguous:
 both method conv in object E of type [T, U](b: Quux[T,U])Int
 and method conv in object E of type [T, U](b: Quux[T,U])Int
 are possible conversion functions from Quux[MyApp.r.E,MyApp.s.E] to Int
  (new Quux[r.E, s.E]): Int // fails due to pre-stripping implicits which
   ^
one error found
```

Which is clearly more informative (even if also a little baffling). I think
that ambiguity via multiple paths is sufficiently rare that the performance
benefits of this early pruning are likely to minimal and not enough to
outweigh improved error messages.

Because this change can result in a symbol _legitimately_ being revisited, via
a different prefix, we need to change the way that the a pruned path is
represented. Instead of using empty lists, as introduced in scala#5951 (which fixes
scala/bug#10081) we use explicit sentinels to mark
that a symbol has been visited at a given prefix yielding no additional
implicits. Testing this yielded scala/bug#10425
which appears to be a regression relative to 2.12.x. That's also fixed in this
PR.
milessabin added a commit to milessabin/scala that referenced this issue Jan 13, 2018
@milessabin
Fixes over aggressive pruning of implicit scope.
365acdb 
When the implicit scope is constructed an initial pruning phase attempts to
discard implicit members which it is believed would later be rejected as
ambiguous. Members of a companion are discarded if they can be reached via
more than one prefix, on the assumption that being visible via two or more
paths means that the multiple values must conflict with one another. However,
this does not take into account the possibility that the implicit members
might depend on the prefix in a way which renders them non-ambiguous. This
scenario is illustrated in scala/bug#4947 and
scala/bug#5340. This PR address that by only pruning
implicits which are independent of the prefix.

Whilst this PR tries to stay as close as possible to the current behaviour, I
believe that it would be desirable to drop the early pruning of even the
prefix-independent implicits. If we do that then we get improved error
messages reporting ambiguity rather the ambiguous members being silently
ignored which leads to otherwise unexplained failures of implicit resolution.
For instance in the case of `test/files/neg/t5340.scala` which currently
reports,

```
t5340.scala:15: error: type mismatch;
 found   : Quux[MyApp.r.E,MyApp.s.E]
 required: Int
  (new Quux[r.E, s.E]): Int // fails due to pre-stripping implicits which
   ^
one error found
```

we would get the following report,

```
t5340.scala:15: error: type mismatch;
 found   : Quux[MyApp.r.E,MyApp.s.E]
 required: Int
Note that implicit conversions are not applicable because they are ambiguous:
 both method conv in object E of type [T, U](b: Quux[T,U])Int
 and method conv in object E of type [T, U](b: Quux[T,U])Int
 are possible conversion functions from Quux[MyApp.r.E,MyApp.s.E] to Int
  (new Quux[r.E, s.E]): Int // fails due to pre-stripping implicits which
   ^
one error found
```

Which is clearly more informative (even if also a little baffling). I think
that ambiguity via multiple paths is sufficiently rare that the performance
benefits of this early pruning are likely to minimal and not enough to
outweigh improved error messages.

Because this change can result in a symbol _legitimately_ being revisited, via
a different prefix, we need to change the way that the a pruned path is
represented. Instead of using empty lists, as introduced in scala#5951 (which fixes
scala/bug#10081) we use explicit sentinels to mark
that a symbol has been visited at a given prefix yielding no additional
implicits. Testing this yielded scala/bug#10425
which appears to be a regression relative to 2.12.x. That's also fixed in this
PR.
@SethTisue SethTisue assigned milessabin and unassigned retronym Jan 23, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@milessabin milessabin

Labels
dependent types has PR implicit infer
Projects
None yet
Milestone
2.13.0-M3
Development

No branches or pull requests
3 participants
@retronym @milessabin @scabug