Non-consuming IntoIter & borrow-checker 'static requirements

1

Hi all

I'm trying to force non-consuming IntoIter in generic functions.
However rustc just refuses to compile it :slight_smile:
I've already taken an inspiration from a smart solution here - IntoIterator/Iterate by ref (non-consuming) trait bound - #5 by quinedot , but looks like I am not that smart to make it work properly.

// A GAT-like substitute to transfer the lifetime from `&T` to `T`
pub trait NonconsumingIter<'a, _LifetimeHack = &'a Self> {
    type Item;
    type IntoIter: Iterator<Item = Self::Item>;
}

// Our main trait which relies on it
pub trait Iterable: for<'any> NonconsumingIter<'any> {
    fn iter(&self) -> <Self as NonconsumingIter<'_>>::IntoIter;
}

// Blanket implement for everything that matches our use case
impl<'a, I: ?Sized> NonconsumingIter<'a> for I
where
    &'a I: IntoIterator,
{
    type Item = <<&'a I as IntoIterator>::IntoIter as IntoIterator>::Item;
    type IntoIter = <&'a I as IntoIterator>::IntoIter;
}

// Blanket implement for everything that meets the bounds period
impl<T: ?Sized> Iterable for T
where
    for<'any> &'any T: IntoIterator,
{
    fn iter(&self) -> <Self as NonconsumingIter<'_>>::IntoIter { self.into_iter() }
}

#[derive(Debug)]
pub enum NestedValue<'a, T, V>
where
    V: Iterable<Item = &'a T>,
    V: FromIterator<T>,
{
    SingleRef(&'a T),
    Single(T),

    NestedRef(&'a V),
    Nested(V),
}

impl<'a, T, V> PartialEq for NestedValue<'a, T, V>
where
    T: PartialEq,
    V: Iterable<Item = &'a T>,
    V: FromIterator<T>,
{
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (NestedValue::SingleRef(x), NestedValue::SingleRef(y)) => x == y,
            (NestedValue::Single(ref x), NestedValue::Single(ref y)) => x == y,

            (NestedValue::NestedRef(x), NestedValue::NestedRef(y)) => x.iter().zip(y.iter()).all(|(x, y)| x == y),
            (NestedValue::Nested(ref x), NestedValue::Nested(ref y)) => x.iter().zip(y.iter()).all(|(x, y)| x == y),
            _ => false,
        }
    }
}

impl<'a, T, V> Eq for NestedValue<'a, T, V>
where
    T: PartialEq,
    V: Iterable<Item = &'a T>,
    V: FromIterator<T>,
{
}

pub trait NestedMapC<'a, T, V, F>: Sized + Iterator<Item = &'a NestedValue<'a, T, V>>
where
    T: 'a,
    V: 'a + Iterable<Item = &'a T>,
    V: FromIterator<T>,
    F: Fn(&T) -> T,
{
    fn nested_map(self, mapf: F) -> NestedMap<'a, T, V, F, Self> { NestedMap { it: self, mapf } }
}
impl<'a, T, V, F, I> NestedMapC<'a, T, V, F> for I
where
    T: 'a,
    V: 'a + Iterable<Item = &'a T>,
    V: FromIterator<T>,
    F: Fn(&T) -> T,
    I: Iterator<Item = &'a NestedValue<'a, T, V>>,
{
}

pub struct NestedMap<'a, T, V, F, I>
where
    T: 'a,
    V: 'a + Iterable<Item = &'a T>,
    V: FromIterator<T>,
    F: Fn(&T) -> T,
    I: Iterator<Item = &'a NestedValue<'a, T, V>>,
{
    it: I,
    mapf: F,
}

impl<'a, T, V, F, I> Iterator for NestedMap<'a, T, V, F, I>
where
    T: 'a,
    V: Iterable<Item = &'a T>,
    V: FromIterator<T>,
    F: Fn(&T) -> T,
    I: Iterator<Item = &'a NestedValue<'a, T, V>>,
{
    type Item = NestedValue<'a, T, V>;
    fn next(&mut self) -> Option<Self::Item> {
        self.it.next().map(|x| match x {
            NestedValue::SingleRef(x) => NestedValue::Single((self.mapf)(x)),
            NestedValue::Single(x) => NestedValue::Single((self.mapf)(x)),

            NestedValue::NestedRef(v) => NestedValue::Nested(v.iter().map(&self.mapf).collect()),
            NestedValue::Nested(v) => NestedValue::Nested(v.iter().map(&self.mapf).collect()),
        })
    }
}

//=======================================================================================
pub fn test_map<'a, T, V, F>(s: &'a [NestedValue<'a, T, V>], mapf: F) -> Vec<NestedValue<'a, T, V>>
where
    V: Iterable<Item = &'a T>,
    V: FromIterator<T>,
    F: Fn(&T) -> T,
{
    //
    s.iter().nested_map(mapf).collect()
}

    #[test]
    fn test_map1() {
        //test_map<'a, T, V, F>(s: &'a [NestedValue<'a, T, V>], mapf: F) -> Vec<NestedValue<'a, T, V>>
        let s1 = 10u32;
        let v1 = vec![1, 2, 3];
        let nv1 = [NestedValue::SingleRef(&s1), NestedValue::SingleRef(&s1), NestedValue::NestedRef(&v1)];
        let v = test_map(&nv1, |x| x + 1);

        let s2 = 10u32;
        let v2 = vec![1, 2, 3];
        let nv2 = vec![NestedValue::SingleRef(&s2), NestedValue::SingleRef(&s2), NestedValue::NestedRef(&v2)];

        let v = format!("{:?}", v);
        let nv2 = format!("{:?}", nv2);

        //assert_eq!(v, nv2);
    }

... or in playground here - Rust Playground

I just get something like:

error: implementation of `NonconsumingIter` is not general enough
   --> src/tree.rs:400:19
    |
400 |         let nv1 = [NestedValue::SingleRef(&s1), NestedValue::SingleRef(&s1), NestedValue::NestedRef(&v1)];
    |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `NonconsumingIter` is not general enough
    |
    = note: `Vec<u32>` must implement `NonconsumingIter<'0>`, for any lifetime `'0`...
    = note: ...but it actually implements `NonconsumingIter<'1>`, for some specific lifetime `'1`

error[E0597]: `s1` does not live long enough
   --> src/tree.rs:400:43
    |
398 |         let s1 = 10u32;
    |             -- binding `s1` declared here
399 |         let v1 = vec![1, 2, 3];
400 |         let nv1 = [NestedValue::SingleRef(&s1), NestedValue::SingleRef(&s1), NestedValue::NestedRef(&v1)];
    |                                           ^^^
    |                                           |
    |                                           borrowed value does not live long enough
    |                                           this usage requires that `s1` is borrowed for `'static`
...
411 |     }
    |     - `s1` dropped here while still borrowed
    |
note: due to current limitations in the borrow checker, this implies a `'static` lifetime
   --> src/tree.rs:49:17
    |
49  |     V: Iterable<Item = &'a T>,
    |                 ^^^^^^^^^^^^

Any help?

BR

2

The issue is with

V: Iterable<Item = &'a T>

which talks about the Item type in the

: for<'any> NonconsumingIter<'any>

supertrait of trait Iterable, but doesn’t declare that Item type with any dependency on the lifetime 'any. As such, this will mean V expects iterators that always produce &'a T, for your blanket impl that means you’d need a type Foo where &'any Foo: IntoIter<Item = &'a T>. Which of course won’t match your use case of Vec, for &'a Vec<T>, the IntoIter produces &'a T of the same lifetime.

One way to write this Item = … in a more correct way is to put it on a HRTB about NonconsumingIter instead.

In fact, if I go on and replace every

    V: Iterable<Item = &'a T>,

with

    V: Iterable + for<'b> NonconsumingIter<'b, Item = &'b T>,

then your example already seems to work.

3

Thanks. It works indeed after rewriting to

V: Iterable + for<'b> NonconsumingIter<'b, Item = &'b T>,

But is it possible to shorten it to just single trait usage?
I mean something like following:

V: for<'b> Iterable<'b, Item = &'b T>,
4

You can put the method in the lifetime-specific trait so you don't have to mention Iterable in the bounds.

1 Like
5

Great!
Thanks a lot. It works as expected.

6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.