Messed up trait linearisation?

Question

Here is a trait linearisation puzzler that causes me headaches. I have basically type Node which defines equals and hashCode to be compared against other Nodes. And I have a Selector type which may wrap a Node along with extra data, and thus has its own equals and hashCode to be compared against other Selectors.

Now I have a Standalone type which combines Node and Selector, but I get inconsistent (?) linearisation with respect to equals and hashCode:

trait Selector { override def hashCode = 1 }
trait Event extends Selector

trait Node { override def hashCode = 2 }
trait Standalone extends Node with Event

Now all is fine (the more specific hashCode 1 is called) when I extend from either Event or Standalone:

object Single1 extends Event
Single1.hashCode // 1 -- ok

object Single2 extends Standalone
Single2.hashCode // 1 -- ok

It is also fine if I extend from both in this order:

object Compound1 extends Standalone with Event
Compound1.hashCode // 1 -- Ok

But it messes up when I do this:

object Compound2 extends Event with Standalone
Compound2.hashCode  // 2 -- no!!!!!!!!

I made a little .dot diagram (mixins are ordered from left-to-right):

enter image description here

So, if I understand linearisation rules correctly, I should always end up with the hashCode implemented by Selector. The only explanation for this behaviour would be that there is some sort of greedy/depth-first thing involved...?

Also, if there is a technique I can use to make sure that whenever Standalone is mixed in, it is ensured that Selector overrules Node (other than copying equals and hashCode from Selector to Standalone), that would be very much appreciated.

This is with Scala 2.9.2.

Kaito · Accepted Answer · 2012-06-23T23:44:34.543

It's best to go to the Spec for this kind of thing. The algorithm is described at 5.1.2 Class Linearization

Paraphrasing it, the Linearization of a class C is C followed by Linearization of the things it extends starting with the rightmost item. Then there is the final step of removing duplicates in the Linearization, keeping only the rightmost ones.

So in your example for Compound1 (ignoring built ins like AnyRef):
L(Compound1) = Compound1 + L(Event) + L(Standalone)
L(Event) = Event + L(Selector)
L(Selector) = Selector
L(Standalone) = Standalone + L(Event) + L(Node)
L(Node) = Node
Putting it together:
L(Compound1) = Compound1 Event Selector Standalone Event Selector Node
Removing the duplicates:
Compound1 Standalone Event Selector Node

For Compound2 it ends up being:
Compound2 Standalone Node Event Selector

As for the other question, I think the easiest way would be to override the method in Standalone and call the desired method in the super class.

trait Standalone extends Node with Event { override def hashCode = super[Event].hashCode }

Assuming this is not what you meant by "copying".

_keeping only the rightmost one_... ok, so that seems to be the problem then. I guess there is no way than to re-implement the methods thus in `Standalone`... — 0__, Jun 23 '12 at 22:48
`Standalone` comes before `Node` and `Selector` in the linearization of both objects so you could override it there. However, all this seems very frail to me, you're probably better off redesigning it. — Kaito, Jun 23 '12 at 23:50

Messed up trait linearisation?

1 Answers1