Stream: t-libs

Topic: RangeInclusive representation: #67194


pnkfelix (Feb 03 2020 at 22:52, on Zulip):

hey @simulacrum , your note about removing fn canonicalized_is_empty led me to a thought ...

pnkfelix (Feb 03 2020 at 22:53, on Zulip):

would it be bonkers to have an associated type be in charge of tracking the is_empty-ness of the iterator that is implicitly associated with the range?

simulacrum (Feb 03 2020 at 22:54, on Zulip):

hm, so like

struct RangeInclusive<Idx: SomeTrait> {
    start: Idx,
    end: Idx,
    is_empty: Idx::Empty,
}
pnkfelix (Feb 03 2020 at 22:54, on Zulip):

so instead of having it be Option<bool>, it would instead be Trait::IterState, which would be bool for integer types, and () for other stuff ?>

pnkfelix (Feb 03 2020 at 22:54, on Zulip):

Yeah exactly

pnkfelix (Feb 03 2020 at 22:55, on Zulip):

i don't know if this would actually resolve the problem here

simulacrum (Feb 03 2020 at 22:55, on Zulip):

I'm not sure if we can add that backwards-compatibly

pnkfelix (Feb 03 2020 at 22:55, on Zulip):

I find the backwards-compatibility situation here very murky

simulacrum (Feb 03 2020 at 22:56, on Zulip):

i.e., even if we have impl<T> SomeTrait for T {} then I imagine you still need T: SomeTrait if you have struct SomeRangeContainer<T> { range: RangeInclusive<T> }, right?

pnkfelix (Feb 03 2020 at 22:56, on Zulip):

ah yeah, it would have to be something everybody implements

simulacrum (Feb 03 2020 at 22:56, on Zulip):

(I guess it would be default impl<T> SomeTrait for T {}

simulacrum (Feb 03 2020 at 22:56, on Zulip):

my point is that we can't add that bound backwards compatibly I think

pnkfelix (Feb 03 2020 at 22:56, on Zulip):

right. But maybe even worse, it might have to be something like Sized

pnkfelix (Feb 03 2020 at 22:57, on Zulip):

yeah I retract my suggestion now.

simulacrum (Feb 03 2020 at 22:57, on Zulip):

I think if we were to go down that path I would just eagerly compute the emptiness for integers in the constructor

simulacrum (Feb 03 2020 at 22:57, on Zulip):

i.e., we do that calculation up front

Jonas Schievink (Feb 03 2020 at 22:57, on Zulip):

it does work if you have a blanket impl that applies to all types

pnkfelix (Feb 03 2020 at 22:58, on Zulip):

yeah but then we'd be doing somethinig involving specialization of an associated type

Jonas Schievink (Feb 03 2020 at 22:58, on Zulip):

ie. this compiles

struct Inner<T: Trait>(T);

trait Trait {}
impl<T> Trait for T {}

struct Outer<T> {
    inner: Inner<T>,
}
Jonas Schievink (Feb 03 2020 at 22:58, on Zulip):

true

simulacrum (Feb 03 2020 at 22:59, on Zulip):

huh, I would.. not have expected that

simulacrum (Feb 03 2020 at 22:59, on Zulip):
trait Foo {
    type Assoc;
}

impl<T> Foo for T {
    type Assoc = Option<bool>;
}

struct Assoc<T: Foo> { value: T::Assoc }

struct Bar<T>(Assoc<T>);
pnkfelix (Feb 03 2020 at 22:59, on Zulip):

I think if we were to go down that path I would just eagerly compute the emptiness for integers in the constructor

I assume there's some argument against doing this that's already been posted somewhere?

simulacrum (Feb 03 2020 at 22:59, on Zulip):

@pnkfelix well, it still needs specialization

simulacrum (Feb 03 2020 at 23:00, on Zulip):

and arguably if we go down that road then we are basically saying "if you're not an integer your PartialEq is just broken"

simulacrum (Feb 03 2020 at 23:00, on Zulip):

otoh, I don't even know of many uses for PartialEq on ranges

pnkfelix (Feb 03 2020 at 23:00, on Zulip):

hmm, i would nonetheless worry about breaking it

simulacrum (Feb 03 2020 at 23:00, on Zulip):

it = ? in that?

pnkfelix (Feb 03 2020 at 23:01, on Zulip):

I would worry about breaking PartialEq on ranges.

pnkfelix (Feb 03 2020 at 23:01, on Zulip):

(even for non-integers)

simulacrum (Feb 03 2020 at 23:01, on Zulip):

hm, sure -- my proposal does not do so (or at least not known cases), but hash the Hash/Eq problem

pnkfelix (Feb 03 2020 at 23:01, on Zulip):

Though I do think the situation of having it be iteration sensitive would not have been so bad

pnkfelix (Feb 03 2020 at 23:02, on Zulip):

i.e. this conversation, I think, could have been dealt with via messaging

pnkfelix (Feb 03 2020 at 23:02, on Zulip):

(and allowing r == (r.start()..=r.end()) to not always be true)

simulacrum (Feb 03 2020 at 23:02, on Zulip):

To be clear:

fn reflexive(r: RangeInclusive) -> bool {
    r == (r.start()..=r.end())
}

is not always true today

simulacrum (Feb 03 2020 at 23:03, on Zulip):

because (u8::max_value()..=u8::max_value()).next() != (u8::max_value()..=u8::max_value())

simulacrum (Feb 03 2020 at 23:03, on Zulip):

and based on testing there's no sentinel value or anything for performance reasons

pnkfelix (Feb 03 2020 at 23:03, on Zulip):

wow, wait, I thought part of the goal of the current design was to achieve that reflexivity property

simulacrum (Feb 03 2020 at 23:04, on Zulip):

my understanding is that the goal is a bit different

simulacrum (Feb 03 2020 at 23:04, on Zulip):

(I used to think like you did, so my prior comments may have been unclear)

simulacrum (Feb 03 2020 at 23:05, on Zulip):

because AFAIK we cannot guarantee reflexivity like that (emptiness is a property not represented by it)

simulacrum (Feb 03 2020 at 23:05, on Zulip):

i.e., start and end are insufficient to faithfully inform about the whole state of a RangeInclusive

pnkfelix (Feb 03 2020 at 23:06, on Zulip):

yeah. I was mostly figuring we would just accept that the x..=y form is incapable of expressing all possible RangeInclusives

simulacrum (Feb 03 2020 at 23:06, on Zulip):

What we are trying to do, and I believe accomplish today, is:

Right. Both "compares equal when reconstructed form accessors" and "yields the same items if compares equal" seem desirable, but we can’t have both with this PR’s three-fields design. (https://github.com/rust-lang/rust/pull/51622#discussion_r196513565)

simulacrum (Feb 03 2020 at 23:06, on Zulip):

er, specifically, the latter

simulacrum (Feb 03 2020 at 23:06, on Zulip):

i.e. that if PartialEq == true, then self.next() == other.next()

pnkfelix (Feb 03 2020 at 23:08, on Zulip):

(gottta go AFK)

simulacrum (Feb 03 2020 at 23:09, on Zulip):

I think my impl does not satisfy that fully though, as ((self.start == self.end) == (other.start == other.end)) is a necessary but insufficient condition for determining emptiness, so it would not work.

simulacrum (Feb 03 2020 at 23:10, on Zulip):

And indeed, it does make sense that determining emptiness requires PartialOrd/Step in the general case.

pnkfelix (Feb 05 2020 at 15:01, on Zulip):

To me it seems like there's a fundamental design bug somewhere here. Either in the fact that ranges are iterators (vs implementing IntoIterator), or in the fact that ranges don't require PartialOrd for their Idx

pnkfelix (Feb 05 2020 at 15:02, on Zulip):

(and I wonder whether we could address such design bugs via an edition change? Not sure.)

simulacrum (Feb 05 2020 at 15:16, on Zulip):

@pnkfelix I think there is a design bug, yes, or at least an unfortunate reality. I think we have no mechanism that allows us to change std via edition mechanisms (though I've long thought about trying to design something, just never had the time)

kennytm (Feb 05 2020 at 15:16, on Zulip):

the only possible edition change is make x..=y return a different type which is IntoIterator but not Iterator.

simulacrum (Feb 05 2020 at 15:21, on Zulip):

hm, I think we can't even really do that without breaking a bunch of code that has let foo: RangeInclusive<usize> = x..=y right?

simulacrum (Feb 05 2020 at 15:21, on Zulip):

fixably, in theory, but seems too big a change for editions

kennytm (Feb 05 2020 at 15:24, on Zulip):

yeah that would be a disruptive change. i just mean it is "possible" (unlike removing Iterator from RangeInclusive which out right requires Rust 2.0) :upside_down:

simulacrum (Feb 05 2020 at 15:26, on Zulip):

my thoughts in this direction have been to make it not possible to use that impl (i.e., the compiler ignores its existence) in the next edition, with the thought being that since (to my knowledge) you can't test for lack of a trait impl positively that might work out fine

centril (Feb 06 2020 at 02:28, on Zulip):

let foo: RangeInclusive<usize> = x..=y seems unlikely to be common

centril (Feb 06 2020 at 02:29, on Zulip):

if we could make edition changes for modules I certainly think we can for this

centril (Feb 06 2020 at 02:29, on Zulip):

whether it's a good idea is a different matter

kennytm (Feb 06 2020 at 03:09, on Zulip):

well you could also allow coercion from NewRangeInclusive<X> to RangeInclusive<X> :upside_down:

pnkfelix (Feb 06 2020 at 16:25, on Zulip):

in the meantime: PR #68835 looks good to me. We can just land it, right @simulacrum ? (I don't think it needs a backport or anything, since its not like we've seen this weaponized in practice...")

simulacrum (Feb 06 2020 at 16:27, on Zulip):

@pnkfelix possibly modulo test ignoring

simulacrum (Feb 06 2020 at 16:27, on Zulip):

I'll take a look today and try to approve it

pnkfelix (Feb 06 2020 at 16:27, on Zulip):

Oh I thought they added that, but did not actually confirm with eyes

simulacrum (Feb 06 2020 at 16:28, on Zulip):

I think there was a couple iterations

Last update: Feb 25 2020 at 03:25UTC