It's weird that cmp::Ord methods can't take &const T without purity.

[bblum]

I am hacking up a fibonacci heap implementation, in which all the nodes are @mut cells, and unless I want to grow T:Copys all over the place, comparing against data already in the heap is impossible, because today you need immutable pointers to use Ord.

[nikomatsakis]

You should be able to freeze @mut data.

[bblum]

Hmm, patrick points out that since now &mut T is borrowable to &T this is a non-issue. Ignore me (for now)!

[bblum]

Actually I think that only helps a little bit. Using cmp::Ord by going through &mut is "dangerous" when the base data is inside an @mut box. The danger could be avoided if cmp::Ord methods took &const T.

[nikomatsakis]

What is dangerous about it? It is no problem to freeze data more than once. Also, cmp::Ord can't take &const T---what if T contains a ~[T]? You couldn't compare the elements of that array for fear it would be overwritten.

[nikomatsakis]

(Presuming we remove purity, by the way)

[nikomatsakis]

(It is also true that if an @mut were already borrowed as an &mut you couldn't compare it, but that is indeed the general @mut contract.)

[bblum]

let (x,y) = (@mut 5, @mut 7);
let (xp,yp) = (&mut *x, &mut *y);
assert xp.lt(yp);
make_bigger(x,y);
assert yp.lt(xp);

fn make_bigger(x: @mut int, yp: @mut int) {
    if (x.lt(y)) { *x = *y + 1 }
}

This should fail inside make_bigger because xp,yp are still active, no?

[nikomatsakis]

Yes, this will fail.

[nikomatsakis]

The fact that this code will fail is only incidentally related to cmp::Ord, however. This is simply not using @mut and &mut the way they are intended to be used. Changing cmp::Ord to take &const will not solve this problem, though it may ease it in some scenarios (not this one, I might note). But it will cause cmp::Ord to be inapplicable to any type that contains ~T (unless we retain purity). But if we retain purity, we might as well leave cmp::Ord as &T, because purity allows an &const T to be safely cast to an &'r T so long as the function is pure for 'r. So in short, I think what you are really saying is that we should remove the write barrier portion of INHTWAMA and keep purity instead, which seems like a separate discussion.

[nikomatsakis]

Sorry, I shouldn't have phrased as that last sentence as "what you are really saying". It sounds hostile and I don't mean to put words in your mouth. What I mean is, "So in short, I think that the real question is whether to keep the write barrier approach or to use purity".

[nikomatsakis]

(In case it's unclear, I still favor the write barriers over purity. For one thing, if we removed the dynamic write barriers, you simply would not be able to convert an @mut T to an &mut T (unenforceable), and so the program in question would be illegal for that reason. But that would make it much harder to write generic code that operates on mutable data where it is found in the heap. We'd need an &alias mut or else &own or something like that. Essentially the INHTWAMA idea sort of unravels, and I think the result is a noticeably more complex type system that will be harder to use. But I guess the jury is out on whether the current dynamic behavior winds up being harder to get running.)

[bblum]

Hmm, I had thought this would just be a library gripe rather than going down to the system itself. It didn't occur to me that &const ~Ts couldn't be dereferenced (and I'm not sure if I yet understand why?). Am I correct in guessing that fn lt(&const T, &const T) would be appropriate for the old, purity system, but is no longer?

If so I will continue hacking on my fibonacci heap and see if needing to go from @mut to &mut to compare elements gets in my way anywhere else. :)

(Also, if so, I wonder -- what use remains for &const under INHTWAMA?)

[nikomatsakis]

I hope to remove &const as well as purity. You do know how you could re-code that example you gave so that it works, right?

[nikomatsakis]

The reason you can't take the address of a dereference an &const ~T (without purity) is that you can't be sure someone else doesn't have an identical &mut ~T. In that event, they might mutate it and invalidate your pointer.

[nikomatsakis]

(More accurately, what's illegal is &const **x where x has type &const ~T, but that's what Eq would need to do to recurse and compare the type T)

[bblum]

You do know how you could re-code that example you gave so that it works, right?

Yeah, in the specific example it is clear. But I am worried that the example could be a simplified version of something someone might run into, where the problem is buried underneath some layers of abstraction (e.g., they want to put @mut Ts inside of one data structure, and &Ts inside of another). Then the system would be violating the principle of least surprise (compared to an immediate but obtuse compiler error).

[bblum]

what's illegal is &const **x where x has type &const ~T, but that's what Eq would need to do to recurse and compare the type T

Oh, oh, I understand. Eq/Ord needs to do a &const **x borrow (which makes no sense for the same reason that option::get_mut_ref would make no sense) because an implementation of it might have to do a dispatch on a contained type.

So because eq/ord with &const would no doubt be fine under the purity system (because they don't take user-provided closures to call), it would be safe to write them taking &const in this system and doing something unsafe inside, right? (Of course it wouldn't be fair to ask user-provided eq implementations to do that, though.)

[nikomatsakis]

Yes.

[catamorphism]

I don't understand this entire discussion, but it seems like the issue will go away when const and/or pure are removed, so I'm closing. In the subject line, RFCs should propose something specific that needs to be changed, rather than making a declarative statement about an existing problem (the latter would be a bug, not an RFC).