Why is Seq.containsSlice not type-safe?

Question

While debugging my program, I found that I had made the mistake of supplying the wrong argument to the containsSlice method of a Seq[Char]. I had supplied a Seq[Boolean] which is of course never contained in the Seq[Char].

Why did the compiler let me do this? Can't this method be implemented in a type-safe way in the Scala collections library? I think it must have been done deliberately to be able to supply a Seq[Any], which could theoretically be all Chars. But shouldn't the designers have kept this method type-safe and add some non-type-safe method like containsAnySlice?

EDIT: I've tried creating my own type-safe containsSlice method outside of the collection class hierarchy, but for some reason the code in the test method compiles while I had hoped it wouldn't:

object Seqs {
  def containsSlice[A, B <: A](s1: Seq[A], s2: Seq[B]): Boolean = {
    s1.containsSlice(s2)
  }
  def test = {
    val sc: Seq[Char] = Seq('A','B','C')
    val sb: Seq[Boolean] = Seq(true, false)
    containsSlice(sc, sb)
  }
}  

I guess this is because the common supertype of Char and Boolean (AnyVal) is inferred for type parameter A, and I need to explicitly call containsSlice[Char](sc, sb) if I don't want that (but then I could just use sc.containsSlice[Char](sb)).

To make it not compile for incompatible Seqs, the only way I could do this is use 2 parameter lists so the correct type gets inferred:

object Seqs {
  def containsSlice[A, B <: A](s1: Seq[A])(s2: Seq[B]): Boolean = {
    s1.containsSlice(s2)
  }
  def test = {
    val sc: Seq[Char] = Seq('A','B','C')
    val sb: Seq[Boolean] = Seq(true, false)
    containsSlice(sc)(sb) // does not compile, yay!
  }
}  

Answer 1

The problem is that Seq is declared to be covaraint in its type parameter: trait Seq[+A] this means that Seq[A] is a subclass of Seq[B] if A is a subclass of B. The parameter to containsSlice is naturally in a contra-variant position, which means that it CANNOT match the type parameter A, since A is already declared as covariant. Try writing this yourself:

trait MySeq[+A] {
  def containsSlice(as: Seq[A]): Boolean
}

The compiler will complain:

error: covariant type A occurs in contravariant position in type Seq[A] of value as
  def containsSlice(as: Seq[A]): Boolean
                    ^
one error found

And you can if you play around with this, how you cannot guarantee type safety anyway. Lets pretend that the compiler allowed this definition. In your example you had a Seq[Char]. Well because of the covariance of Seq, this should be allowed:

val myseq: Seq[Char] = List('a','b','c')
val anyseq: Seq[Any] = myseq

We are allowed to do this because Seq[Char] is a subtype of Seq[Any] since Char is a subtype of Any. Now, what is the type of containsSlice on anyseq? its Seq[Any] since the type parameter of Seq in our anyseq is Any, and thus your type safety is gone.

Answer 2

containsSlice is just a call to indexOfSlice, which has the following signature:

indexOfSlice[B >: A](that: GenSeq[B]): Int

containsSlice could do the same thing.

It's useful to constrain the type param with a lower bound so you can do this:

apm@mara:~/tmp$ scalam -Ywarn-infer-any 
Welcome to Scala version 2.11.0-M7 (OpenJDK 64-Bit Server VM, Java 1.7.0_25).
Type in expressions to have them evaluated.
Type :help for more information.

scala> "abcdef" contains 8
<console>:8: warning: a type was inferred to be `AnyVal`; this may indicate a programming error.
              "abcdef" contains 8
                                ^
res0: Boolean = false

The warning tells you that type safety has been compromised.

-Xlint includes -Ywarn-infer-any.

But check this out:

scala> "abcdef" indexOfSlice (1 to 10)
res1: Int = -1

No warning?

You can turn on the fancy new -Ytyper-debug to see:

|    |    |    |    |    \-> [B >: Char](that: scala.collection.GenSeq[B], from: Int)Int <and> [B >: Char](that: scala.collection.GenSeq[B])Int
|    |    |    |    solving for (B: ?B)

and

|    |    |    |    solving for (B: ?B)
|    |    |    |    \-> Int

which seems to mean that in the presence of overloading, you don't get the warning.

That's because of how typechecking is done for overloading.

-Xprint:typer confirms that, of course, you wind up with AnyVal, but it must happen later:

private[this] val res0: Int = scala.this.Predef.augmentString("abcdef").indexOfSlice[AnyVal](scala.this.Predef.intWrapper(1).to(10));

We didn't really need another reason that overloading is evil, but did you know that println is also evil?

scala> println("abcdef" contains 8)
false

No warning.

It turns out that the warning is very conservative:

  // Can warn about inferring Any/AnyVal as long as they don't appear
  // explicitly anywhere amongst the formal, argument, result, or expected type.

Since println takes Any, that is our expected type for the expression, and we lose the warning.

In summary,

import reflect.runtime._
import universe._

case class Foo[+A](a: A) {
  def f[B >: A : TypeTag](other: Foo[B]): String = typeTag[B].toString
  def g[B] = "huh"
  def j[B >: A : TypeTag](other: Foo[B]): String = typeTag[B].toString
  def j[B >: A : TypeTag](other: Foo[B], dummy: Int): String = typeTag[B].toString
}

object Test extends App {
  val x = Foo("abc") f Foo(3)       // warn
  val y = Foo("abc").g
  val w = Foo("abc") j Foo(3)       // nowarn
  val z = Foo("abc") j (Foo(3), 0)
  Console println s"$x $y $w $z"
  val b = "abcdef" contains 8       // warn
  println("abcdef" contains 8)      // nowarn

  implicit class Sectional[+A](val as: Seq[A]) {
    def containsSection[B >: A](other: Seq[B]): Boolean = as containsSlice other
  }
  ("abcdefg": Seq[Char]) containsSection (1 to 10)  // warn
  implicit class Sectional2(val as: String) {
    def containsSection[B >: String](other: Seq[B]): Boolean = as containsSlice other
  }
  "abcdefg" containsSection (1 to 10)  // warn
}

Too bad about special-casing String.