Scala Class Linearization

When you use Scala traits to inherit implementation from more than one parent, Scala uses a technique called linearization to resolve ambiguities.

Contents

• Overview
• Trait Declarations
• Trait Class Files
• Linearization Rules
• Class Initialization
• Method Overriding
• Variable Overriding
• Type Overriding
• Glossary

Overview

Unlike Java interfaces, Scala traits can include code, which effectively gives the ability to do multiple inheritance. Implementations of multiple inheritance without linearization can suffer from the diamond inheritance problem, in which there is an ambiguity in how to deal with an attribute such as a method which could be inherited from either parent. Linearization specifies a single linear order for all of the ancestors of a class, including both the regular superclass chain and the parent chains of all of the traits.

Scala traits that contain code are called mixin (or mix-in) traits. If you don't use any mixin traits, then the only code is in the regular superclass chain, just as in Java, and linearization is not an issue. Since linearization is only of interest when using mixin traits, it is worth reviewing the characteristics and constraints on such traits.

Trait Declarations

A Scala trait can include code, in which case the trait is called a mixin trait. The code can be any of the following:

• method definitions.
• mutable and immutable variables (vars and vals).
• a no-argument constructor (a trait may not have a constructor with parameters).

When considering the inheritance hierarchies of classes and traits, they are in many ways similar:

• Both can use with clauses to inherit from additional traits (with some restrictions, see below).
• Every class and trait declaration is always implicitly extended to include with ScalaObject at the end. If you explicitly add with ScalaObject you will get an error that it has been inherited twice.
• If a class or trait does not explicitly extend any class or trait, then its superclass is AnyRef, which compiles to java.lang.Object (just as in Java).
• If a class or trait is declared to extend a trait directly rather than extending a class with that trait, that declaration is treated the same as if it explicitly extended the trait's superclass with the trait.
• Every user-defined class and trait has exactly one superclass that it extends, which is one of
  1. the explicitly extended superclass (as opposed to extending a trait),
  2. the superclass of the trait being explicitly extended, or
  3. implicitly AnyRef when nothing is explicitly extended.

Note that the superclass of a trait that extends a trait is the superclass of the parent trait, so the new trait has the same superclass as its parent.

All class and trait declarations can be converted into a canonical form in which the superclass (a class, not a trait) is explicitly specified using extends, all traits are specified using with, and the ScalaObject trait is automatically appended to the end.

For example, given these trait and class declarations:

class A
class B extends A
trait C
trait D extends B
class E extends D with C

the canonical form for each of these is:

class A extends AnyRef with ScalaObject
class B extends A with ScalaObject
trait C extends AnyRef with ScalaObject
trait D extends B with ScalaObject
class E extends B with D with C with ScalaObject

The following class definitions all produce an identical class file:

class A
class A extends AnyRef
class A extends java.lang.Object

Trait Class Files

When you define a Scala trait with only method declarations but no code, Scala produces a Java interface class file, just as you would get by defining an interface in Java. When you include code in your Scala trait, Scala still produces the same Java interface class file, but it also produces a second class file that contains your code. For example, create this simple Scala file A.scala:

trait A { def a:Int }

Compile with scalac A.scala to produce A.class, then dump it with javap -c A to get this:

Compiled from "A.scala"
public interface A{
public abstract int a();

}

Now modify the trait to include some code:

trait A { def a:Int = 1 }

Compile with scalac and you will see two class files: in addition to the interface class file A.class there is a code class file called A$class.class. Running javap -c A shows that A.class is identical to what it was when A.scala contained no code. Running javap -c 'A$class' shows the added code:

Compiled from "A.scala"
public abstract class A$class extends java.lang.Object{
public static void $init$(A);
  Code:
   0:   return

public static int a(A);
  Code:
   0:   iconst_1
   1:   ireturn

}

The a method is our code that returns 1, and the $init$ method is our empty constructor code.

When a class extends a trait, any variables declared in the trait appear in the class, methods in the trait get turned into facade methods in the class that turn around and call the code for that method in the trait's code class, and the constructor for the class makes a call to the $init$ method in the trait's code class. If you want to see this in more detail, you can create a class B that extends trait A, compile it, and run javap on the B.class file. The output is a bit convoluted, which is why I tried to summarize here what is going on.

Linearization Rules

Scala's linearization rules are described starting on page 49 of the Scala Language Specification (SLS), Chapter 5, "Classes and Objects".

In order to allow reuse of compiled classes and to ensure well-defined behavior, the linearization must satisfy a few rules:

• The linearization of any class must include unmodified the linearization of any class (but not trait) it extends.
• The linearization of any class must include all classes and mixin traits in the linearization of any trait it extends, but the mixin traits need not be in the same order as they appear in the linearization of the traits being mixed in.
• No class or trait may appear more than once in the linearization.

One consequence of these rules is that it is not possible to create a class or trait that has multiple disjoint superclasses. In other words, the set of all base classes (excluding traits) of a class or trait must form a simple linear chain of class extensions. Consider a potential counterexample, where classes A and B separately extend AnyRef (thus they are disjoint), and class C extends A with B. Since the linearization of A is A-AnyRef and the linearization of B is B-AnyRef, there is no way to create a single linearization that includes A, B and AnyRef that includes the linearizations of both A and B and does not include the AnyRef class more than once. This statement continues to hold true if there are traits inserted between A and AnyRef, B and AnyRef, or C and either A or B. Thus defining this kind of disjoint class ancestry is not allowed.

The disallowance of disjoint class ancestry constrains the allowable combinations of trait and class inheritance. Thus while it is possible for a class to inherit from a trait, and for a trait to inherit from a class, not all traits can be used with all classes. A trait whose superclass is AnyRef can be mixed in with any class, but if the trait's superclass is something more specific, then there are some classes with which that trait can not be used. Given a class C that is extending a superclass S, the only traits that can be mixed in with C are traits whose superclass is either S or an ancestor of S.

From the way the Java language and VM works, we know that when an object is initialized, the constructor for the java.lang.Object class runs first. In terms of linearization, this means that Object must be at one end of the linearization, and that initialization must start at that end. By convention, Scala linearizations are listed from left to right, with the rightmost class being the most general, i.e. Object. The combination of Object (which in Scala translates to AnyRef, or in a linearization AnyRef followed by Any) being the rightmost class together with the rule that the linearization of a class must include the linearization of its superclass means that the linearization of the superclass must appear as a suffix (i.e. as the rightmost part) of the linearization of the class.

As mentioned earlier, all class and trait declarations are implicitly extended by adding with ScalaObject at the end. The predefined Scala classes such as Any and AnyRef do not include this declaration. Thus if you declare a class

class Foo extends AnyRef

the linearization of that class will be (SLS section 5.1.2):

{ Foo, ScalaObject, AnyRef, Any }

If you now declare a class that extends that class

class Bar extends Foo

the linearization of the extended class will include the linearization of the superclass as a suffix:

{Bar, Foo, ScalaObject, AnyRef, Any }

The linearization of the values classes (such as Int in this example) are all of the form

Int, AnyValue, Any

Since these classes are final and you can't extend them, you don't need to worry about calculating linearizations.

The linearization of a reference class is calculated using the following algorithm:

1. Start with the class declaration, for example:

   class C extends S with T1 with T2
   

2. Reverse the order of the list, except keep the first item (C) at the beginning, and drop the other keywords:

   C T2 T1 S
   

3. Replace each item in the list except the first (C) with its linearization:

   C T2L T1L SL
   

4. Insert a right-associative list-concatenation operator between each element in the list:

   C +: T2L +: T1L +: SL
   

5. Append the standard Scala classes ScalaObject, AnyRef, Any:

   C +: T2L +: T1L +: SL +: ScalaObject +: AnyRef +: Any
   

6. Evaluate the list to get the final linearization. The operator works on two lists as follows: remove any items from the left hand list that appear in the right hand list, then prepend the remaining items from the left hand list to the right hand list (if either side is not a list, treat it as a list with one element). The operator is right-associative, so start with the classes on the right end and work your way to the left until all lists have been combined; in this example, the first possibility to remove anything will be to look at S_L and remove any duplicates of ScalaObject, AnyRef and Any; then look at T1_L and remove anything already in S_L or to the right of it, and so on back to C.

Recall that all of the traits in the list must have as their smallest superclass (as opposed to a parent trait) either S or any superclass of S, so when combining the linearization of a trait into the linearization of the superclass S, as soon as we run into a class rather than a trait, we know that that class and everything past it in the linearization of that trait must already be represented in the linearization of S and thus we can ignore them. That means the only thing that can be contributed by the linearization of a trait are that trait's mixin and the mixins of any parent trait which does not already appear in any of the linearizations to the right of that trait in the list.

The SLS gives as Example 5.1.3 this set of class declarations and the linearization of class Iter:

abstract class AbsIterator extends AnyRef { ... }
trait RichIterator extends AbsIterator { ... }
class StringIterator extends AbsIterator { ... }
class Iter extends StringIterator with RichIterator { ... }

{ Iter, RichIterator, StringIterator, AbsIterator, ScalaObject, AnyRef, Any }

For another description of the linearization algorithm, including some more complex examples, see Linearization of an Object's Hierarchy in Chapter 7, The Scala Object System, in the 2008 O'Reilly book Programming Scala by Dean Wampler and and Alex Payne.

Class Initialization

When creating an instance of a class (what the SLS calls "template evaluation", section 5.1), the constructor code is executed according to the order of classes in the linearization but in reverse, from right to left. The first constructors executed are for Any and AnyRef, and the last is for the class being instantiated.

Because the linearization is defined to include as a suffix the linearization of the superclass, this means the entire constructor of the superclass is executed before the constructor of the class or any of its mixin traits are executed.

After the superclass constructor is executed, the constructors for each mixin trait are executed. Since they are executed in right-to-left order within the linearization, but the linearization is created by reversing the order of the traits, this means the constructors for the mixin traits are executed in the order that they appear in the declaration for the class. Remember, however, that when mixins share hierarchy, the order of execution may not be quite the same as how the mixins appear in the declaration.

Finally, the constructor for the class being instantiated is executed. This happens after the constructors for all superclasses and mixins have been executed.

Method Overriding

As in Java, when class A extends class B in Scala it can typically override method definitions in class B. The SLS has a detailed set of rules (section 5.1.4) about when an extending class can override a member (def, var or val) of a supertype. These are approximately:

• You can't override a final or private.
• Visibility (access modifiers such as public or protected) and laziness must match.
• In a concrete class, all abstracts must be overridden.
• When overriding non-abstract members, the override keyword must be used.

As in Java, when you override a method you can invoke the overridden method in the supertype from the new method by using the keyword super as an object qualifier before the method name. In Scala, you can invoke the supertype using the same syntax, or you directly reference any of the traits in the declaration of the class, possibly skipping some of the overridden methods of the traits between, by qualifying the super keyword with a trait type (a trait qualifier, to form a static super reference; SLS, section 6.5, page 73).

Consider the following scala definitions, along with a simple test object T, which you can compile and run to print the values indicated by the comments:

class A { def t = 1 }
trait B extends A { override def t = super.t * 2 }
trait C extends A { override def t = super.t * 3 }

class D1 extends B with C { override def t = super.t }
class D2 extends B with C { override def t = super[B].t }
class D3 extends B with C { override def t = super[C].t }

class E1 extends C with B { override def t = super.t }
class E2 extends C with B { override def t = super[B].t }
class E3 extends C with B { override def t = super[C].t }

object T {
    def main(args:Array[String]) {
        println((new D1).t)     //prints 6
        println((new D2).t)     //prints 2
        println((new D3).t)     //prints 6
        println((new E1).t)     //prints 6
        println((new E2).t)     //prints 6
        println((new E3).t)     //prints 3
    }
}

The above code shows how you can specify a particular parent trait to call. You can directly call to any of the traits in the with clause, or to the direct supertype being extended, but you can not directly call supertypes of your direct supertype.

Note that traits B and C both extend A, so you might think that calling super.t from within either B or C would refer to A.t, but that's not how Scala works. The super.t reference is to the next class in the linearization, working from left to right along that list. In the linearization of D1, C comes before B (D1, C, B, A), so calling super.t from C calls to B.t, and calling super.t from B calls to A.t; but the linearization of E1 has B before C (E1, B, C, A), so the super.t calls between B and C are in the other direction, with super.t in B calling C.t and super.t in C calling A.t.

Given that you can compile B and C separately, then compile the D and E classes using just the class files for B and C rather than their source files, how is it that Scala can make super.t in B call A.t in one case and C.t in another? If you run javap on the B and B$class classes, you will see the answer:

$ javap B
Compiled from "T.scala"
public interface B extends scala.ScalaObject{
    public abstract int t();
    public abstract int B$$super$t();
}

$ javap 'B$class'
Compiled from "T.scala"
public abstract class B$class extends java.lang.Object{
    public static void $init$(B);
    public static int t(B);
}

Scala creates a method B$$super$t that is defined in the B interface, but not implemented in the B$class class. When the trait is used in a class declaration, as in D1 or E1, Scala creates an implementation of B$$super$t that calls the appropriate super method.

Variable Overriding

You can override variables (vals or vars) using the same rules as for methods. In particular, the "laziness" of the overriding variable must match that of the overridden variable: either they are both lazy, or neither is lazy.

The lazy declaration is particularly useful when setting up variable overrides, since the order of execution of initialization code can make it difficult to understand what is happening.

For example, consider this code in a query posted to the Scala listserv by Sébastien Bocq in July of this year:

abstract class A(s:Option[String]) {
    val h = s.get
}

class B extends A(None) {
    override val h = "Hello"
}

When B is instantiated it throws a NoSuchElementException in line 2 of class A. Despite the initialization of the overriding h in class B, the initialization of h in class A still occurs, since it is part of the class initialization of A, which is executed before anything in class B is executed.

One easy solution, as Sébastien points out, is to make h a lazy val in both classes.

Unlike methods, you can not use the super notation with variables. When you override a variable, the overridden version is no longer available. However, note that you can override a def in a superclass with a val in an extending class:

class A { def x = 1 }
class B extends A { override val x = 2 }

When overriding a def with a val you can access the def in the superclass by using the super notation, which will call that method once when calculating the initialization of the val:

class B extends A { override val x = super.x + 1 }

Type Overriding

Scala currently uses linearization to resolve type overrides in the same way as method and variable overrides, by using inheritance with linearization. This is sometimes not what people expect, and Martin has commented that he has considered changing this behavior to make overridden type declarations compositional and commutative, which might make them more useful and less surprising, despite the fact that overriding types would then be different from overriding other elements.

Scala types have a lot of flexibility, and when you mix that flexibility with overriding you can get into complicated situations and unexpected behavior pretty quickly. There is enough more to say about types to make another entire post, so I will not go into that in any more detail here.

I leave you with this valid Scala code fragment, which I find interesting:

class P { def x=1; def y=2 }
trait X { type T <: { def x:Int } }
trait Y { type T <: { def y:Int } }
class C extends X with Y { type T = P }

Glossary

• base classes: "The classes reachable through transitive closure of the direct inheritance relation from a class C" (SLS, section 5.1.2, page 52). In other words, all of the immediate supertypes and their supertypes back to the root object.
• least proper supertype of a class: "the class type or compound type consisting of all its parent class types" (SLS, section 5.1, page 50).
• linearization: the arranging of a class and its base classes into a linear ordering.
• parent class or type: one of the classes or traits listed in the declaration of a class or trait from which it extends; an immediate supertype.
• superclass of a class C (when used in this document without qualification): a class (not trait) which is one of the base classes of C.
• supertype of a class C (when used in this document without qualification): a class or trait which is one of the base classes of C.

Updated 2010-10-17: revised description of linearization algorithm; added reference to Wampler and Payne's Programming Scala.