Emulating abstract base classes in Rust

When coming from a mainstream oop language like C# to Rust, like me, the lack of implementation inheritance is one of the many things you have to get used to. Unfortunately, this means that tried and true inheritance-based patterns for code reuse like Template Method, which is a common use case for abstract base classes, are not available to us.

In this post, I will take you on a ride from a naive way to emulate an abstract base class in Rust, inspired by what you might do in many oop languages, to a version that actually works. After that, I will show how a little change in perspective can lead to a much more elegant solution.

If you are just interested in the final approach, feel free to skip to the section A more Elegant Solution. Otherwise, come along.

The Problem

Let's say you have a general problem with variations that differ only in a few specific details, like e.g. day 18 of the 2020 installment of AdventOfCode, which requires you to write a formula parser for each part of the problem; they only differ in the semantics of binary operations.

In a language like C# a typical approach to this setup is to use an abstract base class as follows.

public abstract class FormulaPaserBase
{
    protected abstract FormulaExpression ParseBinaryOperation(int index, List<Token> tokenstream);

    public FormulaExpression Parse(int index, List<Token> tokenstream)
    {
        //Do something
        var binaryExpression = ParseBinaryOperation(opertorIndex, tokenstream);
        //Do more stuff
    }

    protected FormulaExpression ParseOperand(int index, List<Token> tokenstream)
    {
        //Do something
    }
}

The derived classes will have to implement a way to parse binary operations and can use the two other methods on the base class.

Since Rust does not support implementation inheritance, we will have to switch from inheritance to composition. As we know from Design Patterns by the gang of four, the composition equivalent of the Template Method pattern is the Strategy pattern.

The Problem Using a Strategy

Using a strategy pattern, the method ParseBinaryOperation is put onto a separate interface and objects implementing the interface are injected into the the base class. In C#, the base class might look as follows.

public class FormulaPaser
{
    private IBinaryOpParser _binaryOpParser;

    public FormulaPaser(IBinaryOpParser binaryOpParser)
    {
        _binaryOpParser = binaryOpParser
    }

    public FormulaExpression Parse(int index, List<Token> tokenstream)
    {
        //Do something
        var binaryExpression = ParseBinaryOperation(opertorIndex, tokenstream);
        var binaryExpression = 
        //Do more stuff
    }

    public FormulaExpression ParseOperand(int index, List<Token> tokenstream)
    {
        //Do something
    }

    private FormulaExpression ParseBinaryOperation(int index, List<Token> tokenstream){
        return _binaryOpParser.ParseBinaryOperation(opertorIndex, tokenstream);
    }
}

The main problem we face when porting this to Rust is that the implementation of IBinaryOpParser will want to access the methods on the base class. This can be achieved in different ways. We will start with the more natural approach coming from C# and modify it until it actually works in Rust. Then we approach the issue in a slightly different way, leading to a more elegant and versatile solution.

An Approach Inspired by other OOP Languages

In this approach, we will emulate the an abstract base class using a strategy pattern exactly as demonstrated in C# in the Problem section above. We will also use the same example as above.

To emulate the strategy interface, we set up a trait for the strategy structs.

pub trait BinaryOpParsingStrategy{
    fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option<FormulaContext>;
}

We use an Option here to deal with inadequate inputs. A better approach might be do use Result with appropriate errors, but we want to keep things simple here.

Then we set up the base struct as follows.

pub struct FormulaParser<T>{
    binary_op_parsing_strategy: T,
}

impl<T: BinaryOpParsingStrategy> FormulaParser<T>{
    pub fn new(binary_op_parsing_strategy: T) -> FormulaParser<T>{
        FormulaParser {binary_op_parsing_strategy}
    }

    pub fn parse(&self, index: usize, tokenstream: &[Token]) -> Option<FormulaContext>{
        //Do something
        let binary_expression = self.parse_binary_op(operator_index, tokenstream)?;
        //Do more stuff
    }

    fn parse_operand(&self, index: usize, tokenstream: &[Token]) -> Option<FormulaExpression>
    {
        //Do something
    }

    fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option<FormulaContext>{
        self.binary_op_parsing_strategy.parse_binary_op(operator_index, tokenstream)
    }
}

So far, everything looks rather straightforward. Now, we are left with how to set up the implementations of the BinaryOpParsingStrategy such that they are able to use the appropriate methods on the base struct.

However, before we come to this, we have to talk a bit about the necessary logistics on the side of the base struct.

Some Logistics

If you want to define strategies in a different file than the base struct, you will have to make the protected methods on it visible to the strategies. A simple way to do this is to put them on a trait. So, we will do this here.

pub trait FormulaParserProtectedInterface{
    fn parse(&self, index: usize, tokenstream: &[Token]) -> Option<FormulaContext>;
    fn parse_operand(&self, index: usize, tokenstream: &[Token]) -> Option<FormulaExpression>;
    fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option<FormulaContext>;
}

impl<T: BinaryOpParsingStrategy> FormulaParserProtectedInterface for FormulaParser<T>{
    fn parse(&self, index: usize, tokenstream: &[Token]) -> Option<FormulaContext>{
        self.parse(index, tokenstream)
    }

    fn parse_operand(&self, index: usize, tokenstream: &[Token]) -> Option<FormulaExpression>{
        self.parse_operand(index, tokenstream)
    }

    fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option<FormulaContext>{
        self.parse_binary_op(operator_index, tokenstream)
    } 
}

If you only want to define your strategies in the same file as the base struct, you can access all its methods anyway and do not require the trait.

A Naive Start

A typical way to make the base struct methods accessible in a language like C# is to simply store the base instance in a property on the strategy. So, let us start with that.

pub struct BinaryOpParser<T>{
    base_parser: T,
}

impl<T: FormulaParserProtectedInterface> BinaryOpParsingStrategy for BinaryOpParser<T>{
    fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option<FormulaContext>{
        //Do something
        let operand = self.base_parser.parse_operand(operand_index, tokenstream);
        //Do more stuff
    }
}

To allow other code to initialize this, we have little other choice than to do the following.

impl<T: FormulaParserProtectedInterface> BinaryOpParser<T>{
    pub fn new(base_parser: T) -> BinaryOpParser<T>{
        BinaryOpParser {base_parser}
    }
}

At first glance, everything looks fine. However, this setup has a fundamental flaw; it can never be instantiated. The base struct requires an instance of the strategy and the strategy an instance of the base class. This would also not have worked in C#.

Breaking the Cycle

In a language like C#, in which most types are nullable by default (at least until recently), we could have just not set the value of the base_parser field in the constructor and filled it in later. However, Rust does not allow this. Instead, we have to make it explicit that the field is optional.

pub struct BinaryOpParser<T>{
    base_parser: Option<T>,
}

This means that we have to unwrap the field whenever we use it.

impl<T: FormulaParserProtectedInterface> BinaryOpParsingStrategy for BinaryOpParser<T>{
    fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option<FormulaContext>{
        let base_parser = self.base_parser?;
        //Do something
        let operand = self.base_parser.parse_operand(operand_index, tokenstream);
        //Do more stuff
    }
}

Here, we bail out if the field containing the base struct is not initialized.

In exchange for this inconvenience we can instantiate the strategy as follows.

impl<T: FormulaParserProtectedInterface> BinaryOpParser<T>{
    pub fn new(base_parser: T) -> BinaryOpParser<T>{
        BinaryOpParser {None}
    }
}

Now, we need to enable the other code to initialize field holding the base struct. We will define a trait for this to streamline things and then implement it.

pub trait BaseStructInitializable<T>{
    fn initialize_base(&mut self, base: T);
}

impl<T: FormulaParserProtectedInterface> BaseStructInitializable<T> for BinaryOpParser<T>{
    fn initialize_base(&mut self, base: T){
        if self.base_parser.is_none(){
            self.base_parser = Some(base);
        }
    }
}

The setup above allows us to postpone initialization of field holding the base struct to after the strategy has been provided to the base struct. The natural place to perform the initialization is the base struct's construction method.

impl<T: BinaryOpParsingStrategy + BaseStructInitializable<Self>> FormulaParser<T>{
    pub fn new(binary_op_parsing_strategy: T) -> FormulaParser<T>{
        let parser = FormulaParser {binary_op_parsing_strategy};
        binary_op_parsing_strategy.initialize_base(parser);
        parser
    }
}

Although this would be reasonable in C#, this does not work in Rust; we will come to why next.

Rust is Different

Rust uses move semantics. So, the first reason why the approach in the previous section does not work is that binary_op_parsing_strategy has been moved into parser and can no longer be accessed when we initialize its field holding the base struct. As a fix, we might try the following.

impl<T: BinaryOpParsingStrategy + BaseStructInitializable<Self>> FormulaParser<T>{
    pub fn new(binary_op_parsing_strategy: T) -> FormulaParser<T>{
        let parser = FormulaParser {binary_op_parsing_strategy};
        parser.binary_op_parsing_strategy.initialize_base(parser);
        parser
    }
}

This also does not work. We cannot return parser from new since we have moved it into binary_op_parsing_strategy when we initialized the field holding the base struct.
This tells us that our naive approach will not work due to Rust's move semantics. So, what to do instead?

A Failed Attempt

At this point, you might consider using a reference to the base struct instead, like I did when I worked my way through this problem. Let us see why this cannot work.

Using references, we will have to change the strategy struct and the initialization a bit.

pub struct BinaryOpParser<a', T>{
    base_parser: Option<&'a T>,
}

pub trait BaseStructInitializable<'a, T>{
    fn initialize_base(&mut self, base: &'a T);
}

impl<'a, T: FormulaParserProtectedInterface> BaseStructInitializable<'a, T> for BinaryOpParser<T>{
    fn initialize_base(&mut self, base: &'a T){
        if self.base_parser.is_none(){
            self.base_parser = Some(base);
        }
    }
}

Then, we try to instantiate the base struct.

impl<T: BinaryOpParsingStrategy + BaseStructInitializable<Self>> FormulaParser<T>{
    pub fn new(binary_op_parsing_strategy: T) -> FormulaParser<T>{
        let parser = FormulaParser {binary_op_parsing_strategy};
        parser.binary_op_parsing_strategy.initialize_base(&parser);
        parser
    }
}

Here, the compiler will tell us why references do not work here. It tells us that the reference passed to initialize_base might not live long enough. But why is this the case?

To understand the compiler error you have to understand what references in Rust really are: they are essentially absolute pointers, but with safety applied. Consequently, they become stale once whatever they point to moves in memory. In our example, this will actually happen immediately when parser is returned from new. This is what the borrow checker guards against.

The nature of references means that any struct with a field containing a reference to itself must not move. In particular, such a struct cannot be returned from a function.

In safe code, you can really only define self-referential structs on the heap using explicit pointers and Pin, which prevents in-memory movement.

We will have to find another way to deal with our ownership problems.

Reference Counting to the Rescue

As we have seen two section ago, our naive approach does not work because we move ownership of the base struct to the strategy and, as we have seen in the previous section, we cannot use references to the base struct instead. So we will have to share ownership of the base struct.

A simple way to share ownership in Rust to use a reference counted box on the heap, i.e. an Rc<T>. Using it, our strategy looks as follows. (You have to import std::rc::Rc.)

pub struct BinaryOpParser<T>{
    base_parser: Option<Rc<T>>,
}

pub trait BaseStructInitializable<T>{
    fn initialize_base(&mut self, base: Rc<T>);
}

impl<T: FormulaParserProtectedInterface> BaseStructInitializable<T> for BinaryOpParser<T>{
    fn initialize_base(&mut self, base: Rc<T>){
        if self.base_parser.is_none(){
            self.base_parser = Some(base);
        }
    }
}

The usage of the base struct does not change at all as Rc implements DeRef. The only real change is in the base struct construction.

impl<T: BinaryOpParsingStrategy + BaseStructInitializable<Self>> FormulaParser<T>{
    pub fn new(binary_op_parsing_strategy: T) -> Rc<FormulaParser<T>>{
        let parser = FormulaParser {binary_op_parsing_strategy};
        let mut parser_wrapper = Rc::new(parser);
        let reference_for_strategy = Rc::clone(&parser_wrapper);
        parser_wrapper.binary_op_parsing_strategy.initialize_base(reference_for_strategy);
        parser_wrapper 
    }
}

Again, this will not work. The problem is that Rc cannot return a mutable reference to its contents and that Rust, by default, does not allow inner mutability for non-mutable references. This is very different to languages like C# that let you call any public method on any object you have a reference to.

Thankfully Rc's documentation tells you how to solve this.

Internal Mutability

To allow initialization of the field holding the base struct on the strategy after it has already been moved into the base struct behind the Rc, we have to explicitly tell Rust that the inner mutation is OK. This is done using the types Cell and RefCell.

Using RefCell in our example looks as follows. (You have to import std::cell::RefCell.)

pub struct BinaryOpParser<T>{
    base_parser: Option<Rc<RefCell<T>>>,
}

pub trait BaseStructInitializable<T>{
    fn initialize_base(&mut self, base: Rc<RefCell<T>>);
}

impl<T: FormulaParserProtectedInterface> BaseStructInitializable<T> for BinaryOpParser<T>{
    fn initialize_base(&mut self, base: Rc<RefCell<T>>){
        if self.base_parser.is_none(){
            self.base_parser = Some(base);
        }
    }
}

Then the base struct's construction will look as follows. (You have to import std::cell::RefMut.)

impl<T: BinaryOpParsingStrategy + BaseStructInitializable<Self>> FormulaParser<T>{
    pub fn new(binary_op_parsing_strategy: T) -> Rc<FormulaParser<RefCell<T>>>{
        let parser = FormulaParser {binary_op_parsing_strategy};
        let parser_cell = RefCell::new(parser);
        let parser_wrapper = Rc::new(parser_cell);
        let reference_for_strategy = Rc::clone(&parser_wrapper);
        {
            let mut strategy: RefMut<_> = parser_wrapper.borrow_mut();
            strategy.binary_op_parsing_strategy.initialize_base(reference_for_strategy);
        }
        parser_wrapper 
    }
}

Here, we introduce a scope to contain the inner mutability as tightly as possible.

This approach actually works. However, there is still a problem: the base struct and the strategy will never be deallocated. As it stands, the strategy holds a counted reference to the base struct and, since the strategy is kept alive by the base struct, the count will never be decremented to zero.

Breaking Another Cycle

It is rather straightforward to overcome the final hurdle that we currently have a reference cycle between the strategy and the base struct: we switch the reference from a strong Rc<T> to a weak Weak<T>. This is sensible since the strategy really no longer needs to do anything when the base struct has been dropped.

This leads us the the following setup for our strategy. (You have to import std::rc::Weak.)

pub struct BinaryOpParser<T>{
    base_parser: Option<Weak<RefCell<T>>>,
}

pub trait BaseStructInitializable<T>{
    fn initialize_base(&mut self, base: Weak<RefCell<T>>);
}

impl<T: FormulaParserProtectedInterface> BaseStructInitializable<T> for BinaryOpParser<T>{
    fn initialize_base(&mut self, base: Weak<RefCell<T>>){
        if self.base_parser.is_none(){
            self.base_parser = Some(base);
        }
    }
}

The base struct's construction will look as follows. (You have to import std::cell::RefMut.)

impl<T: BinaryOpParsingStrategy + BaseStructInitializable<Self>> FormulaParser<T>{
    pub fn new(binary_op_parsing_strategy: T) -> Rc<FormulaParser<RefCell<T>>>{
        let parser = FormulaParser {binary_op_parsing_strategy};
        let parser_cell = RefCell::new(parser);
        let parser_wrapper = Rc::new(parser_cell); 
let reference_for_strategy = Rc::downgrade(&parser_wrapper);
        {
            let mut strategy: RefMut<_> = parser_wrapper.borrow_mut();
            strategy.binary_op_parsing_strategy.initialize_base(reference_for_strategy);
        }
        parser_wrapper 
    }
}

The only real change is that we generate a weak pointer to pass to the strategy by calling downgrade instead of clone. This does not increase the reference count and will allow the base struct to be dropped once the reference count of the Rc we return from new reaches zero.

Finally, we have to amend the strategy's implementation because the base struct is now contained in multiple layers.

impl<T: FormulaParserProtectedInterface> BinaryOpParsingStrategy for BinaryOpParser<T>{
    fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option<FormulaContext>{
        let base_wrapper = self.base_parser.as_ref()?;
        let base_cell = base_wrapper.upgrade()?;
        let base_parser = base_cell.borrow();
        //Do something
        let operand = self.base_parser.parse_operand(operand_index, tokenstream);
        //Do more stuff
    }
}

At this point, we have a working method to emulate an abstract base class used to implement the template method. However, the current approach is still a bit cumbersome to the caller; we return an Rc<RefCell<T>> although the caller really wants a T.

Tidying Things Up

In order to make our initial approach work, we had to wrap the base struct in multiple layers, which is rather inconvenient to the caller. So, it makes sense to introduce a wrapper that hides away these implementation details.

I will just call the wrapper FormulaParserContainer to keep things consistent here. However, from the point of view of the caller, it would be more sensible to rename the original FormulaParser to FormulaParserImpl and reuse the original name for the wrapper.

pub struct FormulaParserContainer<T>{
   parser_impl: Rc<RefCell<FormulaParser<T>>>,
}

impl<T: BinaryOpParsingStrategy + BaseStructInitializable<Self>> FormulaParserContainer<T>{
    pub fn new(binary_op_parsing_strategy: T) -> FormulaParserContainer<T>{
        let parser_impl = FormulaParser::new(binary_op_parsing_strategy);
        FormulaParserContainer {parser_impl};
    }

    pub fn parse(&self, index: usize, tokenstream: &[Token]) -> Option<FormulaContext>{
        let inner = self.parser_impl.borrow();
        inner.parse(index, tokenstream)
    }
}

With this wrapper the caller does not need to worry about the layers we needed to add to make things work.

Note that our solution is not thread-safe since neither Rc<T> nor RefCell<T> is thread-safe. So, if you want to share the emulated abstract class between threads, you will have to look into the alternatives/ways to handle this in the module-level documentation for these two types.

Finally, before coming to the more elegant approach, note that we have basically recreated the equivalent of what we would have gotten in C#; the base struct lives on the heap, is referenced through a managed reference, the reference is optional and we have inner mutability. Apart from the fact that C# is garbage collected and, thus, does not really care about reference cycles, the only two differences are that we use static dispatch instead of dynamic dispatch and that we had to be explicit in Rust.

A more Elegant Solution

The approach we have slowly developed in the preceding sections has some caveats. In particular, the base struct has to live on the heap and writing the strategy emulating the derived class is a bit cumbersome because of all the layers around the reference to the base struct. All of this was a consequence of the desire to store some kind of reference to the base struct on the strategy in order to access the base struct's protected methods. But do we really need that?

Taking a small step back, we can see that we really don't. All it takes is to perform a small change to the strategy trait.

pub trait BinaryOpParsingStrategy<T: FormulaParserProtectedInterface>{
    fn parse_binary_op(&self, base: &T, operator_index: usize, tokenstream: &[Token])-> Option<FormulaContext>;
}

Here FormulaParserProtectedInterface is the trait we defined in the section Some Logistics to make the protected methods on the base struct available to the strategy emulating the derived class.

This change means that we no longer have to save the base struct on the strategy, allowing it to be very simple.

pub struct BinaryOpParser{}

impl<T: FormulaParserProtectedInterface> BinaryOpParsingStrategy<T> for BinaryOpParser{
    fn parse_binary_op(&self, base: &T, operator_index: usize, tokenstream: &[Token])-> Option<FormulaContext>{
        //Do something
        let operand = base.parse_operand(operand_index, tokenstream);
        //Do more stuff
    }
}

impl BinaryOpParser{
    pub fn new() -> BinaryOpParser{
        BinaryOpParser {}
    }
}

Since there is no more reference to the base struct, the construction of the base struct becomes much simpler.

impl<T: BinaryOpParsingStrategy<Self>> FormulaParser<T>{
    pub fn new(binary_op_parsing_strategy: T) -> FormulaParser<T>{
        FormulaParser {binary_op_parsing_strategy}
    }
}

Instead of providing the the base struct to the strategy here, we do it whenever the corresponding method is called. This leaves us with the following implementation of the base struct.

pub struct FormulaParser<T>{
    binary_op_parsing_strategy: T,
}

impl<T: BinaryOpParsingStrategy<Self>> FormulaParser<T>{
    pub fn parse(&self, index: usize, tokenstream: &[Token]) -> Option<FormulaContext>{
        //Do something
        let binary_expression = self.parse_binary_op(operator_index, tokenstream)?;
        //Do more stuff
    }

    fn parse_operand(&self, index: usize, tokenstream: &[Token]) -> Option<FormulaExpression>
    {
        //Do something
    }

    fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option<FormulaContext>{
        self.binary_op_parsing_strategy.parse_binary_op(self, operator_index, tokenstream)
    }
}

This approach is much simpler than the one holding a reference to the base struct as state on the strategy, but still allows to emulate an abstract base class. Moreover, we no longer need to store the base struct on the heap and do not have to worry about thread-safety as long as the base struct and strategies are otherwise thread-safe.

Virtual and Additional Methods

The two approaches above deal with the aspect of abstract methods on abstract base classes. They leave out two other aspects, virtual but not abstract methods and extensions with new methods. These require some more work, for which I will just mention some possible approaches.

The possibly simplest approach to emulate virtual methods is to treat them as abstract methods and provide the base implementations via some trait. That way, the derived class, i.e. the strategy, needs to implement the method, but can simply refer to the base implementation. This makes it rather explicit what is going on.

Alternatively one could return functions overriding the base implementations wrapped in an Option from the derived class.

To extend the abstract base class with new methods, a simple way is to use a different pattern, namely Decorator. To do this, one first needs to extract the base struct's public interface into a trait. Then we can define a decorator owning a base struct and let it forward all calls in its trait implementation to the base struct. This way it retains the base struct's functionality and is able to add more methods itself.

In principle, the decorator can change the implementation instead of just forwarding, but when doing this, one has to be aware that any internal calls to the public methods will not change. So, it is probably often best to just forward and deal with virtual and abstract methods via strategies.

To sum it up, to also implement the aspects of virtual methods and additional new methods one can combine the approachs described in the previous sections with a trait providing base implementations for the virtual methods and an additional decorator for the additional methods.