Linearization order in Scala

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

The accepted answer is wonderful, however, for the sake of simplification, I would like to do my best to describe it, in a different way. Hope can help some people.

When you encounter a linearization problem, the first step is to draw the hierarchy tree of the classes and traits. For this specific example, the hierarchy tree would be something like this:

The second step is to write down all the linearization of the traits and classes that interferes the target problem. You will need them all in the one before the last step. For this, you need to write just the path to reach the root. The Linearization of traits are as following:

L(A) = A
L(C) = C -> B -> A
L(B) = B -> A
L(D) = D -> A

The third step is to write the linearization of the problem. In this specific problem, we are planning to solve the linearization of

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

Important note is that there is a rule by which it resolves method invocation by first using right-first, depth-first search. In another word, you should start writing the Linearization from most right side. It is as follow: L(B)>>L(C)>>L(D)>>L(A)

Fourth step is the most simple step. Just substitute each linearization from second step to third step. After substitution, you will have something like this:

B -> A -> C -> B -> A -> D -> A -> A

Last but not least, you should now remove all duplicated classes from left to right. The bold chars should be removed: B -> A -> C -> B -> A -> D -> A -> A

You see, you have the result: C -> B -> D -> A Therefore the answer is CBDA.

I know it is not individually deep conceptual description, but can help as an complementary for the conceptual description I guess.

---

And this part explains by relying on formula:

 Lin(new A with D with C with B) = {A, Lin(B), Lin(C), Lin(D)}
 Lin(new A with D with C with B) = {A, Lin(B), Lin(C), {D, Lin(A)}}
 Lin(new A with D with C with B) = {A, Lin(B), Lin(C), {D, A}}
 Lin(new A with D with C with B) = {A, Lin(B), {C, Lin(B)}, {D, A}}
 Lin(new A with D with C with B) = {A, Lin(B), {C, {B, Lin(A)}}, {D, A}}
 Lin(new A with D with C with B) = {A, Lin(B), {C, {B, A}}, {D, A}}
 Lin(new A with D with C with B) = {A, {B, A}, {C, {B, A}}, {D, A}}
 Lin(new A with D with C with B) = {C,B,D,A}

Scala's traits stack, so you can look at them by adding them one at a time:

1. Start with new A => foo = "A"
2. Stack with D => foo = "DA"
3. Stack with C which stacks with B => foo = "CBDA"
4. Stack with B does nothing because B is already stacked in C => foo = "CBDA"

Here's a blog post about how Scala solves the diamond inheritance problem.