Tag: design

Today in ##java, someone had a problem: They wanted a bounded-size PriorityQueue. One solution offered was extending the PriorityQueue class to add this behavior¹.
This article will talk about why that is not a good solution.
Here is an example implementation of this approach:

public class BoundedPriorityQueue<E> extends PriorityQueue<E> {
    private final int bound;
    public BoundedPriorityQueue(Comparator<? super E> comparator, int bound) {
        super(comparator);
        this.bound = bound;
    }
    @Override
    public boolean add(E e) {
        if (size() >= bound) { return false; }
        return super.add(e);
    }
}

Now… This looks somewhat correct, if you don’t pay attention. But it isn’t! The important thing missed here is that the Queue.offer(E) method is not overridden, and gives the user a way to put this queue into an invalid state (too many items).
In this particular case this is not a huge issue. There are only two methods, offer and add, that increase the size of a PriorityQueue, and add happens to delegate to offer. The important thing to get out of this example is that this bug can happen in the first place, and that the compiler – or runtime – won’t warn you about it.

Extending ArrayList

Let’s get to a more problematic example. We want to have a List that can only be added to, but never removed from.

public class AddOnlyArrayList<E> extends ArrayList<E> {
    @Override public E remove(int index) { throw new UnsupportedOperationException(); }
    @Override public boolean remove(Object o) { throw new UnsupportedOperationException(); }
    @Override public boolean removeAll(Collection<?> c) { throw new UnsupportedOperationException(); }
    @Override public void clear() { throw new UnsupportedOperationException(); }
    @Override public Iterator<E> iterator() { return Iterators.unmodifiableIterator(super.iterator()); }
    @Override public List<E> subList(int fromIndex, int toIndex) { return ...; }
    @Override public ListIterator<E> listIterator() { return ...; }
    @Override public ListIterator<E> listIterator(int index) { return ...; }
}

Hey, this is good, right? All remove methods and clear accounted for, iterators and subList also implemented, should be fine! Well, that’d be right. In Java 7.
With Java 8, Collection.removeIf(Predicate<E>) was added. This is a default method on Collection that normally only delegates to iterator, but ArrayList has its own, optimized version of it.
Suddenly, just with a JDK update, our class breaks and we may not even notice it. The issue is pretty subtle – it may never appear, and when it does happen, the only way we’ll notice is that our “AddOnly”ArrayList suddenly is shrinking because someone elsewhere decided to use that fancy new removeIf method.
The core problem with both these examples is that extension is fragile. A class has to be designed with extension in mind if it’s supposed to be extensible this way. While most standard library classes aren’t final, many of them are not intended to be extended, or only offer hooks for some specific forms of extension.

How to do it properly

You hear this repeated often, but many do not really seem to understand why: Prefer composition over inheritance. Here’s our AddOnlyArrayList with composition:

public class AddOnlyArrayList<E> extends AbstractList<E> {
    private final List<E> elements = new ArrayList<>();
    @Override public E get(int index) { return elements.get(index); }
    @Override public int size() { return elements.size(); }
    @Override public E set(int index, E element) { return elements.set(index, element); }
    @Override public void add(int index, E element) { elements.add(index, element); }
}

remove is unsupported by this class, but importantly, this can never change. The elements list we’re delegating to is fully encapsulated, and we control all access to it. There’s no way for a future change in List, AbstractList or even ArrayList itself to allow removal of elements. This approach is a lot less fragile than extending ArrayList itself.
Here’s our implementation of BoundedPriorityQueue following the same principle:

public class BoundedPriorityQueue<E> extends AbstractQueue<E> {
    private final Queue<E> elements;
    private final int bound;
    public BoundedPriorityQueue(Comparator<? super E> comparator, int bound) {
        this.elements = new PriorityQueue<>(comparator);
        this.bound = bound;
    }
    @Override public Iterator<E> iterator() { return elements.iterator(); }
    @Override public int size() { return elements.size(); }
    @Override public E poll() { return elements.poll(); }
    @Override public E peek() { return elements.peek(); }
    @Override
    public boolean offer(E e) {
        if (elements.size() > bound) return false;
        return elements.offer(e);
    }
}

Disadvantages

Of course, delegation has its disadvantages.

Memory overhead

There’s an additional object for the wrapper. This isn’t really a problem in practice, though.

Performance

You can’t take advantage of all optimizations a class may introduce in the future. ArrayList.removeIf is a great example again – the delegating class will only delegate a subset of methods, falling back to the potentially unoptimial behavior of AbstractList for others. But importantly, while this may be slower, it’s always correct – if it becomes a problem, just delegate that method as well. At least it won’t suddenly lead to broken behavior.

Missing Optional Methods

It’s possible to miss certain optional methods when delegating. In the standard AbstractList example, it’s very easy to forget to delegate the set(int, E) method since it isn’t used very often.
However, this is usually fail-fast – it’ll throw an Exception and you’ll notice it – and much preferrable to the unexpected and subtle results wrong extension may produce.

Additional Code

Especially with large interfaces and interfaces where you don’t have a handy stub class like AbstractList available, there can be quite a lot of methods to delegate. This is probably the biggest problem with delegation and a good reason to keep interfaces small.

Tooling

Your IDE can assist you with generating delegation methods.
If you are a fan of lombok, it offers an experimental @Delegate annotation. But beware: Using this annotation with only excludes defined can lead to the very same issue! Take the example from the lombok website:

class ExcludesDelegateExample {
  long counter = 0L;
  private interface Add {
    boolean add(String x);
    boolean addAll(Collection<? extends String> x);
  }
  @Delegate(excludes=Add.class)
  private final Collection<String> collection = new ArrayList<String>();
  public boolean add(String item) {
    counter++;
    return collection.add(item);
  }
  public boolean addAll(Collection<? extends String> col) {
    counter += col.size();
    return collection.addAll(col);
  }
}

Here we are missing proper handling for the listIterator.add and corresponding subList methods – we can enter invalid states and can have subtle bugs. Be very careful when using this annotation!

Conclusion

Don’t extend classes that weren’t meant to be extended. A class not being final does not give us a free pass – non-final is the default in java, and many programmers do not design their classes with extension in mind (and that’s fine).
Before extending a class with actual logic in it, think about alternatives. Can you use delegation instead? With collections and their convenient Abstract* stub implementations it’s easy, but with small interfaces you may not even need that.

---