An Inheritance Detox

I once pointed out to someone, who was learning Rust, that Rust doesn't have inheritance. He's a software engineering major at RIT1, so this was a shock to him. I eventually told him I would need to give him an object-oriented programming detox. But as I was researching, I learned that even people who like object-oriented programming don't defend inheritance anymore. Inheritance was the problem he was dealing with, so I decided to just focus on that. This post is a blog-translation of the presentation I eventually gave to the Buffalo Rust User Group.

I once attended a Java user group meeting where James Gosling (Java's inventor) was the featured speaker. During the memorable Q&A session, someone asked him: "If you could do Java over again, what would you change?" "I'd leave out classes", he replied. After the laughter died down, he explained that the real problem wasn't classes per se, but rather implementation inheritance (the extends relationship). Interface inheritance (the implements relationship) is preferable. You should avoid implementation inheritance whenever possible.

- Allen Holub

The Problem of Inheritance

For starters, anything you can do with inheritance, you can also do with composition. I'll give some examples of that later. That, on its own, should enough to make you skeptical of inheritance, but I'll keep going.

One problem is that inheritance leads to unnecessary coupling. Allowing the child class to modify the base class, and vice-versa, are going to result in more testing on your part. If you ever change the base class, not only do you need to retest that base class, but also anything that inherits from that base class.

Another problem is known as the fragile-base class problem. To illustrate it, here's an example of some code that would be difficult to write in Rust:

public class Queue<E> extends ArrayList<E> {
	private int start;

	public Queue() {
		this.start = 0;
	}

	public void enqueue(E element) {
		this.add(element);
	}

	public E dequeue() {
		return this.get(this.start++);
	}
}

Say, for the sake of argument, that when you implemented the Queue, the ArrayList only had two methods: get and add. Later, somebody decides to add a clear method. What happens if someone calls queue.clear()? Your start field won't be updated to reflect the new length. So you'll very quickly run into a bug.

Queue<Integer> queue = new Queue<>();
queue.enqueue(5);
queue.enqueue(6);
int x = queue.dequeue();
// pretty normal so far

queue.clear(); // oh no
int y = queue.dequeue(); // oh no no no no

Ok, so let's say, for the sake of argument, that you realize what happened and update Queue quickly.

public class Queue<E> extends ArrayList<E> {
	// ... *snip* ...

	@override
	public void clear() {
		this.start = 0;
		super.clear();
	}
}

That's one problem solved. But what happens when someone adds removeRange?

public class Queue<E> extends ArrayList<E> {
	// ... *snip* ...

	@override
	public void removeRange(int from, int to) {
		// ???
	}
}

So a better way of doing this would be to have Queue contain an ArrayList, rather than being an ArrayList.

public class Queue<E> {
	private int start;
	private ArrayList<E> list;

	public Queue() {
		this.start = 0;
		this.list = new ArrayList<>();
	}

	public void enqueue(E element) {
		this.list.add(element);
	}

	public E dequeue() {
		return this.list.get(this.start++);
	}
}

Note that this is actually very easy to write in Rust.

pub struct Queue<T> {
	start: int,
	list: Vec<T>,
}

impl<T> Queue<T> {
	pub const fn new() -> Self {
		Self {
			start: 0,
			list: Vec::new(),
		}
	}

	pub fn enqueue(&mut self, item: T) {
		self.list.push(item);
	}

	pub fn dequeue(&mut self) -> Option<T> {
		let idx = self.start;
		self.start += 1;
		self.list.get(idx)
	}
}

In Allen Holub's article, Why extends is evil, he gives another example of a problem where optimizing a base Stack class causes a problem if the child classes depend on a method being called. I won't copy and past his article, but I wanted to show that he recommended using an interface in that case. And the interface he wrote translates very nicely to Rust.

pub trait Stack<T> {
	fn push(&mut self, item: T);
	fn pop(&mut self) -> T;
	fn push_many(&mut self, items: &[T]);
}

pub struct SimpleStack<T> {
	stack_pointer: Option<usize>,
	stack: Box<[T]>
}

impl<T> Stack<T> for SimpleStack<T> {
	fn push(&mut self, item: T) {
		self.stack_pointer += 1;
		self.stack[self.stack_pointer] = item;
	}

	fn pop(&mut self) -> T {
		let item = self.stack[self.stack_pointer];
		self.stack_pointer -= 1;
		item
	}

	fn push_many(&mut self, items: &[T]) {
		// Notice that this doesn't call push. If this were a base class for
		// MonitorableStack, it might incorrectly assume that this will call push.

		let start = self.stack_pointer + 1;
		let end = self.stack_pointer + 1 + items.len();
		self.stack[start..end].clone_from_slice(items);
		self.stack_pointer += items.len();
	}
}

pub struct MonitorableStack<T> {
	stack: SimpleStack<T>,
	high_water_mark: usize,
	current_size: usize,
}

impl<T> Stack<T> for SimpleStack<T> {
	fn push(&mut self, item: T) {
		self.current_size += 1;
		if self.current_size > self.high_water_mark {
			high_water_mark = self.current_size;
		}

		self.stack.push(item)
	}

	fn pop(&mut self) -> T {
		self.current_size -= 1;
		self.stack.pop()
	}

	fn push_many(&mut self, items: &[T]) {
		if self.current_size + items.len() > self.high_water_mark {
			self.high_water_mark = self.current_size + items.len();
		}

		// We cannot assume that our call function will be pushed, because
		// that'd be impossible. We're in charge of our own destiny here.
		self.stack.push_many(items)
	}
}

That was a long piece of code. But I hope that the point is clear.

Replacing Inheritance

So if we can't use inheritance, what can we use. Rust provides a few mechanisms for composition:

Let's show a few examples of common object-oriented patterns in Rust.

Factory Methods

It's worth noting that I'm getting these patterns from oodesign.com. For copyright reasons, I will link to their implementation.

Their example is actually hilarious to me, because we can replace it with a type alias, if you're ok with monomorphization, and the fact that Rust doesn't actually care about type bounds on type alises at the moment.

type Factory<P: Product> = fn() -> P;

The typical use-case I've seen for factories in the past is when creating the product relies on some other state. Another case is when we can't specify the underlying type and only know that it's a product. We can do bose of those as well.

trait ProductFactory {
	fn create_product(&mut self) -> Box<dyn Product>;
}

The Java version is even simpler:

interface ProductFactory {
	Product createProduct();
}

Shapes

This is a very common example of inheritance, but I think it's accidentally an example of why you shouldn't use it. There's an example on oodesign.com. Notice that calling setWidth on a square doesn't make very much sense. Here's what I would do in Rust:

trait Shape {
	fn width(&self) -> f32;

	fn height(&self) -> f32;

	fn area(&self) -> f32;

	// no need for set_width and set_height here
}

struct Rectangle {
	width: f32,
	height: f32,
}

impl Rectangle {
	fn set_height(&mut self, height: f32) {
		self.height = height;
	}

	fn set_width(&mut self, width: f32) {
		self.width = width;
	}
}

impl Shape for Rectangle {
	fn width(&self) -> f32 {
		self.width
	}

	fn height(&self) -> f32 {
		self.height
	}

	fn area(&self) -> f32 {
		self.width * self.height
	}
}

struct Square {
	size: f32,
}

impl Square {
	fn set_size(&mut self, size: f32) {
		self.size = size;
	}
}

impl Shape for Square {
	fn width(&self) -> f32 {
		self.size
	}

	fn height(&self) -> f32 {
		self.size
	}

	fn area(&self) -> f32 {
		self.size * self.size
	}
}

Interpreter

I was planning on using the Command pattern here, but after another look I noticed that the provided example didn't even use inheritance. So instead we'll use the interpreter pattern. This pattern is amazing for Rust, because of enums. If you don't want user code to extend the set of possible commands, then this is really simple.

pub enum Expression {
	Literal(Arc<str>),
	Or(Arc<Expression>, Arc<Expression>),
	And(Arc<Expression>, Arc<Expression>)
}

impl Expression {
	fn interpret(&self, tokens: &[Token]) -> bool {
		match self {
			Self::Literal(test) => for token in tokens {
				if token.value() == test {
					return true;
				}

				false
			},
			Self::Or(expr1, expr2) => expr1.interpret(tokens) || expr2.interpret(tokens),
			Self::And(expr1, expr2) => expr1.interpret(tokens) && expr2.interpret(tokens),
		}
	}
}

Let's say, for the sake of argument, that you want the set of expressions to be extendable. That can be done too.

pub trait Expression {
	fn interpret(&self, tokens: &[Token]) -> bool;
}

pub struct TerminalExpression {
	literal: Arc<str>,
}

impl TerminalExpression {
	pub fn new(literal: Arc<str>) -> Self {
		Self { literal }
	}
}

impl Expression for TerminalExpression {
	fn interpret(&self, tokens: &[Token]) -> bool {
		for token in tokens {
			if token.value() == self.literal {
				return true;
			}
		}

		false
	}
}

pub struct OrExpression {
	expression1: Arc<Expression>,
	expression2: Arc<Expression>,
}

impl OrExpression {
	pub fn new(expression1: Arc<Expression>, expression2: Arc<Expression>) -> Self {
		Self {
			expression1,
			expression2
		}
	}
}

impl Expression for OrExpression {
	fn interpret(&self, tokens: &[Token]) -> bool {
		self.expression1.interpret(tokens) || self.expression2.interpret(tokens)
	}
}

pub struct AndExpression {
	expression1: Arc<Expression>,
	expression2: Arc<Expression>,
}

impl AndExpression {
	pub fn new(expression1: Arc<Expression>, expression2: Arc<Expression>) -> Self {
		Self {
			expression1,
			expression2
		}
	}
}

impl Expression for AndExpression {
	fn interpret(&self, tokens: &[Token]) -> bool {
		self.expression1.interpret(tokens) && self.expression2.interpret(tokens)
	}
}

But that is far more verbose.

Observer

In case someone is now accusing me of picking examples that work too easily in Rust, the Observer pattern is actually quite difficult. So before I show this one, I want to give a sneak peak into what this pattern looks like in Java. The inheritance version is provided on oodesign.com, but I'll use composition.

interface Observer {
	void update();
}

class Observable {
	private ArrayList<Observer> observers;

	public Observable() {
		this.observers = new ArrayList<>();
	}

	public void attach(Observer observer) {
		this.observers.add(observer);
	}

	public void detach(Observer observer) {
		this.observers.remove(observer);
	}

	public String notify(String newState) {
		for (Observer observer in this.observers) {
			observer.update();
		}
	}
}

class StatefulObservable {
	private Object state;
	private Observable observable;

	public StatefulObservable(Object initialState) {
		this.state = initialState;
		this.observable = new Observable();
	}

	public void attach(Observer observer) {
		this.observable.attach(observer);
	}

	public void detach(Observer observer) {
		this.observable.detach(observer);
	}

	public Object getState() {
		return this.state;
	}

	public setState(Object newState) {
		this.state = newState;
		this.observable.notify();
	}
}

I wanted this here because I wanted to point out that the tricky part of this pattern is Rust's borrow checker, and not composition. So now we'll walk step by step through making this work in Rust.

First, we'll need an Observer trait. That's easy.

trait Observer {
	fn update(&mut self);
}

"Show me your data, and your functions will be obvious", so let's go ahead and make the Observable struct. The problem is that we need to be able to mix and match different types that all implement Observable. We'll need a dyn Observable, but trait objects aren't sized, and thus can't be put into a Vec directly. We can't use Arc because Observer::update requires a mutable reference. We'll use Box.

struct Observable {
	observers: Vec<Box<dyn Observer>>,
}

You might be wondering why Observer::update needs a mutable reference. What if we want to have multiple references to the observer? The answer to the first question is that some Observers will need to mutate after an update. The answer to the second question is that it won't be difficult to wrap your existing Observer inside of an Arc before attaching it to the Observable. Yeah, Box<Arc<Observer>> isn't ideal, but it's better than forcing the Observables to all have interior mutability.

use super::ImmutableObserver; // we want multiple references to this

#[derive(Debug, Clone)]
pub struct AliasableObserver(Arc<ImmutableObserver>);

impl Observer for AliasableObserver {
	fn update(&mut self) {
		self.0.update()
	}
}

Alternatively, we could update our API to allow both immutable and mutable observers.

pub trait Observer {
	fn update(&self);
}

pub trait MutableObserver {
	fn update(&mut self);
}

pub struct Observable {
	observers: Vec<Arc<dyn Observer>>,
	mutable_observers: Vec<Box<dyn MutableObserver>>,
}

I actually like this idea, so let's go with this. But this raises another concern. In Java, we could detach observers by passing in a reference and comparing the pointer addresses. This is still possible with observers but not mutable_observers, since a Box needs to be a unique reference. But, we could use a raw pointer.

impl Observable {
	pub fn detach(&mut self, observer: *const ()) -> Option<()> {
		for i in 0..self.observers.len() {
			if std::ptr::addr_eq(&self.observers[i], observer) {
				self.observers.remove(i);
				return Some(());
			}
		}

		for i in 0..self.mutable_observers.len() {
			if std::ptr::addr_eq(&self.mutable_observers[i], observer) {
				self.mutable_observers.remove(i);
				return Some(());
			}
		}

		None
	}
}

Dealing with raw pointers is annoying, but it works. Alternatively, we could put an ID on each attached observer, and remove using an ID, but that sounds even worse. Plus, we'd have to deal with a sparse index. I don't want that.

I suppose we've jumped the gun a bit on implementing detach, so now let's implement the rest of Observable.

impl Observable {
	pub const fn new() -> Self {
		Self {
			observers: Vec::new(),
			mutable_observers: Vec::new(),
		}
	}

	pub fn attach(&mut self, observer: Arc<dyn Observer>) {
		self.observers.push(observer);
	}


	pub fn attach_mutable(&mut self, observer: Box<dyn MutableObserver>) {
		self.mutable_observers.push(observer);
	}

	pub fn detach(&mut self, observer: *const ()) -> Option<()> {
		// ... already did this ...
	}

	pub fn notify(&mut self) {
		for observer in &self.observers {
			observer.update();
		}

		for observer in &mut self.mutable_observers {
			observer.update();
		}
	}
}

Now all that's left is the StatefulObserver. In the Java implementation, I used an Object as the state, but that's not very useful in Rust (or in general). So instead I'll use a generic type here. The implementation is pretty simple, so I'll write that out too.

pub struct StatefulObservable<T> {
	state: T,
	observable: Observable,
}

impl<T> StatefulObservable<T> {
	pub const fn new(initial_state: T) -> Self {
		Self {
			state: initial_state,
			observable: Observable::new(),
		}
	}

	pub fn state(&self) -> &T {
		&self.state
	}

	pub fn attach(&mut self, observer: Arc<dyn Observer>) {
		self.observable.attach(observer)
	}

	pub fn attach_mutable(&mut self, observer: Box<dyn MutableObserver>) {
		self.observable.attach_mutable(observer)
	}

	pub fn detach(&mut self, observer: *const ()) -> Option<()> {
		self.observable.detach(observer)
	}

	pub fn set_state(&mut self, new_state: T) {
		self.state = new_state;
		self.observable.notify();
	}
}

And now we're done. Here's the full code for the curious:

use std::sync::Arc;

pub trait Observer {
	fn update(&self);
}

pub trait MutableObserver {
	fn update(&mut self);
}

pub struct Observable {
	observers: Vec<Arc<dyn Observer>>,
	mutable_observers: Vec<Box<dyn MutableObserver>>,
}

impl Observable {
	pub const fn new() -> Self {
		Self {
			observers: Vec::new(),
			mutable_observers: Vec::new(),
		}
	}

	pub fn attach(&mut self, observer: Arc<dyn Observer>) {
		self.observers.push(observer);
	}


	pub fn attach_mutable(&mut self, observer: Box<dyn MutableObserver>) {
		self.mutable_observers.push(observer);
	}

	pub fn detach(&mut self, observer: *const ()) -> Option<()> {
		for i in 0..self.observers.len() {
			if std::ptr::addr_eq(&self.observers[i], observer) {
				self.observers.remove(i);
				return Some(());
			}
		}

		for i in 0..self.mutable_observers.len() {
			if std::ptr::addr_eq(&self.mutable_observers[i], observer) {
				self.mutable_observers.remove(i);
				return Some(());
			}
		}

		None
	}

	pub fn notify(&mut self) {
		for observer in &self.observers {
			observer.update();
		}

		for observer in &mut self.mutable_observers {
			observer.update();
		}
	}
}

pub struct StatefulObservable<T> {
	state: T,
	observable: Observable,
}

impl<T> StatefulObservable<T> {
	pub const fn new(initial_state: T) -> Self {
		Self {
			state: initial_state,
			observable: Observable::new(),
		}
	}

	pub fn state(&self) -> &T {
		&self.state
	}

	pub fn attach(&mut self, observer: Arc<dyn Observer>) {
		self.observable.attach(observer)
	}

	pub fn attach_mutable(&mut self, observer: Box<dyn MutableObserver>) {
		self.observable.attach_mutable(observer)
	}

	pub fn detach(&mut self, observer: *const ()) -> Option<()> {
		self.observable.detach(observer)
	}

	pub fn set_state(&mut self, new_state: T) {
		self.state = new_state;
		self.observable.notify();
	}
}

Conclusion

Anything you can do with inheritance, you can also do with composition. Composition will make your code easier to modify in the future, without creating weird semantics or bugs. Use composition, wherever possible.