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](https://adventofcode.com/2020/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. ```csharp public abstract class FormulaPaserBase { protected abstract FormulaExpression ParseBinaryOperation(int index, List tokenstream); public FormulaExpression Parse(int index, List tokenstream) { //Do something var binaryExpression = ParseBinaryOperation(opertorIndex, tokenstream); //Do more stuff } protected FormulaExpression ParseOperand(int index, List 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](https://en.wikipedia.org/wiki/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. ```csharp public class FormulaPaser { private IBinaryOpParser _binaryOpParser; public FormulaPaser(IBinaryOpParser binaryOpParser) { _binaryOpParser = binaryOpParser } public FormulaExpression Parse(int index, List tokenstream) { //Do something var binaryExpression = ParseBinaryOperation(opertorIndex, tokenstream); var binaryExpression = //Do more stuff } public FormulaExpression ParseOperand(int index, List tokenstream) { //Do something } private FormulaExpression ParseBinaryOperation(int index, List 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. ```rust pub trait BinaryOpParsingStrategy{ fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option; } ``` 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. ```rust pub struct FormulaParser{ binary_op_parsing_strategy: T, } impl FormulaParser{ pub fn new(binary_op_parsing_strategy: T) -> FormulaParser{ FormulaParser {binary_op_parsing_strategy} } pub fn parse(&self, index: usize, tokenstream: &[Token]) -> Option{ //Do something let binary_expression = self.parse_binary_op(operator_index, tokenstream)?; //Do more stuff } fn parse_operand(&self, index: usize, tokenstream: &[Token]) -> Option { //Do something } fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option{ 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. ```rust pub trait FormulaParserProtectedInterface{ fn parse(&self, index: usize, tokenstream: &[Token]) -> Option; fn parse_operand(&self, index: usize, tokenstream: &[Token]) -> Option; fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option; } impl FormulaParserProtectedInterface for FormulaParser{ fn parse(&self, index: usize, tokenstream: &[Token]) -> Option{ self.parse(index, tokenstream) } fn parse_operand(&self, index: usize, tokenstream: &[Token]) -> Option{ self.parse_operand(index, tokenstream) } fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option{ 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. ```rust pub struct BinaryOpParser{ base_parser: T, } impl BinaryOpParsingStrategy for BinaryOpParser{ fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option{ //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. ```rust impl BinaryOpParser{ pub fn new(base_parser: T) -> BinaryOpParser{ 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. ```rust pub struct BinaryOpParser{ base_parser: Option, } ``` This means that we have to unwrap the field whenever we use it. ```rust impl BinaryOpParsingStrategy for BinaryOpParser{ fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option{ 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. ```rust impl BinaryOpParser{ pub fn new(base_parser: T) -> BinaryOpParser{ 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. ```rust pub trait BaseStructInitializable{ fn initialize_base(&mut self, base: T); } impl BaseStructInitializable for BinaryOpParser{ 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. ```rust impl> FormulaParser{ pub fn new(binary_op_parsing_strategy: T) -> FormulaParser{ 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. ```rust impl> FormulaParser{ pub fn new(binary_op_parsing_strategy: T) -> FormulaParser{ 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. ```rust pub struct BinaryOpParser{ 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{ 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. ```rust impl> FormulaParser{ pub fn new(binary_op_parsing_strategy: T) -> FormulaParser{ 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`. Using it, our strategy looks as follows. (You have to import `std::rc::Rc`.) ```rust pub struct BinaryOpParser{ base_parser: Option>, } pub trait BaseStructInitializable{ fn initialize_base(&mut self, base: Rc); } impl BaseStructInitializable for BinaryOpParser{ fn initialize_base(&mut self, base: Rc){ 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. ```rust impl> FormulaParser{ pub fn new(binary_op_parsing_strategy: T) -> Rc>{ 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`.) ```rust pub struct BinaryOpParser{ base_parser: Option>>, } pub trait BaseStructInitializable{ fn initialize_base(&mut self, base: Rc>); } impl BaseStructInitializable for BinaryOpParser{ fn initialize_base(&mut self, base: Rc>){ 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`.) ```rust impl> FormulaParser{ pub fn new(binary_op_parsing_strategy: T) -> Rc>>{ 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` to a weak `Weak`. 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`.) ```rust pub struct BinaryOpParser{ base_parser: Option>>, } pub trait BaseStructInitializable{ fn initialize_base(&mut self, base: Weak>); } impl BaseStructInitializable for BinaryOpParser{ fn initialize_base(&mut self, base: Weak>){ 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`.) ```rust impl> FormulaParser{ pub fn new(binary_op_parsing_strategy: T) -> Rc>>{ 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. ```rust impl BinaryOpParsingStrategy for BinaryOpParser{ fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option{ 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>` 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. ```rust pub struct FormulaParserContainer{ parser_impl: Rc>>, } impl> FormulaParserContainer{ pub fn new(binary_op_parsing_strategy: T) -> FormulaParserContainer{ let parser_impl = FormulaParser::new(binary_op_parsing_strategy); FormulaParserContainer {parser_impl}; } pub fn parse(&self, index: usize, tokenstream: &[Token]) -> Option{ 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` nor `RefCell` 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. ```rust pub trait BinaryOpParsingStrategy{ fn parse_binary_op(&self, base: &T, operator_index: usize, tokenstream: &[Token])-> Option; } ``` 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. ```rust pub struct BinaryOpParser{} impl BinaryOpParsingStrategy for BinaryOpParser{ fn parse_binary_op(&self, base: &T, operator_index: usize, tokenstream: &[Token])-> Option{ //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. ```rust impl> FormulaParser{ pub fn new(binary_op_parsing_strategy: T) -> FormulaParser{ 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. ```rust pub struct FormulaParser{ binary_op_parsing_strategy: T, } impl> FormulaParser{ pub fn parse(&self, index: usize, tokenstream: &[Token]) -> Option{ //Do something let binary_expression = self.parse_binary_op(operator_index, tokenstream)?; //Do more stuff } fn parse_operand(&self, index: usize, tokenstream: &[Token]) -> Option { //Do something } fn parse_binary_op(&self, operator_index: usize, tokenstream: &[Token])-> Option{ 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.

mdoerner

Emulating abstract base classes in Rust

Join Our Newsletter. No Spam, Only the good stuff.