Lifetime bounds in Copy impls are ignored

[arielb1]

UPDATE: Mentoring instructions below.

---

Affected Versions

rustc 1.3.0 - 1.5.0

STR

#[derive(Clone)] struct Foo<'a>(&'a u32);
impl Copy for Foo<'static> {}

fn main() {
    let s = 2;
    let a = Foo(&s);
    drop(a);
    drop(a);
}

Expected Result

Foo<'a> is not Copy, so this should cause a borrowck error.

Actual Result

The code compiles :-).

cc @nikomatsakis

[nikomatsakis]

Nominating.

[nikomatsakis]

triage: P-high

[nikomatsakis]

Correct behavior here is not entirely obvious, given that we erase lifetimes at trans. Possibly we should be treating this affine, or possibly the impl should be an error? Have to mull this over.

cc @rust-lang/lang

[nikomatsakis]

Nominating for discussion at the lang meeting.

[nikomatsakis]

So my feeling is that the copy_or_move code that decides whether this is copy or move ought to decide that values of type Foo<'_> are affine. But there are other complex scenarios too.

[pnkfelix]

possibly the impl should be an error?

(I assume this means e.g. that impl Copy for Foo<'r> for any 'r is illegal; i.e. if we took this tack, we would require a Copy impl to be as generic as the struct definition is. We have similar code to ensure this for Drop impls, so its not totally crazy...)

[nikomatsakis]

So now that I've thought about this I agree with @pnkfelix. We should use the dropck code to enforce this constraint.

[nikomatsakis]

There is a catch -- we can't use the precise dropck check. We don't want all instances of a type to be Copy. In particular, we want to allow at least conditional copy impls like:

impl<T:Copy> Copy for Option<T> { }

Probably we want a "lifetime dispatch" predicate exactly like the one that @aturon was experimenting with for specialization -- basically we want to know the same property here. That is, we want to know that the Copy-ness is not decided by the lifetimes, because we view those as outputs of trait selection, not inputs.

[nikomatsakis]

And, in fact, the problem runs deeper -- just as with specialization, the Copy impl can only rely on other "non-dispatching" impls. Which we can't easily quantify.

All this makes me wonder: maybe we are taking the wrong approach. Maybe we should run borrowck and find all values that are used more than once and then add a requirement then that they be Copy. Basically, can we change from asking "is this Copy?" to demanding that something be Copy whenever it has to be?

Not sure just what would be affected. I know that MIR construction uses "is this Copy?" to avoid creating needless drops, but that's really just a heuristic. I'd have to go look where-else this comes up.

[arielb1]

This can get messier with associated types, as they can introduce lifetime bounds on their own:

trait Foo { type Out; }
#[derive(Clone)]
struct S<T: Foo>(T::Out);
impl<T: Foo> Copy for S where T::Out: Copy {}

impl<'a> Foo for (&'a u32, &'a u32) {
    type Out = u32;
}

[arielb1]

Maybe we should run borrowck and find all values that are used more than once and then add a requirement then that they be Copy.

But then the new lifetime bounds can affect (lifetime) inference.

[nikomatsakis]

@arielb1 Yes, that's true. The other place that I've found where a complication arises is in closure inference, which uses copy-vs-move to decide how to handle upvars in some cases.

[nikomatsakis]

OK, so, I see two viable candidates as of now:

1. Piggyback on some explicit notion of "lifetime dispatchable" (where Copy is NOT lifetime dispatchable).
2. When checking if a type T is "affine", replace all regions with fresh regions just for the purpose of the check. This would mean that sometimes types are moved even if they implement Copy, but only if those Copy impls are not lifetime dispatchable.

The first seems obviously superior in that it doesn't require explaining to people why a move occurred when they expected a copy.

[nikomatsakis]

So I did some investigation here and I believe I have a simple proposal that would solve this problem. We can restrict Copy impls in the same way that we restrict Drop impls -- that is, they cannot have where clauses unless those same where clauses are required for WF -- but with one addition: they CAN have Copy where-clauses. This is basically a simplified version of the "lifetime parametric" predicate in which we have exactly one trait that is guaranteed to be lifetime parametric: Copy. I grepped through the source of every package on crates.io and investigated every explicit impl of Copy (I ignored derive). Literally all of them would work with this restriction.

[arielb1]

@nikomatsakis

Will associated types not be a problem?

[nikomatsakis]

@arielb1

Will associated types not be a problem?

Maybe, but I don't quite see how yet. Can you give an example of where you think a problem would arise? Earlier, you wrote this, but I don't quite understand what you were getting at:

trait Foo { type Out; }
#[derive(Clone)]
struct S<T: Foo>(T::Out);
impl<T: Foo> Copy for S where T::Out: Copy {}

impl<'a> Foo for (&'a u32, &'a u32) {
    type Out = u32;
}

In particular here, it doesn't seem like there are any lifetime bounds that are not already guaranteed by WF, right?

[arielb1]

Maybe they are not actually an issue, because (&'u u32, &'v u32): Foo already implies that 'u = 'v. It is still a little odd to open impls in this "reverse" way.

[nikomatsakis]

Is anyone interested in spearheading this issue? I'm assigned, but I'm pretty overloaded. An RFC would probably be nice. I think we could just write one, but it'd be even better if we could implement the proposed solution so we can measure the impact with a crater run. I prefer this fix.

Logical candidates to do this work:

• @aturon, because he's been diving into this area lately
• @pnkfelix, who wrote the original dropck code that we'd be adapting
• @arielb1, because he's great like that

[eddyb]

@nikomatsakis How does that compare to 170b88d?

[spastorino]

Hey @nikomatsakis thanks for the heads up, yeah if you want I'd be happy to tackle this one :)

[nikomatsakis]

@eddyb

That's basically it, but instead of self.cx.infcx.type_moves_by_default(self.cx.param_env, ty, DUMMY_SP), we should use @spastorino's prove (not yet landed) to prove that the value implements Copy (and add the necessary constraints for region inference).

[eddyb]

If we can ever get rid of MC/EUV, then maybe type_moves_by_default can disappear as well.

[nikomatsakis]

@eddyb I think we will wind up needing something like MC/EUV, because it's needed for upvar inference, but I suspect we can redesign it to be radically better and simpler.

[nikomatsakis]

cc @spastorino -- all the pieces are in place to fix this now, I think. We should use this example:

#![feature(nll)]

#[derive(Clone)] struct Foo<'a>(&'a u32);
impl Copy for Foo<'static> {}

fn main() {
    let s = 2;
    let a = Foo(&s);
    drop(a);
    drop(a);
}

we basically want to change this existing code:

rust/src/librustc_mir/borrow_check/nll/type_check/mod.rs

Lines 376 to 384 in 5c41fce

	if let PlaceContext::Copy = context {
	let ty = place_ty.to_ty(self.tcx());
	if self.cx
	.infcx
	.type_moves_by_default(self.cx.param_env, ty, DUMMY_SP)
	{
	span_mirbug!(self, place, "attempted copy of non-Copy type ({:?})", ty);
	}
	}

so that it invokes prove_trait_ref instead:

rust/src/librustc_mir/borrow_check/nll/type_check/mod.rs

Lines 1486 to 1493 in 5c41fce

	fn prove_trait_ref(&mut self, trait_ref: ty::TraitRef<'tcx>, location: Location) {
	self.prove_predicates(
	&[
	ty::Predicate::Trait(trait_ref.to_poly_trait_ref().to_poly_trait_predicate()),
	],
	location,
	);
	}

In other words, rather than testing that T: Copy, we prove that T: Copy.

[nikomatsakis]

Fixed (with NLL) in #47877