Implicits resolution problem with collections

On Tue, Nov 29, 2011 at 3:00 PM, Stefan Zeiger <szeiger@novocode.com> wrote:

Hi,

I'm trying to make BitSets in the collections library sorted sets, so my (immutable) BitSet now extends SortedSet, BitSetLike extends SortedSetLike, and so on. Now I'm running into an ambiguous implicit error when compiling scala.util.automata.SubsetConstruction:

import scala.collection.{ mutable, immutable }

class SubsetConstruction[T <: AnyRef](val nfa: NondetWordAutom[T]) {
 import nfa.labels

 def selectTag(Q: immutable.BitSet, finals: Array[Int]) =
   Q map finals filter (_ > 0) min

[scalacfork]  both method newCanBuildFrom in class SortedSetFactory of type [A](implicit ord: Ordering[A])scala.collection.generic.CanBuildFrom[scala.collection.SortedSet.Coll,A,scala.collection.SortedSet[A]]
[scalacfork]  and method newCanBuildFrom in class SortedSetFactory of type [A](implicit ord: Ordering[A])scala.collection.generic.CanBuildFrom[scala.collection.immutable.SortedSet.Coll,A,scala.collection.immutable.SortedSet[A]]
[scalacfork]  match expected type scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,Int,That]
[scalacfork]     Q map finals filter (_ > 0) min
[scalacfork]       ^
[scalacfork] one error found

I don't understand what's going on here. immutable.BitSet.canBuildFrom is the right CBF to use (and importing it makes the code compile). It's looking for a CanBuildFrom[immutable.BitSet,Int,That], so how can any implicit in SortedSetFactory be more specific than the one in immutable.BitSet?

it looks like it's not even considering the latter one, based on the error message 

What am I missing?

maybe try compiling using -Ytyper-debug to see which implicits it's typing?
cheersadriaan 

On 2011-11-29 23:30, Adriaan Moors wrote:
> maybe try compiling using -Ytyper-debug to see which implicits it's
> typing?

OK, i compiled a simple object Test {
implicitly[CanBuildFrom[immutable.BitSet, Int, _]] } with that. I'm not
quite sure how to read the debug output but it looks like it's on track
at first (checking BitSet.canBuildFrom first, determining that the
resulting type is CanBuildFrom[BitSet,Int,BitSet]) but then abandons the
correct choice for some reason (falling back from BitSet to SortedSet):

infer implicit {
tree
scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]]
pt
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]
undetparams
}
new ImplicitSearch {
tree
scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]]
pt
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]
isView false
context0 Context(Test.@TypeApply
unit=Test.scala scope=499668036)
undetparams
}
typedImplicit0 {
info.name canBuildFrom
ptChecked true
pt
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]
orig info {
undetParams
info.pre scala.collection.immutable.BitSet.type
}
}
typedImplicit1 immutable.this.BitSet.canBuildFrom,
pt=scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
I
nt, _], from implicit canBuildFrom:=>
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,Int,scala.collection.immutable
.BitSet]
typed implicit immutable.this.BitSet.canBuildFrom:=>
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,Int
,scala.collection.immutable.BitSet],
pt=scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]
adapted implicit method
canBuildFrom:scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,Int,scala.collectio
n.immutable.BitSet] to
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]
typedImplicit0 {
info.name newCanBuildFrom
ptChecked true
pt
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]
orig info {
undetParams
info.pre scala.collection.immutable.SortedSet.type
}
}
typedImplicit1 immutable.this.SortedSet.newCanBuildFrom,
pt=scala.collection.generic.CanBuildFrom[scala.collection.immutable.Bit
Set, Int, _], from implicit newCanBuildFrom:[A](implicit ord:
Ordering[A])scala.collection.generic.CanBuildFrom[scala.collection.immutable.S
ortedSet.Coll,A,scala.collection.immutable.SortedSet[A]]
typed implicit
immutable.this.SortedSet.newCanBuildFrom:[A](implicit ord:
Ordering[A])scala.collection.generic.CanBuildFrom[scal
a.collection.immutable.SortedSet.Coll,A,scala.collection.immutable.SortedSet[A]],
pt=scala.collection.generic.CanBuildFrom[scala.collection.
immutable.BitSet, Int, _]
infer implicit {
tree immutable.this.SortedSet.newCanBuildFrom[Int]
pt Ordering[Int]
undetparams
}

Cheers,
Stefan

On 2011-11-30 10:42, Stefan Zeiger wrote:
> On 2011-11-29 23:30, Adriaan Moors wrote:
>> maybe try compiling using -Ytyper-debug to see which implicits it's
>> typing?
>
> OK, i compiled a simple object Test {
> implicitly[CanBuildFrom[immutable.BitSet, Int, _]] } with that. I'm
> not quite sure how to read the debug output but it looks like it's on
> track at first (checking BitSet.canBuildFrom first, determining that
> the resulting type is CanBuildFrom[BitSet,Int,BitSet]) but then
> abandons the correct choice for some reason (falling back from BitSet
> to SortedSet):

For comparison, if I import BitSet.canBuildFrom, it sticks with it:

infer implicit {
tree
scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]]
pt
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]
undetparams
}
new ImplicitSearch {
tree
scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]]
pt
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]
isView false
context0 Context(Test.@TypeApply
unit=Test.scala scope=1849580177)
undetparams
}
typedImplicit0 {
info.name canBuildFrom
ptChecked true
pt
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]
orig info {
undetParams
info.pre scala.collection.immutable.BitSet.type
}
}
typedImplicit1
collection.this.immutable.BitSet.canBuildFrom,
pt=scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _], from implicit canBuildFrom:=>
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,Int,scala.collection.immutable.BitSet]
typed implicit
collection.this.immutable.BitSet.canBuildFrom:=>
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,Int,scala.collection.immutable.BitSet],
pt=scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]
adapted implicit method
canBuildFrom:scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,Int,scala.collection.immutable.BitSet]
to
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]
Implicit search yielded:
SearchResult(collection.this.immutable.BitSet.canBuildFrom, )
typing
scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]](collection.this.immutable.BitSet.canBuildFrom): pt = ?:
undetparams=, implicitsEnabled=true, silent=false, context.owner=value

typed
scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]](collection.this.immutable.BitSet.canBuildFrom):
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]
adapted
scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]](collection.this.immutable.BitSet.canBuildFrom):
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,Int,_$1]
to ?,
adapted
scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _]]: (implicit e:
scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int,
_])scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,
Int, _] to ?,

this is probably due to overload resolution -- see isStrictlyMoreSpecific (uncomment the println to see the scores it computes) and isAsSpecificmy guess is the "lack" of polymorphism and argument list in bitset's canbuildfrom results in a lower "specificity score" for BitSet's canBuildFrom apologies for the terse explanation

On Wed, Nov 30, 2011 at 11:16 AM, Stefan Zeiger <szeiger@novocode.com> wrote:

On 2011-11-30 10:42, Stefan Zeiger wrote:

On 2011-11-29 23:30, Adriaan Moors wrote:

maybe try compiling using -Ytyper-debug to see which implicits it's typing?

OK, i compiled a simple object Test { implicitly[CanBuildFrom[immutable.BitSet, Int, _]] } with that. I'm not quite sure how to read the debug output but it looks like it's on track at first (checking BitSet.canBuildFrom first, determining that the resulting type is CanBuildFrom[BitSet,Int,BitSet]) but then abandons the correct choice for some reason (falling back from BitSet to SortedSet):

For comparison, if I import BitSet.canBuildFrom, it sticks with it:

infer implicit {
 tree         scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _]]
 pt           scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _]
 undetparams
}
           new ImplicitSearch {
             tree         scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _]]
             pt           scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _]
             isView       false
             context0     Context(Test.<local Test>@TypeApply unit=Test.scala scope=1849580177)
             undetparams
           }
           typedImplicit0 {
             info.name  canBuildFrom
             ptChecked  true
             pt         scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _]
             orig       info {
               undetParams
               info.pre     scala.collection.immutable.BitSet.type
             }
           }
           typedImplicit1 collection.this.immutable.BitSet.canBuildFrom, pt=scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _], from implicit canBuildFrom:=> scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,Int,scala.collection.immutable.BitSet]
           typed implicit collection.this.immutable.BitSet.canBuildFrom:=> scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,Int,scala.collection.immutable.BitSet], pt=scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _]
           adapted implicit method canBuildFrom:scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,Int,scala.collection.immutable.BitSet] to scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _]
Implicit search yielded: SearchResult(collection.this.immutable.BitSet.canBuildFrom, )
               typing scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _]](collection.this.immutable.BitSet.canBuildFrom): pt = ?: undetparams=, implicitsEnabled=true, silent=false, context.owner=value <local Test>
               typed scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _]](collection.this.immutable.BitSet.canBuildFrom): scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _]
               adapted scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _]](collection.this.immutable.BitSet.canBuildFrom): scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet,Int,_$1] to ?,
           adapted scala.this.Predef.implicitly[scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _]]: (implicit e: scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _])scala.collection.generic.CanBuildFrom[scala.collection.immutable.BitSet, Int, _] to ?,

On 2011-11-30 11:38, Adriaan Moors wrote:

7f_pc5QE4AjqqgQ [at] mail [dot] gmail [dot] com" type="cite">this is probably due to overload resolution -- see isStrictlyMoreSpecific (uncomment the println to see the scores it computes) and isAsSpecific my guess is the "lack" of polymorphism and argument list in bitset's canbuildfrom results in a lower "specificity score" for BitSet's canBuildFrom apologies for the terse explanation

Thanks, that led me into the right direction. It turns out that isStrictlyMoreSpecific does not resolve this in the intuitively expected way. BitSet.canBuildFrom is not considered to be in a more specific subclass than (collection|mutable).SortedSet.newCanBuildFrom because the latter is inherited from SortedSetFactory (which the BitSet object cannot extend because that only works for sets which can take user-specified orderings).

I think the simplest solution (that avoids changing the implicit resolution in the compiler to take such transitive dependencies into account) is to override newCanBuildFrom in the SortedSet objects (delegating to super.newCanBuildFrom) and make the old canBuildFrom there non-implicit to avoid ambiguities.

-sz