traits - Linearization order in Scala

Question

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

Answer 1

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