How to reverse after zip two chains

Question

I have the following code which does not compile.

fn main() {
  let a =
    "123"
    .chars()
    .chain("4566".chars())
    .zip(
        "bbb"
        .chars()
        .chain("yyy".chars()))
    .rev()
    .map(|x, y| y)
    .collect::<String>();
  println!("Hello, world! {}", a);
}

Got error like following:

src/main.rs:37:10: 37:15 error: the trait `core::iter::ExactSizeIterator` is not implemented for the type `core::iter::Chain<core::str::Chars<'_>, core::str::Chars<'_>>` [E0277]
src/main.rs:37         .rev()
                        ^~~~~
src/main.rs:37:10: 37:15 error: the trait `core::iter::ExactSizeIterator` is not implemented for the type `core::iter::Chain<core::str::Chars<'_>, core::str::Chars<'_>>` [E0277]
src/main.rs:37         .rev()
                        ^~~~~
src/main.rs:38:10: 38:23 error: type `core::iter::Rev<core::iter::Zip<core::iter::Chain<core::str::Chars<'_>, core::str::Chars<'_>>, core::iter::Chain<core::str::Chars<'_>, core::str::Chars<'_>>>>` does not implement any method in scope named `map`
src/main.rs:38         .map(|x, y| y)

My understanding is rev() method is defined in Iterator as where it implements trait DoubleEndedIterator

fn rev(self) -> Rev<Self> where Self: DoubleEndedIterator { ... }

Also Zip implements this trait:

impl<A, B> DoubleEndedIterator for Zip<A, B> where B: DoubleEndedIterator + ExactSizeIterator, A: DoubleEndedIterator + ExactSizeIterator

So the problem is Chain doesn't implement ExactSizeIterator. But how do I work around this?

I tried to add .take() for both chains to convert the type to Take which implements ExactSizeIterator, but Take doesn't implement DoubleEndedIterator.

Note this is a simplified example. In reality I cannot reverse both chain first and then do the zip.

Answer 1

You're looking for the following impl (spoiler: it doesn't exist):

impl<A, B> ExactSizeIterator for Chain<A, B>
  where A: ExactSizeIterator, B: ExactSizeIterator { ... }

An ExactSizeIterator must implement only one method, len(&self). So the idea behind an hypothetical implementation would be to sum both lengths so that chain_a_b.len() == a.len() + b.len().

The reason it doesn't exist is that Rust cannot guarantee that this addition (usize + usize) will not overflow. Thus it forbids it. It sounds like a little strict, but that's the status quo for now, unfortunately.

Worse: even if this impl actually existed, you would run into the fact that Chars is not an ExactSizeIterator, so it would still not work.

An alternative (probably not the only one) would be to collect the chains into a vector. Bad because of the memory allocation, but if it isn't a perf bottleneck it could be worth the tradeoff.