Making lending iterator generic over type it yields

help
1

I have a single "god object" struct which does all the processing. It used to have just lots of methods exposed as its API. I've decided to switch it to a set of "proxy" objects for public API. Each of those proxy objects contains reference to main struct, and many of its methods just execute now-hidden main struct methods. It allowed me to maintain a set of guarantees better, simplify error structure, etc, even if it follows OOP API look and feel, with rust being not the best tool for that.

I already implemented all the key parts. When reduced to basics, it looks like this. However, I have lots of proxy object types, split into several groups. For one of such groups, I'd like to generalize iterator implementation over proxy type it returns, since group is relatively large. But no matter how I try, I fail, likely due to not understanding all the limits and possibilities of lifetime notation.

To generalize over a set of proxies, I introduce a trait New. Its only method doesn't do anything but create proxy structs from passed arguments, which are the same for proxies within the group I want to generalize over. But, I can't find a way to tie produced item to 'lend lifetime of iterator. So far I've been running into "lifetime may not live long enough" (like in this example), trait method declaration incompatibility and a few other errors (tried GATs, GATs + implicit limits).

How do I proceed, to let iterator consume any proxy type which implements New?

2 
trait New<'a> {
    fn new_new(main: &'a mut Main, key: i32) -> Self;
}

impl<'this, T> LendingIterator for GenProxyLendingIterator<'this, T>
where
    T: New<'this>
{
    type Item<'lend> = T where Self: 'lend;

    fn next(&mut self) -> Option<Self::Item<'_>> {
        let key = match self.keys.get(self.index) {
            Some(key) => *key,
            None => return None,
        };
        self.index += 1;
        Some(T::new_new(self.main, key))
    }
}

The T: New<'this> allow allows you to call T::new_new with a lifetime of 'this, which produces another T. You need to be able to call New::new_new on all possible lifetimes shorter than 'this, which will produce a different type for every input lifetime. (Types which differ only by a lifetime are still distinct types, and type parameters like T can only represent a single type.)

Here's one way to accomplish that:[1]

trait New {
    type This<'a>;
    fn new_new(main: &mut Main, key: i32) -> Self::This<'_>;
}

enum Proxy2MutGenerator {}
impl New for Proxy2MutGenerator {
    type This<'a> = Proxy2Mut<'a>;
    fn new_new(main: &mut Main, key: i32) -> Self::This<'_> {
        Proxy2Mut { main, key }
    }
}

The implementors are just "marker types" that act as a type constructor you can name without lifetimes. Alternatively you could implement it for Proxy2Mut<'static>, etc.

Changing the other code to match:

 impl<'a> Proxy1Mut<'a> {
-    fn iter_proxy2_mut(&mut self) -> GenProxyLendingIterator<'_, Proxy2Mut<'_>> {
+    fn iter_proxy2_mut(&mut self) -> GenProxyLendingIterator<'_, Proxy2MutGenerator> {

 struct GenProxyLendingIterator<'this, T>
 where
-    T: New<'this>
+    T: New

 impl<'this, T> LendingIterator for GenProxyLendingIterator<'this, T>
 where
-    T: New<'this>
+    T: New
 {
-    type Item<'lend> = T where Self: 'lend;
+    type Item<'lend> = <T as New>::This<'lend> where Self: 'lend;

It may not completely solve your use case, depending on how complicated it is. For example, if it's not always possible to define New::This<'_> for all lifetimes.

Side note: I suggest you use #![deny(elided_lifetimes_in_paths)].

  1. the diffs include a little cleanup I did before making relevant changes ↩ī¸Ž

3

Thank you, it does the trick.

What are the other ways are?

Also, are there language features on the horizon (even if in the nightly build) which simplify whole process of building lending iterators (besides polonius which I've read a bit on), and generalizing it over returned type?

4

I didn't have an exhaustive list in mind :slightly_smiling_face:. I took another look and I don't think there's any good way to get around T not being exactly what is produced. You can get rid of my newtype. You can leave New alone and use a new type constructor trait.

trait NewFor<'lend, UpperBound = &'lend Self> {
    type NewTy: New<'lend>;
}

impl<'this, 'lend> NewFor<'lend> for Proxy2Mut<'this> {
    type NewTy = Proxy2Mut<'lend>;
}

(Using some designs from here.)

Those create the illusion that T and the output are the same, but really T is just a stand-in for some type constructor, like in my previous playground.

Here's one more where I put the type constructor representative in a wrapping newtype that implements a wrapping-like trait. This makes the implementation of LendingIterator not have to "know about" or care about the type constructor representative, and even admits type-erasing the representative with dyn for<'any> NewFor<'any, Ty = Proxy2Mut<'any>>... not that I'm aware of any reason that would be useful. Also, the Gen wrapper has to be local to the NewFor implementing crate.

If you use traits instead of types -- if you could return an Option<impl use <'_> + Proxy2MutCapability> instead of an Option<Proxy2Mut<'_>> -- then there are some things present (-> impl Trait in traits) or in the pipeline (type Item<'lend> = impl Trait) which provide alternatives. They're not a panacea.

Changes to where bounds are proven/implied, and-or conditional HRTBs (for<'a where 'b: 'a>), would relieve some of the pain covered in the Sabrina Jewson blog post. The latter is being worked on, but I don't know the timelines or how much surface syntax will be available to developers.

But I don't think any of those would have actually helped your OP directly, where basically the T parameter on GenProxyLendingIterator exists to represent Item<'lend>.

I'm not aware of any work on "generic type constructor parameters", so I don't think the pattern of using traits/GATs to emulate them is going away any time soon.

1 Like