How linearization works

In Scala, linearizations are listed from left to right where the right-most class is the most general, for example, AnyRef. While doing linearization, Any is also added to the hierarchy list. This, combined with the rule that any class must include the linearization of its superclass, means that the superclass linearization will appear as a suffix of the class linearization.

Let's see an example with some really simple classes:

class Animal extends AnyRef
class Dog extends Animal

The linearization of these two classes will be, respectively:

Animal -> AnyRef -> Any
Dog -> Animal -> AnyRef -> Any

Now, let's try and formalize an algorithm that describes how a linearization is calculated:

1. Start with the following class declaration—class A extends B with T1 with T2.
2. Reverse the order of the list except the first item and drop the keywords. This way, the superclass will come as a suffix—A T2 T1 B.
3. Each item gets replaced with its linearization—A T2L T1L BL.

1. Concatenate the list elements using the right-associative concatenation operation: A +: T2L +: T1L +: BL.
2. Append the standard AnyRef and Any classes—A +: T2L +: T1L +: BL +: AnyRef +: Any.
3. Evaluate the preceding expression. Due to the right-associative concatenation, we start from the right and move to the left. In each step, we remove any element that has already appeared on the right-hand side. In our case, when we get to BL, we will not add AnyRef and Any that it also contains; we will just add BL and then we will continue. At T1L, we will skip the step to add anything that was added before and so on, until we reach A.

In the end, after the linearization finishes, we will have a list of classes and traits without duplicates.