[rust-dev] Generative associated types (structs and enums)

Eduardo León abc.deaf.xyz at gmail.com
Sun Oct 12 02:44:15 PDT 2014


Hello:

First of all, I am really excited by the addition of associated types to
Rust as an experimental feature. This feature has the potential to reduce
much of the boilerplate that comes with the use of generic traits, which I
use extensively in my code.

However, in the exact form they are proposed:

*
https://github.com/rust-lang/rfcs/blob/d2c2f0f524df814d7b38f69311ab67f41c2ec3ec/active/0059-associated-items.md
* https://github.com/rust-lang/rfcs/issues/313

... associated types do not afford me much convenience. To illustrate this,
I will use an example. Consider the following generic trait:

> pub enum GetResult<I, E, L> {
>     Cont(E, I),
>     Done(L)
> }
>
> pub trait InputIterator<I, E, L> : Copy {
>     fn get(self, I) -> GetResult<I, E, L>;
> }

This trait is implemented for some really scary types. One of the tamest
implementations in my code is:

> pub struct Zip<L, R> { left: L, right: R }
>
> pub enum ZipInputLeftovers<LI, LE, LL, RI, RE, RL> {
>     MoreL(LE, LI, RL),
>     MoreR(LL, RE, RI),
>     Neither(LL, RL)
> }
>
> impl<LI, LE, LL, L: InputIterator<LI, LE, LL>
>      RI, RE, RL, R: InputIterator<RI, RE, RL>>
>
>     InputIterator< (LI, RI), (LE, RE),
>         ZipInputLeftovers<LI, LE, LL, RI, RE, RL> >
>     for Zip<L, R> {
>
>     fn get(self, (li, ri): (LI, RI)) ->
>         GetResult< (LI, RI), (LE, RE),
>             ZipInputLeftovers<LI, LE, LL,
>                               RI, RE, RL> > {
>         match (self.left.get(li), self.right.get(ri)) {
>             // ...
>         }
>     }
> }

With associated types, this code can be rewritten this way:

> pub trait InputIterator : Copy {
>     type Iterator;
>     type Element;
>     type Leftovers;
>
>     fn get(self, I) -> Get<Iterator, Element, Leftovers>;
> }
>
> impl<L: InputIterator, R: InputIterator> InputIterator for Zip<L, R> {
>     type Iterator = (L::Iterator, R::Iterator);
>     type Element = (L::Element, R::Element);
>     type Leftovers = ZipInputLeftovers<
>         L::Iterator, L::Element, L::Leftovers,
>         R::Iterator, R::Element, R::Leftovers >;
>
>     fn get(self, (li, ri): Iterator) ->
>         GetResult<Iterator, Element, Leftovers> {
>         match (self.left.get(li), self.right.get(ri)) {
>             // ...
>         }
>     }
> }

There are two remaining annoyances with this code:

1. We still have generics with long parameter lists: GetResult has 3 type
parameters, ZipInputLeftovers has 6 type parameters, other fancier
iterators have associated types with more than 10 (!) type parameters.

2. The type system permits the construction of nonsensical values, such as
Cont("hello", "world") [of type GetResult<&'static str, &'static str, T>]
or MoreL("ok", "now", "bye") [of type ZipInputLeftovers<&'static str,
&'static str, S, T, U, &'static str>]. In this case, the error is that the
type of "world" and "now", &'static str, is not a meaningful iterator type.

I propose that the aforementioned issues can be avoided by allowing
generative type definitions (that is, structs and enums) inside of traits
and impls, rather than only allowing type synonyms:

> pub trait InputIterator : Copy {
>     type Iterator;
>     type Element;
>     type Leftovers;
>
>     enum Result {
>         Cont(Element, Iterator),
>         Done(Leftovers)
>     }
>
>     fn get(self, Iterator) -> Result;
> }
>
> impl<L: InputIterator, R: InputIterator> InputIterator for Zip<L, R> {
>     type Iterator = (L::Iterator, R::Iterator);
>     type Element = (L::Element, R::Element);
>
>     enum Leftovers {
>         MoreL(L::Element, L::Iterator, R::Leftovers),
>         MoreR(L::Leftovers, R::Element, R::Iterator),
>         Neither(L::Leftovers, R::Leftovers)
>     };
>
>     fn get(self, (li, ri): Iterator) -> Result {
>         match (self.left.get(li), self.right.get(ri)) {
>             // ...
>         }
>     }
> }

The benefits of this change are tangible:

1. No more humongous generic parameter lists.

2. No nonsensical Result or Leftovers values can be constructed.

An important observation is that overriding generative associated type
definitions should be disallowed. If we allow InputIterator implementations
to override the Result type, then we cannot pattern match on Result's
constructors from external code:

> pub struct Transform<I, O> { input: I, output: O }
>
> impl<I: Source, O: Sink> Transform<I, O> {
>     pub type Mapping = |I::Element| -> O::Element;
>
>     pub enum Result {
>         StopI(I::Leftovers, O::Iterator),
>         StopO(I::Iterator, O::Leftovers)
>     }
>
>     pub fn exec(self, f: Mapping, i: I::Iterator, o: O::Iterator) ->
Result {
>         match self.input.get(i) {
>             I::Done(l) => StopI(l, o),
>             I::Cont(e, i) =>
>                 match self.output.put(o, f(e)) {
>                     O::Done(l) => StopO(i, l),
>                     O::Cont(o) => self.exec(f, i, o)
>                 }
>         }
>     }
> }

Do you guys think associated structs and enums could make it into the
language?

All these code snippets are taken from
https://github.com/eduardoleon/rust-stl/tree/master/src/stream .

--
Eduardo León
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20141012/8b11ca7b/attachment.html>


More information about the Rust-dev mailing list