Impl Copy for Range

[jyn514]

From rust-lang/rust#48649 (closed as needing an RFC): It would be nice for Range<Idx: Copy> to implement Copy.

I want to store a Range in a struct, but that prevents me from making the struct Copy. I can make a (start, end) struct that wraps it but that seems a little silly.

With Range from the standard library (playground):

use core::ops::Range;

// error[E0204]: the trait `Copy` may not be implemented for this type
#[derive(Copy)]
struct HasRange {
    r: Range<usize>,
    other_field: usize,
}

// works fine
struct HasRangeWrapper {
    r: RangeWrapper,
    other_field: usize,
}

#[derive(Copy, Clone)]
pub struct RangeWrapper {
    start: usize,
    end: usize,
}

// Note that Range is isomorphic to RangeWrapper;
// you can convert freely between the two
impl From<Range<usize>> for RangeWrapper {
    fn from(range: Range<usize>) -> Self {
        Self { start: range.start, end: range.end }
    }
}

impl From<RangeWrapper> for Range<usize> {
    fn from(range: RangeWrapper) -> Self {
        Self { start: range.start, end: range.end }
    }
}

There is more discussion of pros and cons in the rust-lang/rust issue.

[tesuji]

Clone it?

[Lokathor]

That's clearly less ergonomic than just letting the range be copy.

having range itself be an Iterator and not turn into an iterator is very obviously a design flub at this point, and hopefully an RFC can fix it in some later edition.

[RustyYato]

This is not possible to fix in an edition (I think), so this is non-actionable. Ranges are explicitly not Copy because that could induce weird behaviors in combo with Iterator (this is the same reason why slice::Iter is not Copy even though it could be).

[Lokathor]

Yandros proposed in the issue linked in the OP how, in an edition change, you could remove Iterator from being on Range directly and then give it Copy.

And honestly ive never been clear on what's allowed as an edition change or not. This proposal would be able to compile to the same MIR layer as not using this proposal, so my basic understanding is that it should be possible with an edition change, even if the libs team doesn't end up doing it.

[kennytm]

Adding a Copy impl doesn't require a new edition. However, it would be a total departure from the current practice that Copy and Iterator are mutually exclusive (this is not strongly tied to editions).

---

• doing semver-compatible changes (e.g. adding a Copy to Range) doesn't need a new edition
• incompatible changes to the language itself requires a new edition (assuming both new and old editions are supported by the same MIR)
• incompatible changes to the standard library is prohibited and requires "Rust 2" (e.g. remove Iterator from Range).

[jyn514]

Clone it?

I really don't want to do this since my struct is copied over 150 times throughout the code base. I'm using RangeWrapper in the meantime.

Ranges are explicitly not Copy because that could induce weird behaviors in combo with Iterator

the current practice that Copy and Iterator are mutually exclusive

Can you expand on this? Why doesn't Copy play well with Iterator?

[burdges]

Is there any actual soundness issues with an Iterator being Copy? In fact &T is Copy.

Is it just to avoid impl<I: Copy> Copy for A<I> for many iterator adapters A?

Or is it some performance concern because a tree of loops gets expensive fast? How would that come up?

[sfackler]

This is not a soundess question. Iterator and Copy are both safe APIs, so I don't understand how soudness or the copyability of references would be involved here..

We don't want iterators to be Copy because they are stateful objects, and a Copy stateful object can be copied accidentally, causing unexpected behavior.

[CryZe]

It more seems like there should've been proper IntoIter'd types for ranges then instead of having ranges directly be iterators. Though that would've possibly not been all too ergonomic either.

[burdges]

I see: It's not a performance concern either, so much as a correctness concern. It'd be too easy to make mistakes. It's the same reason &[T] does not satisfy Iterator.

Yes some simple wrapper type like pub struct RangeIter<I>(I); plus the extra impls works here.

[sfackler]

Yeah, in hindsight IntoIterator impls would have been a better approach. In addition to the Copy problem, there's some jank in RangeInclusive that we would have been able to avoid.

[burdges]

At least doing this does not break for loop syntax, so nothing too problematic really, but..

I'm afraid impl<I: Iterator> IntoIterator for I prevents adding pub struct RangeIter<I>(I); before removing impl Iterator for Range, etc., so maybe specialization should land before beginning the edition process?

[sfackler]

We cannot remove impl Iterator for Range. That is a breaking change.

[cmyr]

Just want to chime in to add a little bit of anecdata, which is that I have now on at least three occasions had to search out why Range<T> isn't Copy when T: Copy; it's unexpected and is definitely a papercut. I do a lot of work with text and it is very common to store a range in a struct or similar, and to want to do something like let line_text = &buffer[line.range]. Cloning works, but it feels wrong.

[BurntSushi]

@cmyr Yeah, same, which has led to things like this: https://docs.rs/grep-matcher/0.1.4/grep_matcher/struct.Match.html#indexing

[Diggsey]

Presumably, with the necessary compiler support, we could backwards-compatibly add IntoIterator implementations for the Range types which return RangeIter wrappers that are !Copy, and then add a compiler warning whenever the Iterator implementation of Range is actually used.

Once a warning exists, implementing Copy for Range would not be such a footgun.

[BurntSushi]

and then add a compiler warning whenever the Iterator implementation of Range is actually used.

I think this particular cure might be worse than the disease unfortunately. Using ranges as iterators is not only convenient but very common. Reversing course on that would likely be 1) justifiably unpopular and 2) cause a lot of churn.

Errmm, perhaps not. Maybe the common case is indeed in the context where IntoIterator would work...

[Diggsey]

One option to reduce churn would be to combine this with an edition change: edition 2018 would warn if the Copy trait is used, and edition 2021 would warn if the Iterator trait it used.

This way existing code will continue to work without warnings.

[mitsuhiko]

For posterity this issue gained some increased interest due to this blog post recently: https://ridiculousfish.com/blog/posts/least-favorite-rust-type.html which was discussed on Hacker News and Reddit.

[eddyb]

We don't want iterators to be Copy because they are stateful objects, and a Copy stateful object can be copied accidentally, causing unexpected behavior.

I can't find it now but I recall the concern being mostly about for x in range {...} not mutating range once we had introduced IntoIterator, and that being a papercut?

Isn't that solved with a very specific lint? Quoting myself from HN:

What it'd need to do is look for IntoIterator::into_iter(x) calls expanded from for loops, where x is a variable of a Copy type. And maybe look for mentions of the same x after the loop.

[mitsuhiko]

@eddyb I'm actually curious now why an iterator should not be copy. Mostly because I would have expected if that was an actual concern in practice we would have seen a clippy lint against it by now.

[shepmaster]

if that was an actual concern in practice

https://stackoverflow.com/q/23969191/155423

[eddyb]

I suppose we can generalize the lint to "calling a by-value method (including for loops' into_iter call) on an iterator" followed by "original variable is later used again". At this point it might be easiest to implement this lint on MIR, just so it can handle things like "the later use is the same one, but in a different iteration of an outer loop".

I wouldn't even mind making into_iter or adapter methods (like take_while mentioned above) move their self argument even if it's Copy (well, it would have to be limited to types that aren't Copy today, through some other trait), the copies I want to do of Range or other iterators tend to not be in the vicinity of using them as iterators, so I could still do for i in range.clone() if I really want to iterate on a copy of range, without impacting most of the ergonomics wins elsewhere.

---

But if we want to ignore Iterator/IntoIterator and just focus on the types, we can do something way simpler:

We could introduce a trait MustClone: Copy {} that lets e.g. Range satisfy Copy bounds (for generics, derives, etc.), but you can't actually copy it yourself (or it's linted against, I suppose - point is, we have choices), and you have to .clone() instead.

As another bikeshed entry, it could be ShouldClone instead of MustClone.
(maybe even #[must_use] should've been #[should_use]?)

[pickfire]

cc @ridiculousfish who may be interested in this since he wrote the post

[burdges]

If I understand, there are two choices here, either some wrapper that makes all range types Iterator + !Copy

pub struct RangeIter<T>(T);

or else a wrapper that makes range types Copy + !Iterator

pub struct CopyRange<T>(T);

In either case, could the various range short hands 0..x, etc. yield both the wrapped or unwrapped type, depending upon context?

Abstractly CopyRange looks less elegant. And it causes the warts from that blog post.

Yet, there lots of code like (x..y).map(|i| ..) out there I think. I'd even suspect (x..y).iter().map(|i| ...) would occur more often under RangeIter than most desirable copies of range types listed in that blog post. And CopyRange might break less existing code?

Also, could CopyRange<T>: Deref<Target=T>+DerefMut or does this recreate the copy breaking iterators thing? If this worked, then maybe it's an advantage for CopyRange over RangeIter.

[eddyb]

@burdges To be clear, my MustClone idea doesn't require introducing a wrapper, nor does it run into the "ranges no longer implement Iterator" backwards incompatibility.

I'll try implementing it soon and open a PR, so that we can at least e.g. do a Crater run, and judge it on its merits.

[eddyb]

Opened rust-lang/rust#77180 for the MustClone idea, in its simplest implementation.

[programmerjake]

I was thinking: Why use impl MustClone for T instead of #[must_clone] like the rest of the lints?
(#[must_use], #[must_not_await], etc.)

[eddyb]

@programmerjake I think there were issues with those attributes that relying on traits could've resolved, but also it doesn't really matter either way, an attribute could also work, the only difference is if we ever stabilize it.

[programmerjake]

@programmerjake I think there were issues with those attributes that relying on traits could've resolved, but also it doesn't really matter either way, an attribute could also work, the only difference is if we ever stabilize it.

I think we should plan on stabilizing it as an attribute, since I've also had iterators that could be Copy, but weren't. There are also other iterators in the standard library that can be Copy such as str::Chars and slice::Iter.

[eddyb]

Update on the experiment I was doing in rust-lang/rust#77180: Range<_>: Copy appears to be backwards-compatible, like I was hoping it would be (see rust-lang/rust#77180 (comment)).

Quoting myself from that PR:

So we should be able to proceed here with an RFC or similar - though at the moment I don't have the bandwidth for anything like that, but if someone is interested in writing a #[must_clone] / trait MustClone RFC, feel free to show me drafts etc.

Importantly, I don't have a strong opinion on "attribute vs trait", and both implementation strategies should work (the attribute might be slightly easier even). I'd suggest looking for previous discussions of #[must_use] deficiencies (sadly I only have a vague memory of there being some discussion), or starting a t-lang thread on Zulip to discuss attribute vs trait.

[eddyb]

If anyone is wondering, part of the reason adding Copy impls is backwards-compatible is, well, we future-proofed for it:

trait Trait {}
impl<T: Copy> Trait for T {}
impl Trait for std::ops::Range<usize> {}

That snippet produces (on playground) an error with this note:

upstream crates may add a new impl of trait std::marker::Copy for type std::ops::Range<usize> in future versions

[eddyb]

Because Copy is a marker trait (no associated items), and its absence doesn't confer any additional powers (in general we try to avoid negative reasoning, I think - also see the previous comment where I show coherence is already future-proofed), I believe we can implement Copy on Range and feature-gate it.

While we still can't feature-gate individual impls without running into the complexity of all possible trait system interactions (and how it may behave across crates), we could "just" pretend Copy impls aren't there for types marked with #[must_clone], unless the feature-gate, e.g. #![feature(must_clone_copy_impls)] (bikeshed-ready name) is enabled.

There's one issue I see with this: if a dependency uses #![feature(must_clone_copy_impls)], definitions from it may result in ICEs when used/codegen'd in a downstream crate without the feature-gate. And I can think of two mitigations:

1. avoid the feature in the standard library - this should avoid any cross-crate interactions for users which don't touch the feature-gate (or are on beta/stable), though it would limit dogfooding
2. only hide the #[must_clone] + Copy impls in Reveal::UserFacing mode (i.e. type-checking, borrow-checking, lints), not Reveal::All mode (everything else, including MIR optimizations, miri, codegen, etc.) - that way, MIR from dependencies should continue to codegen correctly, even in downstream crates without the feature-gate
   • this should make mitigation 1. irrelevant but we might still want to be careful about it

cc @nikomatsakis @matthewjasper Do you have any opinions on this strategy? I think if we can feature-gate Range<_>: Copy, we can land it much sooner, and go through the normal stabilization process.

[Ekleog]

I know the timeline is most likely OK, but I just want to point out that once specialization lands, we will have negative reasoning, and so such a change would no longer be backwards-compatible.

[Nadrieril]

Since there was talk of introducing new traits. I wanted to share what I think is the real problem: Copy conflates two things. One would be a CloneIsMemcpy trait, which is only useful for perf, and the other is a AutoClone trait, which says that dereferencing a &T is allowed and automatically inserts a call to clone(). I don't believe we need to require CloneIsMemcpy to allow an AutoClone impl. As long as the clone is cheap enough, being able to elide it syntactically is a huge convenience boost.
So Range would be CloneIsMemcpy but not AutoClone. A wrapper struct around it would be able to have both traits. I think there are also many things that are not Copy but could be AutoClone, notably Rc or Gc smart pointers. People might disagree on whether that's a good idea, but at least one could make a wrapper struct that contains an Rc and does implement AutoClone.
I have no idea if this can be done backwards-compatibly, but sounds fun. Has something like this been suggested anywhere?

[Diggsey]

@Nadrieril this seems completely orthogonal to the Range/Copy problem, since the problem with iterators being Copy is related to what you are calling AutoClone, so splitting Clone into AutoClone and CloneIsMemCopy does nothing to solve the problem.

[Nadrieril]

If the original problem was

I want to store a Range in a struct, but that prevents me from making the struct Copy

then the fact that Range is CloneIsMemcpy allows:

#[derive(Clone, CloneIsMemcpy, AutoClone)]
struct HasRange {
    r: Range<usize>,
}

which makes that wrapping struct behave exactly like Copy does today.

If the original problem was that we wanted Range to behave like AutoClone in some cases but not when used as an iterator, then ok fair enough my idea doesn't help.

[KodrAus]

We've discussed this at recent Libs meetings and considered using an edition to switch the type produced by range (.., ..=) syntax to new distinct set of "fixed" range types that implement Copy and IntoIterator instead of Iterator.

I think @sfackler had some thoughts on how we could do that.

[programmerjake]

We've discussed this at recent Libs meetings and considered using an edition to switch the type produced by range (.., ..=) syntax to new distinct set of "fixed" range types that implement Copy and IntoIterator instead of Iterator.

I think @sfackler had some thoughts on how we could do that.

some additional benefits are that all fields of the new range types can be public, since they don't need extra hidden fields to track whether the last item has been returned for inclusive ranges.

[eddyb]

We've discussed this at recent Libs meetings and considered using an edition to switch the type produced by range (.., ..=) syntax to new distinct set of "fixed" range types that implement Copy and IntoIterator instead of Iterator.

I think @sfackler had some thoughts on how we could do that.

I missed this, sorry, but that doesn't address why iterator types aren't Copy?

The original concern is that something like this could be written:

let iter = 0..10;
for i in iter {
    if i == 5 { break; }
}
for _ in iter {}

And instead of mutating iter, what happens (thanks to for copying/moving the iterable) is both loops iterate ten times each.

What has been suggested over the years is a lint, and the MustClone idea (first described in #2848 (comment) AFAIK) is a generalization of such a lint, and even turning it into an error.

That is, Range<_>: MustClone would force the above to be written like this (same as today):

let iter = 0..10;
for i in iter.clone() {
    if i == 5 { break; }
}
for _ in iter {}

Whereas just changing the expansion of i..j into a new type that implements Copy + IntoIterator, doesn't really do anything.
The "unwanted" example still compiles and with no warnings. On top of that, you can't apply MustClone anymore! (without making the "not an iterator" type itself MustClone, that is, which feels like an ergonomic downgrade)

[Kimundi]

Given the recent developments in rust-lang/rust#84513, would it be possible to apply a similar hack to transition to new range types that don't implement Iterator?

[bstrie]

@Kimundi there was a recent Zulip thread on whether to pursue this for the 2021 edition: https://rust-lang.zulipchat.com/#narrow/stream/268952-edition-2021/topic/range.20reform

The gist is that this issue isn't really blocked on how to implement it, it's blocked on what to implement. WRT a new type that implements Copy but not Iterator, objections were raised about (0..10).map( being forced to be rewritten as (0..10).into_iter().map( (and replace map with every other Iterator method). It's an ergonomics tradeoff.

WRT implementation strategy, that Zulip thread discusses sfackler's draft RFC for this issue, which predates the edition-dependent IntoIterator strategy: https://hackmd.io/cM22mZ5JRH2RAdSART8bWQ?view#Reference-level-explanation . That strategy might be worth taking into consideration for a future version of the RFC, but it doesn't appear to be strictly necessary.

Also note that eddyb's MustClone proposal could be implemented without an edition change (although it too makes an ergonomic tradeoff).

[jyn514]

objections were raised about (0..10).map( being forced to be rewritten as (0..10).into_iter().map( (and replace map with every other Iterator method)

map could be an inherent method. How many of the iterator methods are people actually using on ranges? I'd be surprised if it were much besides map/sum/product.

[tgross35]

There may be some interest in waking this idea up for edition 2024: rust-lang/lang-team#209

[kadiwa4]

@tgross35 Considering that editions are configured for each crate individually, removing the Iterator impl over an edition boundary doesn't make sense. Here's a simple example of what I mean

[tgross35]

There is a pre-RFC proposing to make this change: https://internals.rust-lang.org/t/pre-rfc-fixing-range-by-2027/19936/25