Urgent need for improved equality in IArray (Scala 3) - Case Class Incompatibility

Scala Improvement Process
1

There is a critical issue with IArray’s equality behavior that significantly impacts its usability, particularly within case classes. The default reference equality, even for single-dimensional arrays, violates core immutability principles and breaches the expected promise of value-based equality in Scala.

When IArray is used as a field in a case class, the automatically generated equals method compares references instead of content, leading to unexpected inequality for case class instances with identical IArray values. This directly contradicts the expected behavior of case classes and immutable data structures.

Workarounds, such as encapsulating the IArray instance in a custom wrapper class for consistent equality, introduce significant overhead, negating the performance benefits of IArray. This effectively renders IArray less useful, especially when compared to controlled mutable array encapsulation, which could be more efficient in certain scenarios.

Therefore, i urgently request improvements to IArray’s equality, ideally through value-based equality by default or a robust mechanism for customizable equality checks. This is essential to ensure IArray fulfills its intended purpose as a reliable, predictable, and efficient immutable data structure in Scala 3, and to restore consistency with case class equality expectations.

1 Like
2

What you’re asking for is not possible. If it were, it would have been done already.

Either you get the nice equality, or you get the zero-overhead API over an Array. You cannot get both. Adding the expected equality would require a non-zero-overhead wrapper.

2 Likes
3

Couldn’t just the generated equals method of the case class change so that if the field is an IArray compare its values instead of the references?

I think that’s what’s he asking for, a change to the generated method, not to IArray

Or at least, I think that’s what he needs. If he were to compare two IArrays directly, he can always compare them by value in some other way, the equality problem only arises in case classes

4

That would create an inconsistency at the case class level. Now == on case classes wouldn’t be equivalent to == pairwise on their fields.

4 Likes
5

What with case class Foo[A](field: A); Foo(IArray(1,2,3))? Or with collections that can contain an IArray? Even if the scala compiler would rewrite all equality checks to see if there’s no IArray involved, there are equality checks that the compiler can’t reach, e.g. in Java collections.

3 Likes
6

I see, both of your answers are really good. Well, I guess I just want to comment that we run in this problem regularly in the business applications at my company. Though, the way we work around it is by creating a trait such as:

trait ProductWithArrays extends Product {

  override def equals(other: Any): Boolean = {
    other match {
      case assignableModel: ProductWithArrays if assignableModel.getClass.isAssignableFrom(this.getClass) =>
        val myProducts     = this.productIterator
        val otherProducts  = assignableModel.productIterator
        val zippedProducts = myProducts.zip(otherProducts)
        zippedProducts.forall {
          case (myProductValue: Array[_], otherProductValue: Array[_]) =>
            myProductValue.sameElements(otherProductValue)
          case (myProductValue, otherProductValue) => myProductValue == otherProductValue
        }
      case _ => false
    }
  }

}

And then mix in this trait in any case classes that will have Arrays in them. Of course not the cleanest way but it’s how we work around it in the cases were using Array as the collection is the only option.

1 Like
7

Won’t this issue be resolved once Java ships Value-based classes from Project Valhalla? You would be able to write your own array wrapper which overrides the Object#equals method with minimal runtime overhead. Following the examples from JEP 401 you’d get something like:

public value class MyIArray<T> {
     private final T[] arr;
     public MyIArray(T[] elements) { this.arr = java.util.Objects.requireNonNull(elements); }

     @Override public boolean equals(Object o) { return o instanceof MyIArray that && java.util.Arrays.equals(this.arr, that.arr); }
     @Override public int hashCode() { return java.util.Objects.hash(arr); }

     public int length() { return arr.length; }
     public T apply(int index) { return arr[index]; }
}
1 Like
8

In the meantime, an Immutable Object like IArray that breaks Immutability contract should not exist in a such form. And if it exists, at least It should come with a mandatory equality function to be injected at its construction in order to avoid misleading developpers. Any consideration on potential overhead in order to fix this issue might be a branch of the root of all evil.

9

IArray is just an opaque type on Array to hide the mutating functions. Scala has no power to change IArray at runtime as at runtime it’s the same type as Array. You’d need to do the change at the JVM level if you wanted to change how Arrays compare, and it would likely break a lot of existing code.

If you want an immutable collection backed by an array that has a sane equality function, why not use ArraySeq instead?

8 Likes
10

That is great question !

And there is a very simple answer:

Because I got misleaded by IArray, that was supposed to be an immutable data structure backed by an array, and did not expect as an API consumer that kind of glitch with it. And if I got misleaded by it, others would, for sure.
API consumer should not be forced to know the underlying implementation in general, and for a data structure that claims to be an immutable data structure, there is in Scala an history and a context that let the user to expect it wont break the immutability contract.

This glitch was not documented enough in the API or the documentation.
I believe, “fake” immutable object like IArray should not be called an Immutable object as long as they breach immutability contract, but rather readOnlyObject, in order to distinct between the two.
This naming convention would be clearer, once explicited.

Obviously the aim is to mimimize that kind of read only entity, and to maximise the number of true immutable entities.

Regarding IArray implementation, here is a question from me:

Wouldn’t be possible to prevent the equality glitch by letting the user to provide an Equality function or/and a HashCode function at initialization, like one can provide an Ordering function at a SortedMap initialization ?

And if this parameter was to be made mandatory, it would be safer, since it will bring the focus on the user that something has to be done regarding equality.

This way, the user would be responsible to keep the immutability contract alive, until JVM evolutions would allow better design.

11

I think you are still misunderstanding how IArray works under the hood. In short, it does not exist at runtime and is equivalent to an Array. It is not possible to override the hashCode and equals functions as IArray is just a type alias that hides the mutating functions of Array.

You can provide an ordering to a SortedMap because that sorted map exists at runtime. An IArray does not exist at runtime. Now, could you wrap IArray in a class, so that equality and hashCode could be overridden? You probably could. Personally I believe that many of the advantages of IArray would be lost if you did that, and would want a replacement for IArray. It would be a binary incompatible change, so it’s also a bit late now, but in theory you could. In fact, such a class already exists in the standard library, called ArraySeq.

I feel the docs also makes it clear that IArrays are backed by Array.

An IArray[T] has the same representation as an Array[T], but it cannot be updated.

12

More broadly, I think you’re mixing immutability and structural equality. There’s nothing fundamentally wrong about an immutable data type not having structural equality. Many languages have those.

It is also possible for mutable data structures to have structural equality (mutable Seqs have that in Scala), though that is more debatable, and not widely accepted across languages.

2 Likes
13

There’s a key question underlying all of this: why are you using IArray?

Keep in mind, it’s not used all that much in normal Scala programming. I believe I’ve literally never used it, in a dozen years of full-time Scala.

Precisely because of its inherent inconsistencies, it’s not really idiomatic Scala. It exists because it’s a necessary compromise under some circumstances. But yes, it’s fundamentally kind of messy – something to be used when you need it (due to specific API or performance requirements), not a type to focus on routinely, and it needs to be used with care.

1 Like
14

IArray is Scala 3 only, so it would not be idiomatic in Scala 2 :wink:

I agree there is an inconsistency between equality of mutable collections and equality of arrays. We inherited the array behavior from Java. There’s nothing we can do about that except not using arrays in unwrapped form. As others have noted, wrapped arrays with structural equality already exist, that’s just ArraySeq.

8 Likes
15

I guess this thread should be requalified as a language design matter.

For me, there is a flaw in IArray that could mislead the average user.

I do understand IArray uses Opaque types in order to achieve the read only feature.

I am relatively new to Scala 3 and not familiar enough with Opaque types, even if it looks very interesting, since it looks like compile-time-implicits.

Knowing the fact that IArray use Opaque types and that Opaque types can have extensions, wouldn’t be possible to use an extension for handling an Equality function that would have been defined at the definition of an IArray instance ?

16

As all issues that end with “That’s what the tradeoff was”, I think this issue should not be seen as resolved, but instead at pointing us to the need of better documentation:
https://www.scala-lang.org/api/3.3.3/scala/IArray$.html

An immutable array. An IArray[T] has the same representation as an Array[T], but it cannot be updated. Unlike regular arrays, immutable arrays are covariant.

On top of that here’s the text for it’s equals method:

Compare two arrays per element.

With no mention of eq or == anywhere on the page !

4 Likes
17

It’s important to note that extension functions don’t give the same amount power that normal methods in a class.

Methods in a class can be overridden, while extension functions can not. Extension functions also cannot override existing methods either.

An extension function like this

object IArrayExt1:
  extension [A](arr: IArray[A]) def equals(other: AnyRef): Boolean = ???

is fundamentally the same as this

object IArrayExt2:
  def equals[A](arr: IArray[A])(other: AnyRef): Boolean = ???

In fact, this is valid Scala code IArrayExt1.equals(myIArray)(myOtherIArray). What extension does is that is allows you to also call the above like this myIArray.equals(myOtherIArray).

So far we have defined two equals function. However, neither of them override the equals function found on Object/AnyRef, which is what is used by the standard library to determine of two things are equal.

Now, you are not always forced to use the JVM’s equal function. In your own functions you could take in a typeclass encoding equality. You could roll your own or go with cats’s Eq for example.

If you wanted to roll your own, you can use extension methods in your typeclass to be able to call your new equality as if it was a property of the object.

trait Eq[A]:
  extension (a: A) def ===(b: A): Boolean
object Eq:
  given Eq[Int] with
    extension (a: Int) def ===(b: Int): Boolean = a == b

  given [A: Eq]: Eq[IArray[A]] with
    extension (as: IArray[A]) def ===(bs: IArray[A]) = as.length == bs.length == as.zip(bs).forall((a, b) => a === b)

import Eq.given

IArray(5, 3) === IArray(5, 3) //true
IArray(5, 3) === IArray(5, 4) //false
1 Like
18

I believe the problem comes from the current implementation of IArray.equals:

/** Compare two arrays per element.
   *
   *  A more efficient version of `xs.sameElements(ys)`.
   *
   *  @param xs an array of AnyRef
   *  @param ys an array of AnyRef
   *  @return true if corresponding elements are equal
   */
   def equals(xs: IArray[AnyRef], ys: IArray[AnyRef]): Boolean =
    Array.equals(xs.asInstanceOf[Array[AnyRef]], ys.asInstanceOf[Array[AnyRef]])

The underlying implementation of Array.equals that is used in it should be checked again.
I have written below an example that explains how this problem could be corrected and how to reproduce it:

object ImmutableArray {

  type ImmutableArray[Any] = IArray[Any]

  def apply(mutableArray: Array[Any]): ImmutableArray[Any] = IArray.from(mutableArray)

  extension (ia: ImmutableArray[Any]) def underlying: Array[Any] = ia.asInstanceOf[Array[Any]]  

  def equals(left: ImmutableArray[Any], right: ImmutableArray[Any]): Boolean = {
    java.util.Arrays.equals(left.underlying, right.underlying)
  }

  def main(args: Array[String]): Unit = {

    {
      val ia1 = ImmutableArray(Array(1, 2, 3, 4))
      val ia2 = ImmutableArray(Array(1, 2, 3, 4))
      val ia3 = ImmutableArray(Array(1, 2, 3, 4, 5))

      assert(ImmutableArray.equals(ia1, ia2) == true)
      assert(ImmutableArray.equals(ia2, ia1) == true)

      assert(ImmutableArray.equals(ia1, ia3) == false)
      assert(ImmutableArray.equals(ia3, ia1) == false)

      assert(ImmutableArray.equals(ia2, ia3) == false)
      assert(ImmutableArray.equals(ia3, ia2) == false)
    }

    {
      val ia1 = IArray(Array(1, 2, 3, 4))
      val ia2 = IArray(Array(1, 2, 3, 4))
      val ia3 = IArray(Array(1, 2, 3, 4, 5))

      assert(IArray.equals(ia1, ia2) == true) // will fail
      assert(IArray.equals(ia2, ia1) == true) // will fail

      assert(IArray.equals(ia1, ia3) == false)
      assert(IArray.equals(ia3, ia1) == false)

      assert(IArray.equals(ia2, ia3) == false)
      assert(IArray.equals(ia3, ia2) == false)
    }    

  }

}
19

The previous example was a trivial one since in real life one would rather use java.util.Arrays.deepEquals for nested arrays

object ImmutableArray {

  type ImmutableArray[Any] = IArray[Any]

  def apply(mutableArray: Array[Any]): ImmutableArray[Any] = IArray.from(mutableArray)

  extension (ia: ImmutableArray[Any]) def underlying: Array[Any] = ia.asInstanceOf[Array[Any]]

  def equals(left: ImmutableArray[Any], right: ImmutableArray[Any]): Boolean = {
    java.util.Arrays.deepEquals(left.underlying, right.underlying)
  }

  def main(args: Array[String]): Unit = {

    val ia1 = ImmutableArray(Array(1, 2, 3))
    val ia2 = ImmutableArray(Array(1, 2, 3))
    val ia3 = ImmutableArray(Array(1, 2, 3, 4))

    assert(ImmutableArray.equals(ia1, ia2) == true)
    assert(ImmutableArray.equals(ia2, ia3) == false)
    assert(ImmutableArray.equals(ia1, ia3) == false)

    val nia1 = ImmutableArray(
      Array(
        ImmutableArray(Array(1, 2, 3)),
        ImmutableArray(Array(4, 5, 6)),
        ImmutableArray(Array(7, 8, 9))
      )
    )

    val nia2 = ImmutableArray(
      Array(
        ImmutableArray(Array(1, 2, 3)),
        ImmutableArray(Array(4, 5, 6)),
        ImmutableArray(Array(7, 8, 9))
      )
    )

    val nia3 = ImmutableArray(
      Array(
        ImmutableArray(Array(1, 2, 0)),
        ImmutableArray(Array(4, 0, 6)),
        ImmutableArray(Array(0, 8, 9))
      )
    )

    assert(ImmutableArray.equals(nia1, nia2) == true)
    assert(ImmutableArray.equals(nia2, nia3) == false)
    assert(ImmutableArray.equals(nia1, nia3) == false)

  }

}
20

First of, I believe Array.equals/IArray.equals is sort of tangential to the rest of the discussion. I do not believe this function is used that much in traditional Scala code. Specifically, it is not used when you do Array(a, b, c) == Array(a, b, c), and as such, it is also not used by case classes when checking their equality.

Next, your comparison between ImmutableArray and IArray are different. In the underlying representation you have Array(1, 2, 3, 4) for ImmutableArray, but Array(Array(1, 2, 3, 4)) for your IArray comparison. Changing the apply function constructing your ImmutableArray to wrap the Array like IArray.apply does like this, I get the exact same error for ImmutableArray.

  def apply(mutableArray: Array[Any]): ImmutableArray[Any] = IArray(mutableArray)

You next say that in real like you would want to use deepEquals anyway. Maybe you would, maybe you wouldn’t. I think saying you would always want to use deepEquals is reductive. It wouldn’t surprise me if java.util.Arrays.equals is faster than both java.util.Arrays.deepEquals or scala.Array.equals. Furthermore, again, it wouldn’t surprise me in scala.Array.equals is faster than java.util.Arrays.deepEquals. Would I welcome a scala.Array.deepEquals function? Yes, definetively. Would I want to replace that with scala.Array.equals? No, definetively not.