Iterator composition: Poor error message when Clone trait bound is missing

[pnkfelix]

I am not sure if we can do anything about this, but I thought I should at least note the problem: In the code below, there is a iterator composition (iter().map(..).collect()) that is going wrong because of a missing Clone trait bound.

The fact that the code cannot be compiled is fine. My question is, can we make the error message better? Invocations of methods other than clone yield coherent error messages from rustc; why is clone different in this case? (is this an artifact of some impl<Bounds...> Clone for X floating around, for appropriate substitutions for Bounds and X?)

Test case:

#[allow(unused_imports)];

use std::hashmap::HashSetIterator;
use std::hashmap::HashSet;

#[cfg(and(not(illustrate_poor_error_msg),not(illustrate_fine_error_msg)))]
fn iter_to_vec<'a, 'b, X:Clone>(i: HashSetIterator<'b, X>) -> ~[X] {
    //                  ^~~~~~
    //                  missing clone is the only difference
    let i = i.map(|x| x.clone());
    //                  ^~~~~~
    //                  Here is the call to clone
    let mut i = i;
    i.collect()
}

#[cfg(illustrate_poor_error_msg)]
fn iter_to_vec<'a, 'b, X      >(i: HashSetIterator<'b, X>) -> ~[X] {
    //                  ^~~~~~
    //                  missing clone is the only difference
    let i = i.map(|x| x.clone());
    //                  ^~~~~~
    //                  Here is the call to clone
    let mut i = i;
    i.collect()
}

#[cfg(illustrate_fine_error_msg)]
fn iter_to_vec<'a, 'b, X      >(i: HashSetIterator<'b, X>) -> ~[X] {
    //                  ^~~~~~
    //                  missing clone is the only difference
    let i = i.map(|x| x.enolc());
    //                  ^~~~~~
    //                  Here is a call to something other than clone
    let mut i = i;
    i.collect()
}

#[cfg(illustrate_original_poor_error_msg)]
fn set_to_vec<X:Eq+Hash      >(s:&HashSet<X>) -> ~[X] {
    //                 ^~~~~~
    //                 missing clone is the only difference
    let i = s.iter();
    let mut i = i.map(|x| x.clone());
    i.collect()
}

#[cfg(not(illustrate_orignal_poor_error_msg))]
fn set_to_vec<X:Eq+Hash+Clone>(s:&HashSet<X>) -> ~[X] {
    //                 ^~~~~~
    //                 (the aforementioned clone)
    let i = s.iter();
    let mut i = i.map(|x| x.clone());
    i.collect()
}

fn main() {
    let mut s = HashSet::new();
    s.insert(1);
    s.insert(100);
    s.insert(10211201);
    println(fmt!("%?", set_to_vec(&s)));
}

Transcript:

% RUST_LOG=rustc=1 rustc --version
/Users/pnkfelix/opt/rust-dbg/bin/rustc 0.8-pre (fd49f6d 2013-09-09 02:36:06 -0700)
host: x86_64-apple-darwin
% RUST_LOG=rustc=1 rustc --cfg illustrate_poor_error_msg  /tmp/baz3.rs
/tmp/baz3.rs:25:4: 26:1 error: expected std::iter::FromIterator<&X>, but found std::iter::FromIterator<X> (expected &-ptr but found type parameter)
/tmp/baz3.rs:25     i.collect()
/tmp/baz3.rs:26 }
/tmp/baz3.rs:25:4: 26:1 error: expected std::iter::FromIterator<&X>, but found std::iter::FromIterator<X> (expected &-ptr but found type parameter)
/tmp/baz3.rs:25     i.collect()
/tmp/baz3.rs:26 }
error: aborting due to 2 previous errors
task <unnamed> failed at 'explicit failure', /Users/pnkfelix/Dev/Mozilla/rust.git/src/libsyntax/diagnostic.rs:95
task <unnamed> failed at 'explicit failure', /Users/pnkfelix/Dev/Mozilla/rust.git/src/librustc/rustc.rs:376
% RUST_LOG=rustc=1 rustc --cfg illustrate_fine_error_msg  /tmp/baz3.rs
/tmp/baz3.rs:32:22: 32:32 error: type `&X` does not implement any method in scope named `enolc`
/tmp/baz3.rs:32     let i = i.map(|x| x.enolc());
                                      ^~~~~~~~~~
error: aborting due to previous error
task <unnamed> failed at 'explicit failure', /Users/pnkfelix/Dev/Mozilla/rust.git/src/libsyntax/diagnostic.rs:95
task <unnamed> failed at 'explicit failure', /Users/pnkfelix/Dev/Mozilla/rust.git/src/librustc/rustc.rs:376
% 

[eddyb]

The reason this happens is because you're iterating over &X, and all references are Clone-able.

While Clone takes &self, that doesn't stop autoref from turning &X into &&X for the clone call on it, and you end up with an iterator over the same references, which .collect() can't collect to a Vec<X>, only a Vec<&X>.

Adding the trait bound makes the method call resolve to the Clone implementation of X, before attempting autoref - this is an issue specific to Clone, because it takes &self and is implemented by all &T.

Updated testcase:

#![allow(unused_imports)]

use std::collections::hashmap::{HashSet, SetItems};
use std::hash::Hash;

#[cfg(not(illustrate_poor_error_msg), not(illustrate_fine_error_msg))]
fn iter_to_vec<'a, 'b, X:Clone>(i: SetItems<'b, X>) -> Vec<X> {
    //                  ^~~~~~
    //                  missing clone is the only difference
    let i = i.map(|x| x.clone());
    //                  ^~~~~~
    //                  Here is the call to clone
    let mut i = i;
    i.collect()
}

#[cfg(illustrate_poor_error_msg)]
fn iter_to_vec<'a, 'b, X      >(i: SetItems<'b, X>) -> Vec<X> {
    //                  ^~~~~~
    //                  missing clone is the only difference
    let i = i.map(|x| x.clone());
    //                  ^~~~~~
    //                  Here is the call to clone
    let mut i = i;
    i.collect()
}

#[cfg(illustrate_fine_error_msg)]
fn iter_to_vec<'a, 'b, X      >(i: SetItems<'b, X>) -> Vec<X> {
    //                  ^~~~~~
    //                  missing clone is the only difference
    let i = i.map(|x| x.enolc());
    //                  ^~~~~~
    //                  Here is a call to something other than clone
    let mut i = i;
    i.collect()
}

#[cfg(illustrate_original_poor_error_msg)]
fn set_to_vec<X:Eq+Hash      >(s: &HashSet<X>) -> Vec<X> {
    //                 ^~~~~~
    //                 missing clone is the only difference
    let i = s.iter();
    let mut i = i.map(|x| x.clone());
    i.collect()
}

#[cfg(not(illustrate_original_poor_error_msg))]
fn set_to_vec<X:Eq+Hash+Clone>(s: &HashSet<X>) -> Vec<X> {
    //                 ^~~~~~
    //                 (the aforementioned clone)
    let i = s.iter();
    let mut i = i.map(|x| x.clone());
    i.collect()
}

fn main() {
    let mut s = HashSet::new();
    s.insert(1i);
    s.insert(100);
    s.insert(10211201);
    println!("{}", set_to_vec(&s));
}

[eefriedman]

Updated testcase:

use std::collections::hash_set::Iter;
use std::collections::HashSet;

fn iter_to_vec<'b, X>(i: Iter<'b, X>) -> Vec<X> {
    let i = i.map(|x| x.clone());
    i.collect()
}

fn main() {
    let mut s = HashSet::new();
    s.insert(1u8);
    println!("{:?}", iter_to_vec(s.iter()));
}

Currently gives:

<anon>:6:7: 6:16 error: the trait `core::iter::FromIterator<&X>` is not implemented for the type `collections::vec::Vec<X>` [E0277]
<anon>:6     i.collect()
               ^~~~~~~~~
<anon>:6:7: 6:16 note: a collection of type `collections::vec::Vec<X>` cannot be built from an iterator over elements of type `&X`
<anon>:6     i.collect()
               ^~~~~~~~~

Not sure it's possible to do much better than that given the current semantics of Rust.

[steveklabnik]

Triage: no change with @eefriedman 's example

[estebank]

Current output, no change other than update to "new style" diagnostics:

error[E0277]: the trait bound `std::vec::Vec<X>: std::iter::FromIterator<&X>` is not satisfied
 --> src/main.rs:6:7
  |
6 |     i.collect()
  |       ^^^^^^^ a collection of type `std::vec::Vec<X>` cannot be built from an iterator over elements of type `&X`
  |
  = help: the trait `std::iter::FromIterator<&X>` is not implemented for `std::vec::Vec<X>`

---

The diagnostic should check for possible trait implementations for the current struct/enum that would be acceptable when ignoring the trait bounds, and suggest a note about this:

error[E0277]: the trait bound `std::vec::Vec<X>: std::iter::FromIterator<&X>` is not satisfied
 --> src/main.rs:6:7
  |
6 |     i.collect()
  |       ^^^^^^^ a collection of type `std::vec::Vec<X>` cannot be built from an iterator over elements of type `&X`
  |
  = help: the trait `std::iter::FromIterator<&X>` is not implemented for `std::vec::Vec<X>`
  = note: the trait `std::iter::FromIterator<&X>` is implemented for `std::vec::Vec<X>` for the following unsatisfied trait bounds:
          - `X: Clone`

[estebank]

Current output, no real change:

error[E0277]: a collection of type `std::vec::Vec<X>` cannot be built from an iterator over elements of type `&X`
 --> src/main.rs:6:7
  |
6 |     i.collect()
  |       ^^^^^^^ a collection of type `std::vec::Vec<X>` cannot be built from `std::iter::Iterator<Item=&X>`
  |
  = help: the trait `std::iter::FromIterator<&X>` is not implemented for `std::vec::Vec<X>`

[pnkfelix]

From my point of view, the reason this case is confusing is because of method autoref being willing to turn the &X into &&X for the clone call, and then it says "yes &X implements Clone" and things proceed.

In other words, I think the spot where my mental model diverged from the compiler is along the lines of what @eddyb described here; this is different than what @estebank described later, because (if I understand correctly) in that latter case according to the compiler's internal model, the clone would still be happening on the &X, and we would only be trying to make the resulting Iterator<Item=&X> be able to be collected into a Vec<X>, which was not the original intent of the code I wrote.

Since autoref is special magic built into the language, it might be helpful to users if diagnostics generated by the method search system also consider what method candidates would arise if you filtered out the candidates only available due to trait implementations on &T or &mut T...

In other words, I suspect our method search mechanism when analyzing the call to x.clone(), it ties that to the first working candidate it finds: the impl Clone for &T. But maybe it would be possible for it to build up a broader list of candidates to be suggested solely when it encounters an error, and that broader list could keep looking even after it finds that impl Clone for &T (since that was available solely due to autoref)...

[pnkfelix]

cc #48677, #34896

[estebank]

Triage: no change.

[rylev]

Triage: no change.

I was expecting this example to trip the noop_method_call lint, but unfortunately it does not, because we can't lint when the type might implement clone.

[TimJentzsch]

Current output: no real change with 1.65.0-nightly (2022-08-10 29e4a9ee0253cd39e552):

error[[E0277]](https://doc.rust-lang.org/nightly/error-index.html#E0277): a value of type `Vec<X>` cannot be built from an iterator over elements of type `&X`
 --> src/main.rs:6:7
  |
6 |     i.collect()
  |       ^^^^^^^ value of type `Vec<X>` cannot be built from `std::iter::Iterator<Item=&X>`
  |
  = help: the trait `FromIterator<&X>` is not implemented for `Vec<X>`
  = help: the trait `FromIterator<T>` is implemented for `Vec<T>`
note: required by a bound in `collect`

For more information about this error, try `rustc --explain E0277`.

[estebank]

Current output:

error[E0277]: a value of type `Vec<X>` cannot be built from an iterator over elements of type `&X`
    --> f54.rs:9:7
     |
9    |     i.collect()
     |       ^^^^^^^ value of type `Vec<X>` cannot be built from `std::iter::Iterator<Item=&X>`
     |
     = help: the trait `FromIterator<&X>` is not implemented for `Vec<X>`
     = help: the trait `FromIterator<T>` is implemented for `Vec<T>`
note: the method call chain might not have had the expected associated types
    --> f54.rs:7:15
     |
7    |     let i = s.iter();
     |             - ^^^^^^ `Iterator::Item` is `&X` here
     |             |
     |             this expression has type `&HashSet<X>`
8    |     let mut i = i.map(|x| x.clone());
     |                   ------------------ `Iterator::Item` remains `&X` here
note: required by a bound in `collect`
    --> /Users/ekuber/workspace/rust/library/core/src/iter/traits/iterator.rs:1832:19
     |
1832 |     fn collect<B: FromIterator<Self::Item>>(self) -> B
     |                   ^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `Iterator::collect`

We now provide a fighting chance of realizing that the x.clone() call isn't really changing anything.

The only outstanding thing would be to suggest constraining X: Clone, which I fear might have to be special cased.

[estebank]

Current output:

error[E0277]: a value of type `Vec<X>` cannot be built from an iterator over elements of type `&X`
    --> f76.rs:6:7
     |
6    |     i.collect()
     |       ^^^^^^^ value of type `Vec<X>` cannot be built from `std::iter::Iterator<Item=&X>`
     |
     = help: the trait `FromIterator<&X>` is not implemented for `Vec<X>`
     = help: the trait `FromIterator<X>` is implemented for `Vec<X>`
     = help: for that trait implementation, expected `X`, found `&X`
note: the method call chain might not have had the expected associated types
    --> f76.rs:4:26
     |
4    | fn iter_to_vec<'b, X>(i: Iter<'b, X>) -> Vec<X> {
     |                          ^^^^^^^^^^^ `Iterator::Item` is `&X` here
5    |     let i = i.map(|x| x.clone());
     |               ------------------ `Iterator::Item` remains `&X` here
note: required by a bound in `collect`
    --> /home/gh-estebank/rust/library/core/src/iter/traits/iterator.rs:2049:19
     |
2049 |     fn collect<B: FromIterator<Self::Item>>(self) -> B
     |                   ^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `Iterator::collect`

Still missing the X: Clone suggestion, although for the more idiomatic case of using .cloned() instead of .map(|i| i.clone()), we do:

error[E0277]: the trait bound `X: Clone` is not satisfied
    --> f76.rs:6:15
     |
6    |     let i = i.cloned();
     |               ^^^^^^ the trait `Clone` is not implemented for `X`
     |
note: required by a bound in `cloned`
    --> /home/gh-estebank/rust/library/core/src/iter/traits/iterator.rs:3519:12
     |
3516 |     fn cloned<'a, T: 'a>(self) -> Cloned<Self>
     |        ------ required by a bound in this associated function
...
3519 |         T: Clone,
     |            ^^^^^ required by this bound in `Iterator::cloned`
help: consider restricting type parameter `X`
     |
4    | fn iter_to_vec<'b, X: std::clone::Clone>(i: Iter<'b, X>) -> Vec<X> {
     |                     +++++++++++++++++++

error[E0599]: `Cloned<std::collections::hash_set::Iter<'_, X>>` is not an iterator
  --> f76.rs:7:7
   |
7  |     i.collect()
   |       ^^^^^^^ `Cloned<std::collections::hash_set::Iter<'_, X>>` is not an iterator
   |
  ::: /home/gh-estebank/rust/library/core/src/iter/adapters/cloned.rs:17:1
   |
17 | pub struct Cloned<I> {
   | -------------------- doesn't satisfy `_: Iterator`
   |
   = note: the following trait bounds were not satisfied:
           `Cloned<std::collections::hash_set::Iter<'_, X>>: Iterator`
           which is required by `&mut Cloned<std::collections::hash_set::Iter<'_, X>>: Iterator`