New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tracking issue for Range*::contains #32311

Open
alexcrichton opened this Issue Mar 17, 2016 · 29 comments

Comments

Projects
None yet
@alexcrichton
Member

alexcrichton commented Mar 17, 2016

Tracking issue for rust-lang/rfcs#1434.

Unresolved questions:

  • What to do about Wrapping ranges.

Implementation work:

  • Heterogeneous comparisons
  • Should take a reference
@ticki

This comment has been minimized.

Contributor

ticki commented Mar 17, 2016

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

@alexcrichton

This comment has been minimized.

Member

alexcrichton commented Mar 17, 2016

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

@ticki

This comment has been minimized.

Contributor

ticki commented Mar 17, 2016

Well, okay. Fine.

@ticki

This comment has been minimized.

Contributor

ticki commented Mar 17, 2016

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

@durka

This comment has been minimized.

Contributor

durka commented Mar 19, 2016

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

@alexcrichton

This comment has been minimized.

Member

alexcrichton commented Mar 19, 2016

For consistency, yeah, seems prudent.

nodakai added a commit to nodakai/rust that referenced this issue Mar 21, 2016

Add core::ops::Range*::contains() as per rust-lang#32311
Signed-off-by: NODA, Kai <nodakai@gmail.com>

nodakai added a commit to nodakai/rust that referenced this issue Mar 22, 2016

Add core::ops::Range*::contains() as per rust-lang#32311
Signed-off-by: NODA, Kai <nodakai@gmail.com>

nodakai added a commit to nodakai/rust that referenced this issue Mar 24, 2016

Add core::ops::Range*::contains() as per rust-lang#32311
Signed-off-by: NODA, Kai <nodakai@gmail.com>

bors added a commit that referenced this issue Mar 25, 2016

Auto merge of #32396 - nodakai:range-contains, r=alexcrichton
Add core::ops::Range*::contains() as per #32311

bors added a commit that referenced this issue Mar 25, 2016

Auto merge of #32396 - nodakai:range-contains, r=alexcrichton
Add core::ops::Range*::contains() as per #32311
@Kimundi

This comment has been minimized.

Member

Kimundi commented Apr 7, 2016

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

This comment has been minimized.

Contributor

josephDunne commented Jul 7, 2016

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)));
}
false
Program ended.
@ExpHP

This comment has been minimized.

Contributor

ExpHP commented Aug 9, 2016

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

This comment has been minimized.

Member

alexcrichton commented Nov 1, 2016

@rfcbot fcp merge

Seem like nifty methods to stabilize!

@rfcbot

This comment has been minimized.

rfcbot commented Nov 1, 2016

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

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

This comment has been minimized.

Contributor

brson commented Nov 4, 2016

@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

This comment has been minimized.

Member

alexcrichton commented Nov 4, 2016

@rfcbot fcp cancel

Ok, sounds like these aren't ready yet.

@rfcbot

This comment has been minimized.

rfcbot commented Nov 4, 2016

@alexcrichton proposal cancelled.

@scottmcm

This comment has been minimized.

Member

scottmcm commented Dec 7, 2016

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

This comment has been minimized.

Contributor

regexident commented Feb 25, 2017

Any status update on this?

@Kixunil

This comment has been minimized.

Kixunil commented Jun 29, 2017

Ping?

@alexcrichton

This comment has been minimized.

Member

alexcrichton commented Jun 30, 2017

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

@regexident

This comment has been minimized.

Contributor

regexident commented Jun 30, 2017

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

@Kixunil

This comment has been minimized.

Kixunil commented Jun 30, 2017

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

@alexcrichton

This comment has been minimized.

@lukaramu

This comment has been minimized.

Contributor

lukaramu commented Aug 6, 2017

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

This comment has been minimized.

Member

varkor commented Dec 31, 2017

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

This comment has been minimized.

Member

varkor commented Jan 3, 2018

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

This comment has been minimized.

Riamse commented Jan 29, 2018

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

This comment has been minimized.

Contributor

smmalis37 commented Mar 17, 2018

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

This comment has been minimized.

Kixunil commented Apr 8, 2018

@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.

bors added a commit that referenced this issue Apr 16, 2018

Auto merge of #49130 - smmalis37:range, r=alexcrichton
Move Range*::contains to a single default impl on RangeBounds

Per the ongoing discussion in #32311.

This is my first PR to Rust (woo!), so I don't know if this requires an amendment to the original range_contains RFC, or not, or if we can just do a psuedo-RFC here. While this may no longer follow the explicit decision made in that RFC, I believe this better follows its spirit by adding the new contains method to all Ranges. It also allows users to be generic over all ranges and use this method without writing it themselves (my personal desired use case).

This also somewhat answers the unanswered question about Wrapping ranges in the above issue by instead just punting it to the question of what those types should return for start() & end(), or if they should implement RangeArgument at all. Those types could also implement their own contains method without implementing this trait, in which case the question remains the same.

This does add a new contains method to types that already implemented RangeArgument but not contains. These types are RangeFull, (Bound<T>, Bound<T>), (Bound<&'a T>, Bound<&'a T>). No tests have been added for these types yet. No inherent method has been added either.

r? @alexcrichton
@smmalis37

This comment has been minimized.

Contributor

smmalis37 commented Apr 18, 2018

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

@smmalis37

This comment has been minimized.

Contributor

smmalis37 commented Apr 18, 2018

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment