Linearization order in Scala

I have difficulties in understanding the linearization order in Scala when working with traits:

class A {
  def foo() = "A"
}

trait B extends A {
  override def foo() = "B" + super.foo()
}

trait C extends B {
  override def foo() = "C" + super.foo()
}

trait D extends A {
  override def foo() = "D" + super.foo()
}

object LinearizationPlayground {
    def main(args: Array[String]) {

      var d = new A with D with C with B;
      println(d.foo) // CBDA????
  }    
}

It prints CBDA but I can't figure out why. How is the order of the traits determined?

Thx

Solution

An intuitive way to reason about linearisation is to refer to the construction order and to visualise the linear hierarchy.

You could think this way. The base class is constructed first; but before being able of constructing the base class, its superclasses/traits must be constructed first (this means construction starts at the top of the hierarchy). For each class in the hierarchy, mixed-in traits are constructed left-to-right because a trait on the right is added "later" and thus has the chance to "override" the previous traits. However, similarly to classes, in order to construct a trait, its base traits must be constructed first (obvious); and, quite reasonably, if a trait has already been constructed (anywhere in the hierarchy), it is not reconstructed again. Now, the construction order is the reverse of the linearisation. Think of "base" traits/classes as higher in the linear hierarchy, and traits lower in the hierarchy as closer to the class/object which is the subject of the linearisation. The linearisation affects how `super´ is resolved in a trait: it will resolve to the closest base trait (higher in the hierarchy).

Thus:

var d = new A with D with C with B;

Linearisation of A with D with C with B is

(top of hierarchy) A (constructed first as base class)
linearisation of D
- A (not considered as A occurs before)
- D (D extends A)
linearisation of C
- A (not considered as A occurs before)
- B (B extends A)
- C (C extends B)
linearisation of B
- A (not considered as A occurs before)
- B (not considered as B occurs before)

So the linearization is: A-D-B-C. You could think of it as a linear hierarchy where A is the root (highest) and is constructed first, and C is the leaf (lowest) and constructed last. As C is constructed last, it means that may override "previous" members.

Given these intuitive rules, d.foo calls C.foo, which returns a "C" followed by super.foo() which is resolved on B (the trait on the left of B, i.e. higher/before, in the linearization), which returns a "B" followed by super.foo() which is resolved on D, which returns a "D" followed by super.foo() which is resolved on A, which finally returns "A". So you have "CBDA".

As another example, I prepared the following one:

class X { print("X") }
class A extends X { print("A") }
trait H { print("H") }
trait S extends H { print("S") }
trait R { print("R") }
trait T extends R with H { print("T") }
class B extends A with T with S { print("B") }

new B  // X A R H T S B     (the prints follow the construction order)

// Linearization is the reverse of the construction order.
// Note: the rightmost "H" wins (traits are not re-constructed)
// lin(B) = B >> lin(S) >> lin(T) >> lin(A)
//        = B >> (S >> H) >> (T >> H >> R) >> (A >> X)
//        = B >> S >> T >> H >> R >> A >> X