`scala.collection.immutable.HashSet.subsetOf` can throw an error on valid data in 2.13

[Prometheus3375]

Reproduction steps

Scala version: 2.13.12

There are 4 tuples of sets to identify whether the 1st one is a subset of the second.

import scala.collection.immutable.HashSet

val set_tuples = Seq(
  (HashSet("ian", "cra"), HashSet("john", "michael", "mills")),
  (HashSet("ian", "cras"), HashSet("john", "michael", "mills")),
  (HashSet("ian", "crasto"), HashSet("john", "michael", "mills")),
  (HashSet("ian", "craston"), HashSet("john", "michael", "mills")),
  )

set_tuples.foreach(tuple => {
    val s1 = tuple._1
    val s2 = tuple._2
    try {
      val result = s1.subsetOf(s2)
      println(s"Result is $result for $s1 <= $s2")
    } catch {
      case _: ClassCastException => println(s"Class cast exception for $s1 <= $s2")
      case exc: Throwable => println(s"Exception $exc for $s1 <= $s2")
    }
  }
)

Expected behavior

For all 4 tuples the result should be false.

Actual behavior

Result is false for HashSet(cra, ian) <= HashSet(michael, john, mills)
Class cast exception for HashSet(cras, ian) <= HashSet(michael, john, mills)
Result is false for HashSet(ian, crasto) <= HashSet(michael, john, mills)
Class cast exception for HashSet(craston, ian) <= HashSet(michael, john, mills)

Exceptions for tuples 2 and 4.

Additional information

For Scala version 2.12.18.

Result is false for Set(cra, ian) <= Set(michael, john, mills)
Result is false for Set(cras, ian) <= Set(michael, john, mills)
Result is false for Set(ian, crasto) <= Set(michael, john, mills)
Result is false for Set(craston, ian) <= Set(michael, john, mills)

[som-snytt]

scala> val hs = HS("hi")
val hs: scala.collection.immutable.HashSet[String] = HashSet(hi)

scala> val empty = HS.empty[String]
val empty: scala.collection.immutable.HashSet[String] = HashSet()

scala> hs.subsetOf(empty)
val res2: Boolean = true

This is why I never use booleans. I'd rather flip a coin, because then at least I have a coin.

Also it would be nice to have a REPL that prints strings in quotes.

[SethTisue]

@scala/collections

[som-snytt]

Taking a look, in subsetOf there is no NxD case. Adding that (which results in false, we have more than one element where the other set has exactly one) fixes the symptom. Additionally, the failing data is a root with subnode, which breaks the invariant arity > 1. (arity is data elements + subnodes) Looking at construction now. I'll PR in a bit.

[SethTisue]

is it 2.13 specific?

[som-snytt]

@SethTisue yes. 2.13 collections rewrite plus CHAMP. The underused pun is "CHAMPing at the bit".

[SethTisue]

🎵 We are the CHAMPions 🎵