Scala's trait mix-in call chain

Question

I have this Scala code:

trait Foo {
    def foo()
}

trait M extends Foo {
    abstract override def foo() {println("M"); super.foo()}
}

// interface implementation
class FooImpl1 extends Foo {
    override def foo() {println("Impl")}
}

class FooImpl2 extends FooImpl1 with M

object Main extends App {
    val a = new FooImpl2
    a.foo 
}

When executed, it prints out

M
Impl

What I'm curious is the mechanism behind the trait method. In this case, the foo in trait M is invoked first, and then super.foo() invokes the concrete call of FooImpl1.foo(). What's the logic behind this call chain? Is there any documentation about this behavior?

Answer 1

Yes, it is called "linearization" and it solves the hated Diamond Problem of Multiple Inherithance in a ver clever way.

Check the links (or the original paper and you'll learn more than any a quick answer I can give, but the basic idea is this: The order in which you inherit from multiple traits or abstract classes matters. Scala will create a single inheritance line, with no breaks, by picking parents in order and calling the closest override available.

Or better yet, check the canonical example from Chapter 12 of Programming in Scala, First Edition:

---

The main properties of Scala's linearization are illustrated by the following example: Say you have a class Cat, which inherits from a superclass Animal and two traits Furry and FourLegged. FourLegged extends in turn another trait HasLegs:

 class Animal 
  trait Furry extends Animal
  trait HasLegs extends Animal
  trait FourLegged extends HasLegs
  class Cat extends Animal with Furry with FourLegged

Class Cat's inheritance hierarchy and linearization are shown in Figure 12.1. Inheritance is indicated using traditional UML notation:3 arrows with white, triangular arrowheads indicate inheritance, with the arrowhead pointing to the supertype. The arrows with darkened, non-triangular arrowheads depict linearization. The darkened arrowheads point in the direction in which super calls will be resolved.

Figure 12.1 - Inheritance hierarchy and linearization of class Cat.

The linearization of Cat is computed from back to front as follows. The last part of the linearization of Cat is the linearization of its superclass, Animal. This linearization is copied over without any changes. (The linearization of each of these types is shown in Table 12.1 here.) Because Animal doesn't explicitly extend a superclass or mix in any supertraits, it by default extends AnyRef, which extends Any. Animal's linearization, therefore, looks like:

The second to last part is the linearization of the first mixin, trait Furry, but all classes that are already in the linearization of Animal are left out now, so that each class appears only once in Cat's linearization. The result is:

This is preceded by the linearization of FourLegged, where again any classes that have already been copied in the linearizations of the superclass or the first mixin are left out:

Finally, the first class in the linearization of Cat is Cat itself:

When any of these classes and traits invokes a method via super, the implementation invoked will be the first implementation to its right in the linearization.