Scala's Diamond problem

Intro

Have recently learned about Scala's Diamond problem solution and found out most examples cover particular paths leaving some opened questions.

In this article I reverse engineer the concept so that I can recall it next time I revise it, as this concept is pretty complex.

First thing I learned is that the solution to diamond problem is called Scala Linearization. It is an algorithm that constructs the list of traits in the order of priority. Where the nearest to the object has the highest priority.

Example:

A->B->C->D

Means B has the highest priority in the list, and A is the Object that has to call a method that can be defined and implemented in any of B, C, D.

Thus understanding how to build the list is the key to understanding what would be the result.

Reverse engineering the algorithm

Algorithm description in Wikipedia: "using a right-first depth-first search of extended 'traits', before eliminating all but the last occurrence of each module in the resulting list" Wikipedia - multiple-inheritance

This means there are three rules

1. right-first


2. depth-first


3. eliminate duplicates but the last

Right first is the most explained one of the three, one that I found insightful enough is this one: Medium - diamond-problem-solution-in-scala

Depth first is seldom covered in articles, a very good article that I found impresive is this one: Kyriakos - liniarization-in-scala

It analysis how linearization works, and in my opinion misses just one thing, the case when the right branch is bigger then the left one as below:

So if B and E override the same method, which one will be called ?

Extending the examples in the Right first article to demonstrate it:

object DiamondProblem {



    trait A {

        def M(): Unit = println("Hi, This is M from trait A")

    }

    trait B extends A {

        override def M(): Unit = println("Hi, This is M from trait B")

    }

    trait E extends A {

        override def M(): Unit = println("Hi, This is M from trait E")

    }

    trait C extends E {

    }

    class D extends B with C {

    }



    def main(args: Array[String]): Unit = {

        var sut = D().M()

    }

}

The result is:

Hi, This is M from trait E

And I guess it completes the demonstration for the depth first.

Eliminate duplicates but the last - for me it was hard to understand until I literally applied it over the Wikipedia's path:

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

removing duplicate elements but last results in

D->C->B->A

In case of depth-first we have D->C->E->A->B->A, resulting in

D->C->E->B->A.

I think I understood the concept. Comment if you disagree.