Unexpected "method not found" compiler error

Question

This question arises from my use (in a toy project to learn Rust) of cartesian_product from itertools together with into_par_iter from Rayon. My question is less about this particular code and more a question about reading rustc error messages, and the Rust library documentation.

This works as expected:

fn main() {
    let it = 0..15;
    it.into_par_iter().for_each(|x| println!("{:?}", x));
}

But the code below fails to compile with the error indicated. The documentation for the Product returned by cartesian_product includes an implementation of Iterator, so I would have expected the into_par_iter method call to type check, but such is not the case.

Here's the failing code and the resulting error message:

fn main() {
    let it = (0..15).cartesian_product(0..8);
    it.into_par_iter().for_each(|x| println!("{:?}", x));
}

Compiling iters v0.1.0 (D:\rust\iters)
error[E0599]: no method named `into_par_iter` found for struct `itertools::adaptors::Product<std::ops::Range<{integer}>, std::ops::Range<{integer}>>` in the current scope
   --> src\main.rs:8:8
    |
8   |       it.into_par_iter().for_each(|x| println!("{:?}", x));
    |          ^^^^^^^^^^^^^ method not found in `itertools::adaptors::Product<std::ops::Range<{integer}>, std::ops::Range<{integer}>>`
    |
   ::: D:\rust\dot.cargo\registry\src\github.com-1ecc6299db9ec823\itertools-0.9.0\src\adaptors\mod.rs:288:1
    |
288 | / pub struct Product<I, J>
289 | |     where I: Iterator
290 | | {
291 | |     a: I,
...   |
294 | |     b_orig: J,
295 | | }
    | | -
    | | |
    | |_doesn't satisfy `_: rayon::iter::IntoParallelIterator`
    |   doesn't satisfy `_: rayon::iter::ParallelIterator`
    |
    = note: the method `into_par_iter` exists but the following trait bounds were not satisfied:
            `itertools::adaptors::Product<std::ops::Range<{integer}>, std::ops::Range<{integer}>>: rayon::iter::ParallelIterator`
            which is required by `itertools::adaptors::Product<std::ops::Range<{integer}>, std::ops::Range<{integer}>>: rayon::iter::IntoParallelIterator`
            `&itertools::adaptors::Product<std::ops::Range<{integer}>, std::ops::Range<{integer}>>: rayon::iter::ParallelIterator`
            which is required by `&itertools::adaptors::Product<std::ops::Range<{integer}>, std::ops::Range<{integer}>>: rayon::iter::IntoParallelIterator`
            `&mut itertools::adaptors::Product<std::ops::Range<{integer}>, std::ops::Range<{integer}>>: rayon::iter::ParallelIterator`
            which is required by `&mut itertools::adaptors::Product<std::ops::Range<{integer}>, std::ops::Range<{integer}>>: rayon::iter::IntoParallelIterator`

Challenger5 · Accepted Answer · 2020-07-17T00:23:54.163

2

itertools::Itertools::cartesian_product returns a value of type itertools::Product, which implements std's Iterator.

However, Rayon can't just work with any type that implements Iterator - it must also implement rayon::ParallelIterator. Rayon happens to provide implementations of ParallelIterator for most std iterators, but it can't implement them for structs in another crate (like itertools) without depending on that crate. Similarly, itertools couldn't implement rayon::ParallelIterator for its types without depending on rayon.

Instead, you can duplicate the functionality of Itertools::cartesian_product yourself using Rayon's API:

use rayon::iter::{ParallelIterator, IntoParallelIterator};

fn main() {
    (0..15).into_par_iter()
        .flat_map(|i| (0..8).into_par_iter().map(move |j| (i, j)))
        .for_each(|x| println!("{:?}", x));
}

Alternatively, you can start with an iterator of length (15 * 8) and then use division and remainder to break it down into tuples:

use rayon::iter::{ParallelIterator, IntoParallelIterator};

fn main() {
    let it = (0 .. 15 * 8).into_par_iter().map(|x| (x / 8, x % 8));
    it.for_each(|x| println!("{:?}", x));
}

edited Jul 17 '20 at 00:23

answered Jul 17 '20 at 00:18

Challenger5

959
6
26

Yes, I see now that into_par_iter is defined on the IntoParallelIterator trait, and that there doesn't seem to be an implementation of IntoParallelIterator for Iterator, as I'd assumed was the case. I suppose this is because Iterator itself is a trait, and IntoParallelItorator needs to be defined on concrete types? – J. Dane Jul 17 '20 at 01:32
This is because not any iterator can be iterated in parallel, so it's impossible to do a "blanket implementation", which covers everything. – Cerberus Jul 17 '20 at 03:03
There is something odd about this explanation (although I don't doubt that it's correct), because the iterator represented by the range `0..15` is accepted by `into_par_iter`. I had assumed that whatever "naive" parallelization was used in that case would be used in any case of a "plain vanilla" iterator. In any case, I found the `ParallelBridge` trait which seems to do just that, and which should work for my simple case. – J. Dane Jul 18 '20 at 01:10

Unexpected "method not found" compiler error

1 Answers1