Union type found when inferring `Array.empty`

[felixmulder]

import java.io.File

object Test {
  Some(new File("."))
    .map(_.listFiles).getOrElse(Array.empty)
    .map(_.listFiles)
}

Error message:

value `map` is not a member of Array[java.io.File] | Array[T]
where:    T is a type variable which is an alias of Array[T]

[smarter]

By just doing:

object Test {
  val x: Option[Array[Int]] = ???
  x.getOrElse(Array.empty)
}

You can see that something goes terribly wrong in typer:

package <empty> {
  final lazy module val Test: Test$ = new Test$()
  final module class Test$() extends Object() { this: Test.type => 
    val x: Option[Array[Int]] = ???
    Test.x.getOrElse[
      (Array[Int] | 
        Array[Array[Array[Array[Array[Array[Array[Nothing]^]^]^]^]^]^]
      )^
    ](
      Array.empty[Array[Array[Array[Array[Array[Array[Nothing]^]^]^]^]^]^](
        arrayTag[Array[Array[Array[Array[Array[Nothing]^]^]^]^]^](
          arrayTag[Array[Array[Array[Array[Nothing]^]^]^]^](
            arrayTag[Array[Array[Array[Nothing]^]^]^](
              arrayTag[Array[Array[Nothing]^]^](
                arrayTag[Array[Nothing]^](
                  arrayTag[Nothing^](
                    scala.reflect.ClassTag.apply[Nothing^](
                      classOf[class Nothing]
                    )
                  )
                )
              )
            )
          )
        )
      )
    )
  }
}

[odersky]

After analyzing this a bit, I found that there are several things that go wrong, and they all have to do with implicit search.

We need to do an implicit search for the ClassTag of Array.empty. The expected type
of Array.empty turns out to be a type variable B? >: Array[Int]. That type variable is not
instantiated. So we cannot derive an expected type for the ClassTag from it. In other words, we search for a ClassTag[T] where T is unspecified.

What happens next is that implicit search will first consider arrayTag (because it is in scope, imported from Predef, whereas class tags are only synthesized by compiler magic if this fails).
ArrayTag needs a classtag for the element type, so the same scenario plays out again. After having done this 5 times, the divergence check kicks in and realizes that we are on a divergent path for
the 6th instance. So we get a local failure. Now we fall back to the class tag materialization and
synthesize a ClassTag[Nothing]. But since this is done 5 levels down the overall result
is a

 arrayTag[arrayTag[arrayTag[arrayTag[arrayTag[ClassTag(Predef.classOf[Nothing])]]]]]

Summarizing, we get several things which are problematic

• When hitting a divergent expansion, we fall back to try something else only once we have exhausted the limit of 5 free tries. We should try to roll back to the root of the divergent expansion. Note that scalac is even more drastic: A divergent expansion is a global failure; no alternatives are tried at all. This causes some of the errors in the generic code of Improvements to implicits #1918 wgere scalac fails with divergent errors whereas dotty handles this OK.

• dotty is less eager than scalac when it comes to instantiating type variables. This is usually good since we keep more options open, but can be bad for implicit search. In particular, it makes no sense to search for ClassTag[T] if T is not determined at toplevel. We might be able to fix that with special logic for ClassTag, but potential problems remain for other user-defined cases as well.