Designing interface for hierarchical entity

Question

I have to design an interface for hierarchical entity:

interface HierarchicalEntity<T extends HierarchicalEntity<T>> {
    T getParent();
    Stream<T> getAncestors();
}

It's quite easy to implement default getAncestors() method in terms of getParent() in such a way that the former would return Stream of all the ancestors.

Implementation example:

default Stream<T> getAncestors() {
    Stream.Builder<T> parentsBuilder = Stream.builder();
    T parent = getParent();
    while (parent != null) {
        parentsBuilder.add(parent);
        parent = parent.getParent();
    }
    return parentsBuilder.build();
}

But I need to also include this into the stream, and here a problem appears. The following line is not correct because this is of type HierarchicalEntity, not T:

parentsBuilder.add(this); // type mismatch!

How can I redesign the interface in order to make getAncestors() include this into the result?

Answer 1

It’s a recurring problem when creating self-referential types. In the base type (or interface), you can’t enforce that this will be assignment compatible with T.

Of course, you can perform an unchecked cast of this to T if you are confident that all subtypes will fulfill that constraint. But you have to perform this unchecked cast whenever you need a this reference as T.

The better solution is to add an abstract method like

/**
    All subtypes should implement this as:

    public T myself() {
        return this;
    }
 */
public abstract T myself();

Then, you can use myself() instead of this whenever you need a self-reference as T.

default Stream<T> getAncestors() {
    Stream.Builder<T> parentsBuilder = Stream.builder();
    for(T node = myself(); node != null; node = node.getParent()) {
        parentsBuilder.add(parent);
    }
    return parentsBuilder.build();
}

Of course, you can’t enforce that subclasses correctly implement myself() as return this;, but at least, you can easily verify whether they do at runtime:

assert this == myself();

This reference comparison is a very cheap operation and, if myself() is correctly implemented as invariably returning this, HotSpot can prove in advance that this comparison will always be true and elide the check completely.

The drawback is that each specialization will have to have this redundant implementation of myself() { return this; }, but on the other hand, it’s completely free of unchecked type casts. The alternative is to have an non-abstract declaration of myself() in the base class as @SuppressWarnings("unchecked") T myself() { return (T)this; } to limit the unchecked operation to a single place for the type hierarchy. But then, you can’t verify whether this really is of type T…

Answer 2

As @SotiriosDelimanolis said, there's no way fully enforce this. But if you're willing to assume the interface is being used as designed, you can assume that this is an instance of T and simply cast it:

parentsBuilder.add((T)this);

If you want to avoid casting, you can add a method to be overridden in the subclass:

interface HierarchicalEntity<T extends HierarchicalEntity<T>> {
    T getParent();
    T getThis();
    default Stream<T> getAncestors() {
        // ...
        parentsBuilder.add(getThis());
        // ...
    }
}

class Foo extends HierarchicalEntity<Foo> {
    // ...
    @Override
    public Foo getThis() {
        return this;
    }
}

Now we can get this in a typesafe manner, but there's no guarantee that getThis() has been implemented correctly. It's possible for it to return any instance of Foo. So, pick your poison I guess.