Help to understand which method is called

I have defined an ADT as follows:

sealed abstract class Bdd {}
sealed abstract class BddTerm extends Bdd {}
object BddTrue extends BddTerm {}
object BddFalse extends BddTerm {}

case class BddNode(label:Int, positive:Bdd, negative:Bdd) extends Bdd {
  // equals and hashCode methods copied from here:
  override def equals(that: Any): Boolean = {
    that match {
      case b: Bdd => this eq b
      case _ => false

  override def hashCode(): Int =

Now if I have a variable hash of type hashMap[(Bdd,Bdd),Bdd], then what does hash((b1,b2)) do? Does it matter whether b1 and b2 are declared as Bdd or as BddNode?

The reason I ask is that when I use VisualVM on my program, it spends a huge about of time in BddNode.equals. Whereas, I though it would spend hardly any time there. Have I defined my ADT with weird semantics, having equal on some classes but not on others?

You haven’t shown the hash method.

x.method(y) invokes method on object x, which means that method is looked up in the class of x. Type of y only matters if method is overloaded in class of x. Overloading is done statically (at compile time) so it doesn’t incur runtime cost.

In Scala world the type of reference doesn’t matter on method selection, i.e. it matters at compile time to decide whether code compiles, but runtime selection of method implementation is done using actual object class, not reference type. OTOH in Java world there are static methods that are resolved statically. Static methods also arent’ overridable or inheritable.

I think I understand, but let me ask redundantly just to be sure.

What does “class of x” mean? Do you mean the actually run-time class of the object x? Or do you mean the type declared for the variable x?

Also what does “type of reference” mean?

It is kind of weird.

First, #equals() should be symmetric - a == b should always yield the same result as b == a, but you’ll run into different implementations depending whether a is a BddNode and b is a BddTerm or vice versa - in the first case, “your” #equals() will be called, in the second case the default implementation.

However, second, you’ll “accidentally” get symmetric behavior in your code, because your #equals()/#hashCode() doesn’t change the semantics of the default implementations at all - they operate on object identity. Which means that

BddNode(1, BddTrue, BddFalse) != BddNode(1, BddTrue, BddFalse)
BddNode(1, BddTrue, BddFalse).hashCode() != BddNode(1, BddTrue, BddFalse).hashCode()

More gory details about #equals()/#hashCode() can be found in PinS.

val f: Foo = new Bar
                 ^ "class of f"
       ^ "type of reference"

More in PinS.

The purpose of my equals is just to prevent the contents from being examined when equals is called.

As I understand my code, only objects which are actually the same object will be equal. Otherwise the objects are not equal despite their having the same or different content. My application has a factor function used for creating Bdd objects which promise to always return identical objects when the content is the same. So Bdd(1,BddTrue,BddFalse) == Bdd(1,BddTrue,BddFalse) because Bdd will return the same pointer each time.

Is there a better way? I thought about just defining equals and hashCode to call this.super, but I didn’t try it. This ordinarily (in non-scala OO systems) but scala write an equal method for you unless you provide one yourself. Right?

But am I sure that the HashMap internal code respects these semantics?

case classes are used to implement data classes, and have some automatic helpers that give you equals, hashcode, apply, and unapply.

You don’t want that in your case. If you use a regular class for BddNode, then you get your implementation automatically.

sealed abstract class Bdd
sealed abstract class BddTerm extends Bdd
object BddTrue extends BddTerm
object BddFalse extends BddTerm
class BddNode(val label: Int, val positive: Bdd, val negative: Bdd) extends Bdd

Here’s a very simplified example on how method invocation works:

class A {
  override def equals(that: Any): Boolean = true

class B {
  // program works the same even if below code line is commented out
  override def equals(that: Any): Boolean = false

val a = new A
val b = new B

println(a.equals(b)) // prints: true
println(b.equals(a)) // prints: false

// upcasting to 'Object" doesn't change anything in the output
// because 'equals' method is non-static
// so the same method implementation will be invoked

val o1: Object = a
val o2: Object = b

println(o1.equals(o2)) // prints: true
println(o2.equals(o1)) // prints: false

equals is a method just like any other and follows the same rules. You don’t get automatic symmetry for any custom method implementation, so why equals should automatically get one?

== operator in Scala delegates to equals after checking for nulls. == operator in Java is equivalent to eq method in Scala. Default equals is equivalent to eq (except that equals can throw NullPointerException).

But then I won’t get pattern matching either. My applications uses pattern matching heavily on BddNode. Perhaps I want to avoid the case class, but instead write an unapply method?

Yes, adding an unapply method sound better than having a case class with reference based equality.

So the method which is called is always computed according to the runtime class of the value to the left of the dot. However, this is not the case for the rest of the method arguments. In CLOS the same rules apply to all the arguments, even the first (the object to the left of the dot, as there is no left-of-the-dot in CLOS).

class X {
  def m(x:X):Int = 1
class Y  extends X {
  override def m(x:X):Int = 2
  def m(y:Y):Int = 3

val x:X = new X
val y:Y = new Y
val z:X = new Y
  List(x.m(x), // 1
       x.m(y), // 1
       x.m(z)),  // 1
    y.m(x),  // 2
    y.m(y),  // 3 
    y.m(z)),  // 2, in CLOS this would be 3
    z.m(x), // 2
    z.m(y), // 2 --  I fail to understand why this returns 2, while y.m(y) returns 3
    z.m(z))) // 2 

If I change this to a non-case class but with an unapply method, then can I be sure that equivalence checking within hash lookups NEVER traverses the tree of objects? Something like hash.get((bdd1,bdd2)) or hash((bdd1,bdd2)) = bdd3, I never want that to descend the BddNode object stores in the instance variables of bdd1 and bdd2. And if I create a set Set(bdd1,bdd2) then the equivalence check never looks at the instance variables of bdd1 and bdd2 ?

If I am the only one calling ==, then I can of course just call eq instead. But the point of providing a protocol for the class is that other function (that I didn’t write) may call ==.

I think this is perfectly fine if you want case-class advantaces (pattern-matching, avoid new() etc.) but want “reference-equalty”. I’d write equals() as follows tho:

override def equals(that: Any): Boolean = this eq that

avoids pattern-matching preserving semantics.

1 Like

@andreak, I like your solution, but I seem to recall NOT using that because of something that I have now forgotten.

I think I need to test this in my code base.

It’s because eq is only available on AnyRef.

ahhh, so the suggestion of @andreak won’t work then?

Both the mutable and immutable HashMap in 2.12 and earlier perform equality checks once you hit the right hash bucket. The completely new implementations in 2.13 always compare the hashcodes first. This should lower the number of equality checks.

Is there a discussion of this 2.13 HashMap change somewhere where I can read more details?

Yes it will, with a minor addition:

override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef]

For every practical means this is sufficient.

what would be the semantics of this?

  override def equals(obj:Any):Boolean = {