Repository: rust
Issue: HashSet and BTreeSet difference() method argument lifetime overconstrained
Labels: A-collections,T-libs-api,C-bug

Consider this code.

```rust
use std::collections::HashSet as Set;
use std::ops::Deref;

fn exclude_set<'a>(given: &Set<&'a str>, to_exclude: &Set<&str>) -> Set<&'a str> {
    given.difference(to_exclude).cloned().collect()
}

fn main() {
    let given: Set<&str> = vec!["a", "b", "c"].into_iter().collect();
    let b = "b".to_string();
    let to_exclude: Set<&str> = vec![b.deref()].into_iter().collect();
    let excluded = exclude_set(&given, &to_exclude);
    drop(b);
    println!("{:?}", excluded);
}
```

This fails to compile.

```text
error[E0621]: explicit lifetime required in the type of `to_exclude`
 --> src/main.rs:5:5
  |
4 | fn exclude_set<'a>(given: &Set<&'a str>, to_exclude: &Set<&str>) -> Set<&'a str> {
  |                                                      ---------- help: add explicit lifetime `'a` to the type of `to_exclude`: `&std::collections::HashSet<&'a str>`
5 |     given.difference(to_exclude).cloned().collect()
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime `'a` required
```

Now change `exclude_set()` so that `to_exclude` takes `&Set<&'a str>>`. Again, this will fail to compile.

```text
error[E0505]: cannot move out of `b` because it is borrowed
  --> src/main.rs:13:10
   |
11 |     let to_exclude: Set<&str> = vec![b.deref()].into_iter().collect();
   |                                      - borrow of `b` occurs here
12 |     let excluded = exclude_set(&given, &to_exclude);
13 |     drop(b);
   |          ^ move out of `b` occurs here
14 |     println!("{:?}", excluded);
   |                      -------- borrow later used here
```

Commenting out the `drop()` will result in successful compile and execute. 

No value from `to_exclude` should appear in the result of `exclude_set()`: set difference can only remove elements, not insert them. Thus, the drop should be harmless.

Some bodging around with code inspired by the implementation of `std::collections::hash_set::Difference` gets this, which compiles and executes.

```rust
use std::collections::HashSet as Set;
use std::ops::Deref;

fn exclude_set<'a>(
    given: &Set<&'a str>,
    to_exclude: &Set<&str>,
) -> Set<&'a str> {
    set_difference(given, to_exclude).collect()
}

fn main() {
    let given: Set<&str> = vec!["a", "b", "c"].into_iter().collect();
    let b = "b".to_string();
    let to_exclude: Set<&str> = vec![b.deref()].into_iter().collect();
    let excluded = exclude_set(&given, &to_exclude);
    drop(b);
    println!("{:?}", excluded);
}

struct SetDifference<'a, 'b, T: ?Sized> {
    iter: Vec<&'a T>,
    other: &'b Set<&'b T>,
}

impl<'a, 'b, T> Iterator for SetDifference<'a, 'b, T>
where
    T: std::hash::Hash + Eq + ?Sized,
{
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let elt: &'a T = self.iter.pop()?;
            if !self.other.contains(elt) {
                return Some(elt);
            }
        }
    }
}

fn set_difference<'a, 'b, T: ?Sized>(
    source: &Set<&'a T>,
    other: &'b Set<&T>,
) -> SetDifference<'a, 'b, T> {
    SetDifference {
        iter: source.iter().cloned().collect(),
        other,
    }
}
```

Sadly, I haven't figured out how to generalize the types and lifetimes for the new implementation in a way that the typechecker/borrowchecker is happy with.

The same issue exists for `BTreeSet`.