#generic #content #traits #ownership #cow #level #framework

no-std static-cow

Cow at the type level: a framework of traits for writing types that are generic over ownership of their contents

3 unstable releases

0.2.0 Jan 9, 2023
0.1.1 Jan 3, 2023
0.1.0 Jan 2, 2023

#2758 in Rust patterns


Used in im-rope

Apache-2.0 WITH LLVM-exception

29KB
393 lines

static-cow

This Rust crate provides a framework of traits for writing types that are generic over ownership of their contents, by lifting Cow to the type level so that whether a particular object is borrowed or owned can be specified through a generic type parameter.

Mascot

Documentation

See API docs on docs.rs.

License

This project licensed under the Apache License 2.0 with LLVM exception. Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in static-cow by you, shall be licensed as Apache 2.0 with LLVM exception, without any additional terms or conditions.


lib.rs:

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

Mascot

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 {
    type Owning;
    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.

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 ToOwning + 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>, you can declare that field as field: S and let S be a generic parameter S: StaticCow<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. ToOwningplaces no constraints onOwning, 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 beTor might beT::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:

  1. It can give you either a T or a T::Owning, and tells you which.

  2. 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<S, E> {
    inner: S,
    index: usize,
    _phantom: PhantomData<[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<[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 parameter E appear somewhere in the struct's fields.

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

impl<S, E> ToOwning for FlexIter<S, E>
where
    S: ToOwning,
{
    type Owning = FlexIter<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<S, E> IntoOwning for FlexIter<S, E>
where
    S: IntoOwning,
{
    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 these implementations are complely rote: we give an Owning type which is the same as Self but with S replaced by S::Owning, and to_owning and into_owning methods which simply apply the same method to each of their fields.

Now we give a constructor for a borrowing iterator, which realizes StaticCow<[E]> with Borrowed<'b, [E]>.

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<S, E> Iterator for FlexIter<S, E>
where
    E: Clone,
    S: StaticCow<[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);
    }
}

Running this, we get the expected result:

Borrowing:
5
4
Owning:
3
2
1

This example is also available as examples/flex_iter.rs in the sources of this crate.

No runtime deps