Chain two iterators from different types but implementing the same trait


#1

Is there a way to chain two iterators from different types yield a iterator over a shared Trait.

A simple example would be:

fn main() {
    let u = vec![1, 2, 3];
    let v = vec![1.5, 2.5, 3.5];
    for p in u.iter().chain(v.iter()) {
        println!("{:?}", p);
    }
}

This fails to compile because chain expects that the first and second iterators have the same item type. But both iterators items implement the Debug trait which is the only thing I need inside the loop. Is there a way to achieve such thing?


#2

It works if you explicitly convert them to &Debug trait objects, so they really do have the same Iterator::Item type.

use std::fmt::Debug;
fn main() {
    let u = vec![1, 2, 3];
    let v = vec![1.5, 2.5, 3.5];
    for p in u.iter().map(|x| x as &Debug)
      .chain(v.iter().map(|x| x as &Debug)) {
        println!("{:?}", p);
    }
}

#3

Thanks @cuviper

Just out of curiosity, Is this expensive or a way to tell the compiler the type?


#4

It’s more expensive in that it forces the Debug methods to be called indirectly through a vtable. That prevents inlining, and such calls are also a bit harder for CPU branch predictors. Perhaps a sufficiently smart compiler could figure out how to unroll and flatten some cases, but it doesn’t appear to do so here.

But it’s hard to say whether it’s expensive enough to matter. In a simple case like this, the cost of an indirect call is almost certainly dwarfed by all the actual IO code for printing.


#5

For formatting, it always goes through a virtual call of for example Debug::fmt anyway.


#6

To catch some of my mistakes, I usually compile Rust code with full warnings, and your code gives me:

temp.rs:5:31: 5:42 warning: trivial cast: `&i32` as `&core::fmt::Debug`. Cast can be replaced by coercion, this might require type ascription or a temporary variable [-W trivial-casts]
temp.rs:5     for p in u.iter().map(|x| x as &Debug)
                                        ^~~~~~~~~~~
temp.rs:6:31: 6:42 warning: trivial cast: `&f64` as `&core::fmt::Debug`. Cast can be replaced by coercion, this might require type ascription or a temporary variable [-W trivial-casts]
temp.rs:6       .chain(v.iter().map(|x| x as &Debug)) {
                                        ^~~~~~~~~~~

What’s the right way to face this (beside disabling those warnings)?


#7

I suppose “.map(|x| { let d: &Debug = x; d })”.

You can almost write “.map(|x| -> &Debug { x }))”, but it tries to use a static lifetime for that reference. I’m not sure how to express that one correctly.


#8

OK, thank you. My original warnings talk about “type ascription”, that I think means using:

.map(|x| x: &Debug)

That doesn’t compile, requiring:

#![feature(type_ascription)]

If I add that at the top of the module, I get other errors:

test.rs:8:23: 8:24 error: mismatched types:
 expected `&core::fmt::Debug`,
    found `&_`
(expected trait core::fmt::Debug,
    found integral variable) [E0308]
test.rs:8              .map(|x| x: &Debug)
                                                                    ^
test.rs:8:23: 8:24 help: run `rustc --explain E0308` to see a detailed explanation
error: aborting due to previous error

Another thing I don’t understand is why x as &Debug raises a “trivial cast” warning. x is a thin reference, while &Debug is a fat pointer, so it’s not a trivial change.


#9

AIUI the warning arises for anything that could be coerced, like my “let d: &Debug = x;”, whereas you can’t do that for casts like u32 to u64.


#10

OK, that’s reasonable. Those warnings help the programmer remove as many “hard casts” as (currently) possible from the Rust code.

So I guess the new “x: &Debug” syntax is not yet usable here…


#11

It still bugs me that I can’t get that closure right, but alternatively it works as a generic function. Might be more useful this way if you need to do such trait-object conversions a lot.

use std::fmt::Debug;
fn as_debug<T: Debug>(x: &T) -> &Debug { x }
fn main() {
    let u = vec![1, 2, 3];
    let v = vec![1.5, 2.5, 3.5];

    for p in u.iter().map(as_debug)
      .chain(v.iter().map(as_debug)) {
        println!("{:?}", p);
    }
}

#12

I have been playing with this to try to understand it more, and there a re still things I do not understand. For example:

Why this works:

struct S1 {
    x: usize,
    v: Vec<u8>,
}

struct S2 {
    y: usize,
    v: Vec<u8>,
}

impl S1 {
    fn new(x: usize) -> Self {
        S1{x: x,
           v: Vec::new()
           }
    }
}

impl S2 {
    fn new(y: usize) -> Self {
        S2{y: y,
           v: Vec::new()
           }
    }
}

trait T {
    fn val(&self) -> usize;
}

impl T for S1 {
    fn val(&self) -> usize {self.x}
}

impl T for S2 {
    fn val(&self) -> usize {self.y}
}

fn sum<'d, I>(it: I) -> usize
    where I: Iterator<Item=&'d T>,
{
    let mut s = 0;
    for el in it.filter(|x| x.val() > 1) {
        s += el.val() 
    }
    s
}

fn main() {
    let u = vec![S1::new(1), S1::new(2), S1::new(3)];
    let v = vec![S2::new(1), S2::new(2), S2::new(3)];
    for p in u.iter().map(|x| x as &T)
      .chain(v.iter().map(|x| x as &T)) {
        println!("{}", p.val());
    }
    let it = u.iter().map(|x| x as &T)
              .chain(v.iter().map(|x| x as &T));
    println!("sum: {}", sum(it));
}

but this fails:

struct S1 {
    x: usize,
    v: Vec<u8>,
}

struct S2 {
    y: usize,
    v: Vec<u8>,
}

impl S1 {
    fn new(x: usize) -> Self {
        S1{x: x,
           v: Vec::new()
           }
    }
}

impl S2 {
    fn new(y: usize) -> Self {
        S2{y: y,
           v: Vec::new()
           }
    }
}

trait T {
    fn val(&self) -> usize;
}

impl T for S1 {
    fn val(&self) -> usize {self.x}
}

impl T for S2 {
    fn val(&self) -> usize {self.y}
}

fn sum<'d, I, A: 'd>(it: I) -> usize
    where I: Iterator<Item=&'d A>, // This is different
          A: T
{
    let mut s = 0;
    for el in it.filter(|x| x.val() > 1) {
        s += el.val() 
    }
    s
}

fn main() {
    let u = vec![S1::new(1), S1::new(2), S1::new(3)];
    let v = vec![S2::new(1), S2::new(2), S2::new(3)];
    for p in u.iter().map(|x| x as &T)
      .chain(v.iter().map(|x| x as &T)) {
        println!("{}", p.val());
    }
    let it = u.iter().map(|x| x as &T)
              .chain(v.iter().map(|x| x as &T));
    println!("sum: {}", sum(it));
}

with the following error:

error: the trait core::marker::Sized is not implemented for the type T [E0277]
println!(“sum: {}”, sum(it));


#13

You can tell it that A may be unsized, A: 'd + ?Sized. Trait objects are DSTs.


#14

@cuviper Thanks for taking the time to answer. I understand ?Sized but I thought that this code

fn sum<'d, I>(it: I) -> usize
    where I: Iterator<Item=&'d MyTrait>,

was just a short version for this other code

fn sum<'d, I, A: 'd>(it: I) -> usize
    where I: Iterator<Item=&'d A>,
          A: MyTrait

but one compiles and the other does not. I guess I am missing something important here. Moreover,
with the second options I can compile println!("U: {}", sum(u.iter())); but not chaining and casting to T two different type. With the first option, It works if I cast the chain elements but I also need to cast u.iter() elements.


#15

No. Lifetime elision only happens for parameters and return values, but not for associated types of parameters.

https://doc.rust-lang.org/book/lifetimes.html#lifetime-elision

Would it make sense and is it feasible to add such a case?


#16

@skade Now I am really confused. What lifetime elision has to do with this. I thought that in the first case I was just saying that the iterator Item bound to MyTrait inline, while in the other I am taking another line.


#17

&Trait is not a shortcut for a generic type with a bound on Trait, it is a trait object, a dynamic-dispatch type.

This means that if you have a Vec<&T> with T: Trait, it will be a homogeneous vector of the same type of references, but Rust will create different instances of the type depending on the T you use. In contrast, Vec<&Trait> can contain references to any object whose type implements Trait at the same time.

Trait objects should only be used where necessary, because they add a restriction (the trait has to be “object-safe”) and a performance penalty (dynamic dispatch using a vtable that is part of the representation of &Trait as a fat pointer).


#18

@birkenfeld Thanks a lot for the explanation, it helped a lot.

If I understood correctly, then there is not way to make sum accept u.iter().map(|x| x as &T).chain(v.iter().map(|x| x as &T)) and also u.iter() without doing u.iter().map(|x| x as &T).