+ +

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 RIT¹, 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:

structs (the equivalent of final class in Java)
traits (like interfaces in Java)
enums (Java has no equivalent. Java enums aren't the same.)

+ +

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. +

+ +