Rust: Tracking issue for Range*::contains

[alexcrichton]

Tracking issue for https://github.com/rust-lang/rfcs/pull/1434.

Unresolved questions:

• What to do about Wrapping ranges.

Implementation work:

• Heterogeneous comparisons
• Should take a reference

[ticki]

I am unsure what part of the rfc was accepted. Is the contains method for iterators accepted?

[alexcrichton]

The accepted portion of an RFC is the detailed design, which in this case only deals with ranges, not iterators.

[ticki]

Well, okay. Fine.

[ticki]

It is in fact also compatible with future extension to iterators.

[durka]

Should this be implemented for (unstable) RangeInclusive and RangeToInclusive as well?

[alexcrichton]

For consistency, yeah, seems prudent.

[Kimundi]

Hm, I just used this and expected it to take &Idx instead of Idx, in case you have a range of non-copyable types.

Looking back the RFC, it does not seem to consider this case - was there any discussion for this possibility?

[josephDunne]

Hi, This RFC doesn't address Wrapping numbers. Is this intended? For example this gist returns false which is not intuitive (albeit correct with regards to PartialOrd)

#![feature(range_contains)]
use std::ops::Range;
use std::num::Wrapping;
use std::u32;

fn main() {
    let r1: Range<Wrapping<u32>> = Range{ start: Wrapping((u32::MAX - 100)), end: Wrapping(100) };
    println!("{}", r1.contains(Wrapping(u32::MAX)));
}

Program ended.

[ExpHP]

Hm, my elation turned into sadness today when I added a contains method to my own iterator extension trait, only to find that _it somehow shadowed the inherent method on Range:_

src/grid/hexagonal.rs:63:43: 63:44 note: expected type `&usize` 
src/grid/hexagonal.rs:63:43: 63:44 note:    found type `usize` 
src/grid/hexagonal.rs:63:43: 63:44 note: expected &-ptr, found usize 
src/grid/hexagonal.rs:63        debug_assert!((0..self.height).contains(r));
                                                                        ^

I can only imagine that method resolution works this way for the sake of backwards compatibility, but... yikes!

Since this change is "compatible with future extension to iterators," I take it that there is a way to implement an Iterator::contains which accepts either a Self::Item or &Self::Item? If so, then I am glad that I was unable to come up with that signature when I wrote my own!

[alexcrichton]

@rfcbot fcp merge

Seem like nifty methods to stabilize!

[rfcbot]

Team member @alexcrichton has proposed to merge this. The next step is review by the rest of the tagged teams:

• [ ] @BurntSushi
• [ ] @Kimundi
• [x] @alexcrichton
• [ ] @aturon
• [ ] @brson
• [x] @sfackler

No concerns currently listed.

Once these reviewers reach consensus, this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[brson]

@rfcbot concern previous-questions

I see three previous comments asking about the API here. I don't know anything about this API but it's not obvious it's ready for stabilization.

[alexcrichton]

@rfcbot fcp cancel

Ok, sounds like these aren't ready yet.

[rfcbot]

@alexcrichton proposal cancelled.

[scottmcm]

A thought on contains: should it allow heterogeneous types, if comparable? (I didn't see a discussion in the RFC.) Like

impl<Idx, T> Range<Idx> where T:PartialOrd<Idx>, Idx:PartialOrd<T> {
    pub fn contains(&self, item: T) -> bool {
        (self.start <= item) && (item < self.end)
    }
}

So it's totally fine if Idx=T (the two constraints collapse to the current one, and a caller could just require Idx:PartialOrd), but would allow checking a BigRational in a Range<BigInteger> or similar, should they have comparisons defined, without needing to convert one to the other.

(Edit: adding backticks so the angle brackets show up)

[regexident]

Any status update on this?

[Kixunil]

Ping?

[alexcrichton]

The FCP for merge was canceled due to unresolved questions, and it looks like those unresolved questions have not been resolved.

[regexident]

@alexcrichton do you happen to have a summary of/link to those unresolved questions by chance?

[Kixunil]

The RFC suggests using a trait. I find it nicer. I'd also like something like what I did recently.

[alexcrichton]

• Should this take references?
• Should this work with Wrapping?
• Do custom types work

[chordowl]

With the RangeArgument (soon to be RangeBounds?) trait nearing stabilization (from what I can tell) (#30877), I don't think this should be stabilized in its current form (even if the other questions are resolved):

All Range* structs but RangeFull have a contains method (and RangeFull could (or should?) have a trivial one added, anyway). It seems rather unfortunate to implement something taking a RangeArgument, wanting to use contains, and then realizing/remembering that it's a method on the Range* structs and not on the trait. This is especially unfortunate since you can implement contains using just RangeArgument::start and RangeArgument::end.

~If I were to start from scratch, a Contains<T> trait (implied by RangeArgument) would seem like a good solution to me (especially since other types like str, slices, and collections also have contains methods).~ (Edit: I don't believe this anymore.) However, I am not sure if that would be doable with regard to stability (since adding it without implementing it for other types with stable contains methods seems more confusing than the current situation with Range*).

As a (more realistic?) alternative, Range*::contains could be moved to RangeArgument as a provided method, although I'm not sure how desirable that is if we'd ever want a proper Contains trait. I'd still prefer it over the status quo though.

I'm sure there are other ways, too.

[varkor]

Just regarding the questions about the current implementation:

1. I would definitely expect contains to take a reference — even aside from the issue non-copyable types, this is what slice::contains does, and we'd expect these to act consistently.
2. Similarly, from a usability standpoint, considering that heterogenous comparisons are being considered for slice::contains barring compatibility issues, it makes sense to also support them for Range::contains.
3. The Wrapping behaviour is clearly incorrect. The range should be inverted if start > end.

I'd suggest the most reasonable implementation would be something like:

impl<Idx> Range<Idx> {
    pub fn contains<T>(&self, item: &T) -> bool
            where Idx: PartialOrd, Idx: PartialOrd<T> {
        if self.start <= self.end {
            self.start <= *item && self.end > *item
        } else {
            self.start <= *item || self.end > *item
        }
    }
}

1 is going to break existing uses; 2 should be implementable without breaking anything; 3 changes behaviour, so would be a breaking change.

As the current implementation falls short of the expected behaviour, it seems to me like this is a change worth making.

[varkor]

Though I still feel it's better to handle the end < start case as it's more intuitive, technically this isn't even valid for the semantics of Range, which require that any x in range satisfies start <= x < end. This seems more of a problem with Wrapping, whose ordering is unintuitive (and arguably incorrect).

[Riamse]

It would be nice if you could make it a trait instead of a directly implemented method so that you can see if a range contains a number without having to worry about whether it's a RangeFull, Range, RangeFrom, etc. It would enable you to do something like

fn pi_in_range<T: ContainRange>(range: T) -> bool {
    range.contains(3.141592653589793238462643383)
}

// ...

assert!(pi_in_range(0.0 .. 10.0);
assert!(pi_in_range(..10.0);
assert!(!pi_in_range(10.0..);
assert!(pi_in_range(..);

[smmalis37]

I'd like to second @lukaramu's and others' comments above, I really think this should be moved to be a trait method on RangeArgument instead of implemented on each range type exclusively. There could probably even be a default impl that just depends on start and end and works for everything.

Edit: See my PR below which does this.

[Kixunil]

@lukaramu why you don't believe Contains<T> implied by RangeBounds wouldn't be good idea? I would love to see it implemented for sets (HashSet and BtreeSets). I'd agree that implementing it for slices and non-set collections would be weird.

[smmalis37]

The two Implementation Work items have now been done. The question about Wrapping types still remains.

[smmalis37]

My personal opinion on the question of Wrapping types: If you look at the new contains implementation it's hard to argue that it could be incorrect in some way. It seems completely reasonable to say that a range contains something iff that something is greater than the start and less than the end. If the Wrapping types don't work within these guidelines that feels to me more like a bug in their PartialOrd implementation. This could potentially be solved with specialization though.

[mbrubeck]

I'd like to suggest this for stabilization.

I agree with the previous comment that the current implementation is fine for Wrapping numbers. Wrapping has always meant "wraps on arithmethic overflow," and has never had any special effect on ordering or comparisons.

(If we had never implemented Ord and PartialOrd for Wrapping, then we could argue differently, but it is too late for that.)

[mbrubeck]

cc @SimonSapin

[SimonSapin]

The comments above on Wrapping sound good to me. Let’s stabilize as-in

@rfcbot fcp merge

[rfcbot]

Team member @SimonSapin has proposed to merge this. The next step is review by the rest of the tagged team members:

• [x] @Kimundi
• [x] @SimonSapin
• [x] @alexcrichton
• [x] @dtolnay
• [ ] @sfackler
• [ ] @withoutboats

No concerns currently listed.

Once a majority of reviewers approve (and none object), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[rfcbot]

:bell: This is now entering its final comment period, as per the review above. :bell:

[rfcbot]

The final comment period, with a disposition to merge, as per the review above, is now complete.