Using Option<T> as associated type in trait that returns reference to it

Question

I have a trait with an associated type Value, and two methods. One returns &Self::Value and the other receives Self::Value. This trait is implemented for several types, but I want to implement it for one type in particular where type Value = Option<...>. This creates a problem, as demonstrated below (playground):

pub trait PersistedContainer {
    type Value;

    fn get_persisted(&self) -> &Self::Value;

    fn set_persisted(&mut self, value: Self::Value);
}

pub struct SelectState<Item> {
    items: Vec<Item>,
    selected: Option<usize>,
}

impl<Item: PartialEq> PersistedContainer for SelectState<Item> {
    type Value = Option<Item>;

    fn get_persisted(&self) -> &Self::Value {
        self.selected.map(|index| &self.items[index])
    }

    fn set_persisted(&mut self, value: Self::Value) {
        if let Some(value) = &value {
            self.selected = self.items.iter().position(|item| item == value);
        }
    }
}

Compiling this results in this error:

error[E0308]: mismatched types
  --> src/lib.rs:18:9
   |
17 |     fn get_persisted(&self) -> &Self::Value {
   |                                ------------ expected `&Option<Item>` because of return type
18 |         self.selected.map(|index| &self.items[index])
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected `&Option<Item>`, found `Option<&Item>`
   |
   = note: expected reference `&Option<_>`
                   found enum `Option<&_>`

Ideally we want to return Option<&Item> from get_persisted, but the trait signature forces us to return &Option<Item> instead. The problem is I can't create an &Option<Item> because I don't have an Option<Item> anywhere.

Some solutions I've considered:

Clone the item and return it

impl<Item: Clone + PartialEq> PersistedContainer for SelectState<Item> {
    type Value = Option<Item>;

    fn get_persisted(&self) -> &Self::Value {
        &self.selected.map(|index| self.items[index].clone())
    }

    fn set_persisted(&mut self, value: Self::Value) {
        if let Some(value) = &value {
            self.selected = self.items.iter().position(|item| item == value);
        }
    }
}

This doesn't work because it's trying to return a reference to a temporary value. I'd like to avoid the clone anyway.

error[E0515]: cannot return reference to temporary value
  --> src/lib.rs:18:9
   |
18 |         &self.selected.map(|index| self.items[index].clone())
   |         ^----------------------------------------------------
   |         ||
   |         |temporary value created here
   |         returns a reference to data owned by the current function

Change the associated type to be a GAT

Rather than return &Self::Value, have Self::Value be a reference to begin with, like so:

pub trait PersistedContainer {
    type Value<'this> where Self: 'this;

    fn get_persisted(&self) -> Self::Value<'_>;

    fn set_persisted(&mut self, value: Self::Value<'_>);
}

pub struct SelectState<Item> {
    items: Vec<Item>,
    selected: Option<usize>,
}

impl<Item: Clone + PartialEq> PersistedContainer for SelectState<Item> {
    type Value<'this> = Option<&'this Item> where Self: 'this;

    fn get_persisted(&self) -> Self::Value<'_> {
        self.selected.map(|index| &self.items[index])
    }

    fn set_persisted(&mut self, value: Self::Value<'_>) {
        if let Some(value) = value {
            self.selected = self.items.iter().position(|item| item == value);
        }
    }
}

This compiles, but the problem is set_persisted is now receiving Option<&Item> instead of Option<Item>. The caller of set_persisted has an owned version of Self::Value and can't generically produce the reference version. That leads us to the next solution:

Two associated types

pub trait PersistedContainer {
    type GetValue<'this> where Self: 'this;
    type SetValue;

    fn get_persisted(&self) -> Self::GetValue<'_>;

    fn set_persisted(&mut self, value: Self::SetValue);
}

pub struct SelectState<Item> {
    items: Vec<Item>,
    selected: Option<usize>,
}

impl<Item: Clone + PartialEq> PersistedContainer for SelectState<Item> {
    type GetValue<'this> = Option<&'this Item> where Self: 'this;
    type SetValue = Option<Item>;

    fn get_persisted(&self) -> Self::GetValue<'_> {
        self.selected.map(|index| &self.items[index])
    }

    fn set_persisted(&mut self, value: Self::SetValue) {
        if let Some(value) = &value {
            self.selected = self.items.iter().position(|item| item == value);
        }
    }
}

This works, but requires implementors to specify essentially the same type twice. Since this will be in a library crate, I want to keep the API as clean as possible.

What I think I need is some trait that maps T -> &T and Option<T> to Option<&T> but haven't found anything online about that. Am I missing something or can this just not be expressed in the type system?

Answer 1

It's impossible to efficiently return &Option<Item> from this sort of method

Unfortunately, &Option<Item> isn't a sort of value that this sort of method can reasonably return, and the reason is to do with the memory layout of your program, and what a reference actually is.

Your container is storing your Item values in a Vec. As such, depending on the type of Item, the Vec might be storing the Item values tightly packed with no room between them. For example, u64 is one possibility for Item that would be stored like that: the first u64 would take up the first 8 bytes of the vector's allocation, the second u64 would take up the next 8 bytes, and so on. With methods that return references with the same lifetime as self (like get_persisted), what the method is doing is to return a reference directly into the relevant part of the Vec. For example, say that you were writing an impl for a different type, that just returned an &Item; the reference could point directly at the &Item within the vector.

There are a couple of different ways that Rust can implement Option<Item>, depending on the type of Item. However, for some types, the implementation of Option<Item> is done using a prefix that's placed next to the value. For example, Option<u64> is internally implemented using a structure that, if it were implemented directly in Rust rather than internally within the compiler, would look something like this:

struct OptionU64 {
    is_some: bool,
    value: MaybeUninit<u64> // initialised if and only if is_some
}

The reason you're having trouble returning an &Option<Item>, then, is that in order to return a Some value, the compiler would have to find a block of memory that had the "this value is a Some" marker in the right place of memory relative to the actual value, and return a reference to that – but because the elements of the Vec are tightly packed in memory, that isn't possible because the memory immediately before the value is another value, rather than the extra information that Option needs to specify whether the value is Some or None. Just because a value item exists in memory doesn't mean that the value Some(item) exists in memory (normally in order to be able to create a Some value, you have to move it into the Option).

(As a side note, it would be possible to implement this inefficiently, by storing an array of Vec<Option<Item>> for which all the elements were Some – that would mean an Option<Item> really would exist in memory that you could return a reference to. But that would be a bad idea because, for many choices of Item, it could double the size of the vector.)

There is no transformation on types that translates T to &T but Option<T> to Option<&T>

Such a transformation couldn't possibly work for all values of T: if you take T to be Option<U>, then it would need to translate Option<U> to &Option<U>, contradicting the assumption that it would transform Option<T> to Option<&T>.

Fortunately, there is a standard way to handle trait methods that might be fallible with some types and infallible with other types

If you have a trait method that needs to be able to return a failure with some types, but always succeeds when other types are used, this can be done using a Result, with an associated type for the error case:

pub trait PersistedContainer {
    type Value;
    type Error;

    fn try_get_persisted(&self) -> Result<&Self::Value, Self::Error>;

    fn set_persisted(&mut self, value: Self::Value);
}

To implement this on SelectState, the most common approach in libraries would be to create a trivial struct that represents a failure, and use that as the Error return:

// implement whatever traits on `NotSelected` seem reasonable
pub struct NotSelected;

impl<Item: PartialEq> PersistedContainer for SelectState<Item> {
    type Value = Item;
    type Error = NotSelected;

    fn try_get_persisted(&self) -> Result<&Self::Value, Self::Error> {
        match self.selected {
            Some(index) => Ok(&self.items[index]),
            None => Err(NotSelected)
        }
    }

    fn set_persisted(&mut self, value: Self::Value) {
        self.selected = self.items.iter().position(|item| *item == value);
    }
}

Note that doing things this way, in addition to having a clear try_get_persisted, also simplifies set_persisted – it's now always being passed a true value, so users of your library don't need to wrap it in Some every time.

For implementations that always succeed, rather than having an error case, you can use std::convert::Infallible (or equivalently core::convert::Infallible if writing a #[no_std] library). For example, here's how you'd implement PersistedContainer on Box:

impl<Item> PersistedContainer for Box<Item> {
    type Value = Item;
    type Error = std::convert::Infallible;
    
    fn try_get_persisted(&self) -> Result<&Self::Value, Self::Error> {
        Ok(&*self)
    }

    fn set_persisted(&mut self, value: Self::Value) {
        **self = value;
    }
}

This mechanism is used by the standard library in such fundamental traits as TryFrom. Unfortunately, it isn't fully implemented yet; get_persisted (for the types that support it) should eventually be expressible as try_get_persisted(…).into_ok() but .into_ok() is unstable and doesn't work well with the current definition of Infallible. So in order to work with current Rust, you would probably need to implement it yourself. Here's what the implementation of GetPersisted looks like (which would have to be in a separate trait, because although all persisted containers support try_get_persisted, not all support an infallible get_persisted):

pub trait GetPersisted {
    type Value;
    fn get_persisted(&self) -> &Self::Value;
}
impl<Container: PersistedContainer<Error=std::convert::Infallible>> GetPersisted for Container {
    type Value = <Container as PersistedContainer>::Value;
    fn get_persisted(&self) -> &Self::Value {
        match self.try_get_persisted() {
            Ok(v) => v,
            Err(err) => match err {}
        }
    }
}

My conclusions here are: although it's possible to write this sort of thing correctly, Rust isn't really up to the task of making it easy just yet. Fortunately, it's already been recognised as a problem and work is being done to fix it (e.g. the match block I wrote above for converting a Result<T, Infallible> into a T really should be part of the standard library, and in fact there are current plans to add something like that to the standard library); it's just that the implementation isn't in a usable state yet.

Side note: why do you need a single trait anyway?

One thing that strikes me about PersistedContainer is that you have, in effect, created a trait that needs two different APIs. On most types, your trait stores a T and gets an &T – that's something that generic code could reasonably abstract over. However, on SelectState, your code (as you were trying to write it) stores a T but requires the argument to be supplied as an Option<T> that is always Some, and gets an Option<&T>. Those are two substantially different APIs, and that would likely mean that it would be impossible to write code that worked generically with any PersistedContainer.

If the two different APIs are acceptable for your use-case, then there isn't much point in trying to fit both types into a single trait – you might as well use PersistedContainer only in cases where get_persisted is infallible, and write code to use SelectState directly in cases where you want its API instead. (After all, your code would have to know whether it was dealing with a SelectState or not already, in order to know whether it needed to handle an Option wrapper or not.)

If the two different APIs aren't acceptable – i.e. code using the trait does need to be able to handle all PersistedContainers in the same way – you will have to use the Result technique in the previous section in order to create something that does work generically, but that will run into the issues mentioned above in which the relevant parts of the standard library aren't fully stable (or even fully implemented) yet.

It's also quite possible that you don't need a trait here at all – if there isn't any use in being able to write generic code that works with different types of PersistedContainers, then using a trait isn't useful and will just tend to confuse matters. What you can do instead is to simply give each type an inherent implementation of get_persisted and set_persisted, defined in the way that makes the most sense for that type; the repeated names will make it easy for the user to find the correct method, and that's probably the only connection between the methods you need. (As an example from the standard library, Option::map and Result::map are clearly in some sense the same function applied to two different types, and their names are the same in order to make the connection clearer, but they don't belong to any sort of trait and you can't write code that can generically map over either an Option or a Result.)