lub of abstract type member

[adriaanm-da]

This fails to type check (2.13.8) -- Scala 3.1.1 (correctly, IMO) accepts it:

object Tst {    
  type F[+A] <: A
  def mark[A](x: A): F[A] = ???

  class P
  class T[+x] extends P

  (if (???)  ??? : T[Nothing]
   else mark(??? : T[String])
  ): T[_] 
  /* found   : Tst.P
     required: Tst.T[_] */
}

scalac test.scala -Dscalac.debug.lub=1        
...
lub of List(Tst.T[Nothing], Tst.F[Tst.T[String]]) at depth Depth(3)
Frontier(
   (0)
        Tst.P
        Object
        Any

   (1)
        Tst.F[Tst.T[String]]
        Tst.T[String]
        Tst.P
        Object
        Any

)
** Depth is Depth(1)
T[Nothing] F[T[String]]
---------- ------------
P          F[T[String]]
Object     T[String]   
Any        P           
           Object      
           Any         
Frontier(
   (0)
        Tst.P
        Object
        Any

   (1)
        Tst.T[String]
        Tst.P
        Object
        Any

)
** Depth is Depth(2)
T[Nothing] F[T[String]]
---------- ------------
P          T[String]   
Object     P           
Any        Object      
           Any         
Frontier(
   (0)
        Tst.P
        Object
        Any

   (1)
        Tst.P
        Object
        Any

)
** Depth is Depth(3)
T[Nothing] F[T[String]]
---------- ------------
P          P           
Object     Object      
Any        Any         
** Depth is Depth(3)
T[Nothing] F[T[String]]
---------- ------------
lub of List(Tst.T[Nothing], Tst.F[Tst.T[String]]) is Tst.P

I would expect the lub of List(Tst.T[Nothing], Tst.F[Tst.T[String]]) to be Tst.T[String].

I added some logging to see what's going on, and this seems suspicious: minSym for List(Tst.T[Nothing], Tst.F[Tst.T[String]]): class T

I would expect the "minimal" symbol in this list to be F (as it's applied to T[String], which means it's bounded by T[String], which implies Tst.F[Tst.T[String]] should be less than Tst.T[String] (and Tst.T[Nothing]), but that gets lost because scalac gets the info for the symbol F, and doesn't apply it to the arguments in the type Tst.F[Tst.T[String]].

I couldn't look into this deeper, apologies for the handwavy diagnosis.

[joroKr21]

I guess by calling info you mean:

      def baseTypeSeqLength(sym: Symbol) =
        if (sym.isAbstractType) 1 + sym.info.upperBound.baseTypeSeq.length
        else sym.info.baseTypeSeq.length

[adriaanm-da]

Yep!

[adriaanm-da]

I should disclaim that I never fully internalized this symbol comparison logic and the way lub is built on top of it, so please take my analysis with the appropriate amount of salt.

[joroKr21]

I think the comment explains it:

A total ordering between symbols that refines the class inheritance graph (i.e. subclass.isLess(superclass) always holds). the ordering is given by: (.isType, -.baseTypeSeq.length) for type symbols, followed by id.

A subtype will always have a longer base type sequence - so it's a more efficient proxy to order symbols than checking for a subtype relationship. But clearly it breaks down for an applied abstract type.

[joroKr21]

So the solution in theory is simple enough - switch to comparing types instead of comparing symbols

[joroKr21]

Something like this:

/** A total ordering between symbols that refines the class
     *  inheritance graph (i.e. subclass.isLess(superclass) always holds).
     *  the ordering is given by: (_.isType, -_.baseTypeSeq.length) for type symbols, followed by `id`.
     */
    final def isLess(that: Symbol): Boolean = isLessBy(that) { sym =>
      if (sym.isAbstractType) 1 + sym.info.upperBound.baseTypeSeq.length
      else sym.info.baseTypeSeq.length
    }

    final def isLessBy(that: Symbol)(rank: Symbol => Int): Boolean =
      (this ne that) && {
        if (this.isType)
          that.isType && {
            val diff = rank(this) - rank(that)
            diff > 0 || diff == 0 && this.id < that.id
          }
        else
          that.isType || this.id < that.id
      }

And the in GlbLubs use the BTS that we already have for ranking

[adriaanm-da]

That makes sense to me. Since it works in Scala 3, I suggest taking a look at how it's implemented there.

[joroKr21]

Scala 3 has union types so I don't think the LUB can be simply backported

[adriaanm-da]

Good point -- I'm getting rusty :-)

[joroKr21]

@adriaanm-da I tried but a test fails and I don't understand why: scala/scala#9937