Crate static_cow

Expand description

This crate provides a framework of traits for writing types that are generic over ownership of their contents.

API Overview

`ToOwning` and `IntoOwning`

ToOwning and IntoOwning are the most general traits provided by this crate, and are the ones that you will implement on your own types. ToOwning is a generalization of std::borrow::ToOwned:

pub trait ToOwning<'o> {
    type Owning: 'o;
    fn to_owning(&self) -> Self::Owning;
}

Unlike ToOwned, it doesn’t require that Owning: Borrow<Self>. Hence ToOwning represents a type that can be converted into some version of itself which owns its contents, but which does not necessarily let you get a reference to the original borrowing type back out from the owning one.

The lifetime parameter 'o is a bound on the lifetime of the owning type. In most circumstances, this can be 'static, unless the owning type still contains some resources which are borrowed. Wherever you see a lifetime parameter named 'o anywhere in this crate documentation, you can mentally substitute 'static unless you are doing something very unusual.

ToOwning has a blanket implementation for T where T : ToOwned + ?Sized. The blanket implementation does the obvious thing of letting Owning = Owned and to_owning = to_owned.

IntoOwning, then is self-explanatory from its declaration:

pub trait IntoOwning<'o>: ToOwning<'o> + Sized {
    fn into_owning(self) -> Self::Owning;
}

IntoOwning has a blanket implementation for T where T : Clone, which makes into_owning the identity function. Therefore, if your type already implements Clone, you get an IntoOwning implementation automatically. If you implement IntoOwning manually, you cannot implement Clone.

User-defined types which implement ToOwning and IntoOwning generally should just call .to_owning() and .into_owning() on each of their fields. Eventually there will be derive macros for this, but I haven’t written them yet.

`StaticCow`

StaticCow, this crate’s namesake, is std::borrow::Cow lifted to the type level. While Cow is an enum, StaticCow is a trait. While Cow::Borrowed and Cow::Owned are enum variants, this crate’s Borrowed and Owned are tuple structs which implement StaticCow (so also does Cow). So instead of having a struct with a field field: Cow<'a, B>, where B: ''o (remember, think “usually 'static” when you see 'o), you can declare that field as field: S and let S be a generic parameter S: StaticCow<'a, 'o, B>. Then, wherever the ownedness of S is known at compile-time, the compiler can generate an appropriately-specialized version of the function.

Like Cow, StaticCow requires B : ToOwned, which allows it to have Deref<Target=B> for a supertrait. IntoOwning is another supertrait of StaticCow.

`Idempotent`

Using Idempotent as a bound allows you to be generic over types that implement IntoOwning but not ToOwned.

StaticCow<B> has Deref<Target=B> as a supertrait, so you can do anything with a StaticCow<B> that you can do with a &B. However, in order to provide this supertrait, its implementations require that B : ToOwned so that they can rely on having B::Owned : Borrow<B>.

Idempotent has weaker requirements, so its capabilities are necessarily weaker as well, and it does not inherit from Deref. ToOwning<'o> places no constraints other than 'o on Owning, which means that as far as the type system is concerned, .into_owning() is just a completely arbitrary conversion. So, you can’t do anything useful with a type that might be T or might be T::Owning but you don’t know which, because they don’t promise to have any traits in common.

Idempotent puts back just enough information that it can be a useful bound:

It can give you either a T or a T::Owning, and tells you which.
It constrains T such that T::Owning::Owning = T::Owning. This means that you can call into_owning() on it as many times as you please and it can still give you either a T or a T::Owning.

Idempotent<T> is implemented by Change<T>, which holds a T; Keep<T>, which holds a T::Owning; and by ChangeOrKeep<T> which might hold either, determined at runtime. Calling .to_owning() or .into_owning() on an Idempotent<T> always gives a Keep<T>.

Example

In this example, we’ll implement a slice iterator which returns the slice’s elements in reverse. Initially, it’ll borrow the slice and clone its elements when returning them. But, it will implement IntoOwning, so that at any time during iteration you can change it into an iterator which owns a Vec. It will then pop the elements it returns off the end of the Vec, without cloning them.

For starters, we’ll declare our flexible iterator:

struct FlexIter<'a, S, E> {
    inner: S,
    index: usize,
    _phantom: CowPhantom<'a, [E]>,
}

E is the type of the slice’s elements. And although the constraint doesn’t appear in the struct declaration, S will be an implementation of StaticCow<'a, 'o, [E]>. Concretely, S will be either Borrowed<'b, [E]>, which wraps a &'b [E], or it will be Owned<[E]>, which wraps a Vec<E>. index is one greater than the index of the next element we’ll return, and _phantom is a zero-sized object which has to be there to satisfy the typechecker by having the parameters 'a and E appear somewhere in the struct’s fields.

Now we’ll create ToOwning and IntoOwning instances for FlexIter.

impl<'a, 'o, S, E> ToOwning<'o> for FlexIter<'a, S, E>
where
    S: ToOwning<'o>,
    E : 'o,
{
    type Owning = FlexIter<'o, S::Owning, E>;
 
    fn to_owning(&self) -> Self::Owning {
        FlexIter {
            inner: self.inner.to_owning(),
            index: self.index.to_owning(),
            _phantom: self._phantom.to_owning()
        }
    }
}
 
impl<'a, 'o, S, E> IntoOwning<'o> for FlexIter<'a, S, E>
where
    S: IntoOwning<'o>,
    E: 'o
{
    fn into_owning(self) -> Self::Owning {
        FlexIter {
            inner: self.inner.into_owning(),
            index: self.index.into_owning(),
            _phantom: self._phantom.into_owning()
        }
    }
}

You can see that the method implementations are completely rote, but all these lifetimes flying around may be confusing. 'o is a lifetime bound on E, the type of the slice’s elements. If the elements are just data, say, u32, then 'o can be 'static. But if we have a slice full of references, say, &'x u32, then 'o is bounded by 'x. 'a is a lifetime bound on the slice we’re iterating over. So, if what we’re given is a &'b [E], then 'a is bounded by 'b. But once we call to_owned() on the slice, which gives us a Vec<E>, now 'a is bounded only by 'o.

Thus we can understand the implementation constraints and the type declaration for Owning. We need an S which implements ToOwning<'o>, and an E which can live up to 'o. Concretely, S will be Borrowed<'a, [E]>, which is a transparent wrapper around &'a [E]. This type does in fact implement ToOwning<'o>, handing us back an Owned<'o, [E]> which is a transparent wrapper around [E]::Owned, i.e., Vec<E>. Given that these constraints are satisfied, we can turn a FlexIter<'a, S, E> into a FlexIter<'o, S::Owning, E>. Concretely, supposing E is u32 so 'o is 'static, we can turn a FlexIter<'a, Borrowed<'a, [u32]>, u32> into a FlexIter<'static, Owned<'static, [u32]>, u32>.

If you understood that, then you should have no problem understanding the constructor for a borrowing FlexIter:

impl<'b, E> FlexIter<'b, Borrowed<'b, [E]>, E> {
    fn new(slice: &'b [E]) -> FlexIter<'b, Borrowed<'b, [E]>, E> {
        FlexIter {
            inner: Borrowed(slice),
            index: slice.len(),
            _phantom: CowPhantom::default(),
        }
    }
}

And now we can implement Iterator:

impl<'a, 'o, S, E> Iterator for FlexIter<'a, S, E>
where
    E: 'o + Clone,
    S: StaticCow<'a, 'o, [E]>,
{
    type Item = E;
    fn next(&mut self) -> Option<Self::Item> {
        // This is here to show that we can also access `inner` generically
        // through its `Deref<Target=[E]>` implementation, without having to 
        // match on `mut_if_owned()`.
        assert!(self.index <= self.inner.len());

        match self.inner.mut_if_owned() {
            // We're borrowing the slice, so we have to work inefficiently
            // by cloning its elements before we return them.
            MutIfOwned::Const(slice) => {
                if self.index == 0 {
                    None
                } else {
                    self.index -= 1;
                    Some(slice[self.index].clone())
                }
            }
            // We own the slice as a `Vec`, so we can pop elements off of it
            // without cloning.
            MutIfOwned::Mut(vec) => {
                // It's necessary to make sure we first truncate the vector
                // to `index`, because we may have already started iterating
                // before `.into_owned()` was called, and this may be our
                // first time calling `.next()` since we took ownership. Of
                // course we could have had our `into_owned` implementation
                // do this instead of doing it here.
                vec.truncate(self.index);
                let ret = vec.pop()?;
                self.index -= 1;
                Some(ret)
            }
        }
    }
}

And now let’s see it in action:

fn main() {
    let numbers = vec![1, 2, 3, 4, 5];
    let mut borrowing_iter = FlexIter::new(numbers.borrow());

    println!("Borrowing:");
    println!("{}", borrowing_iter.next().unwrap());
    println!("{}", borrowing_iter.next().unwrap());

    let owning_iter = borrowing_iter.into_owning();
    std::mem::drop(numbers);

    println!("Owning:");
    for item in owning_iter {
        println!("{}", item);
    }
}