Bidirectional Links in Traits with a Single Type

Question

I am trying to create a trait that implements a tree with bidrectional links such that when a node adds a parent, that node is added to the parent's children. The error I get below is:

type mismatch; found :PolyTree.this.type (with underlying type PolyTree[T]) required: T

Any idea why this code is getting an error and what is needed in order to make this code work:

trait PolyTree[T <: PolyTree[T]]  { 


    private val _parents: ListBuffer[T] = ListBuffer() 
    private val _children: ListBuffer[T] = ListBuffer() 


    def addParent(parent: T): PolyTree[T] = { 

        if (parent == this) 
            throw new IllegalArgumentException(); 

        _parents += parent 

        parent._children += this // Error 

        this 
    } 

}

I think that's meant to be += this, not += tree? But that isn't the cause of the error. — Graham Lea

Graham Lea Graham Lea · Accepted Answer · 2011-05-10T03:24:05

The error occurs because the type of 'parent._children' is 'T', while the type of 'this' is 'PolyTree[T]', which are different types in Scala.

You can fix the error by inserting the the following self-type annotation at the top of the trait:

self: T =>

This is necessary because without it, the following would be valid code:

class TreeOne extends PolyTree[TreeOne]
class TreeTwo extends PolyTree[TreeOne]

TreeTwo is allowed to use TreeOne as the type parameter, because TreeOne satisfies the condition that T <: PolyTree[T]. However, once you add the self-type annotation, Scala essentially tries to cast self/'this' in TreeTwo to 'T' (TreeOne) at compile-time, finds that this isn't type-safe, and rejects the declaration of TreeTwo with the error:

error: illegal inheritance
self-type TreeB does not conform to PolyTree[TreeA]'s selftype TreeA'

I'm not the best at understanding or explaining this stuff, but you can garner a bit more knowledge from Chapter 12. The Scala Type System in O'Reilly's 'Programming Scala'.

Bidirectional Links in Traits with a Single Type

1 Answers