RFC: make default comparisons as deep as a clone

[thestinger]

Traversing @ will recurse forever if there's a cycle. It would be more consistent to use owned trees as the building block for everything, and avoid just having a special case for Clone. There shouldn't be a default Ord/TotalOrd for @t at all imo, just Eq/TotalEq for identity comparison or no default impl.

A different form of equality is still easy to implement, you just wouldn't be able to derive deep equality and shoot yourself in the foot as easily.

[thestinger]

I think at least removing the overloaded operators that can recurse forever should be done soon, before it's too painful.

[nikomatsakis]

This sounds reasonable at first, but I'm not sure if I agree with this. It seems to rule out very legitimate use cases. In the borrow checker, for example, we build up little trees representing loan paths. I use @ because it's convenient. And I compare them for equality. It seems like we wouldn't be able to do that under this proposal, because we would already have hardwired @ comparison to be pointer only.

Maybe I'm too blase about infinite loops, but I kind of feel like cycles in eq are....not our problem. You can always implement your own version of Eq for types that may contain cyclic references, nobody forced you to derive it.

[thestinger]

@nikomatsakis: well, we could do what python does and figure out a way to keep a table of pointers in TLS while recursing. In a situation where it's easily provable (via Owned or Const) that there aren't cycles, there's std::rc as an alternative so I don't think it would be that bad.

[nikomatsakis]

Isn't this only an issue for @mut? After all, any cycle must have a mutable link somewhere. Perhaps we can simply say that @mut (and perhaps &mut too) compares for pointer equality, while @ compares deeply. This seems consistent to me: value-like things are compared in a value-like way, mutable-identity-holding-things are compared in an identity-like way.

[thestinger]

@nikomatsakis: it's an issue for @ too because you can put a non-Const thing like @mut or Cell inside it and use that to sneakily make a cycle.

[nikomatsakis]

Yes, I was thinking that my logic was flawed. However, if we just don't define Eq for Cell or @mut at all, there is no problem.

[thestinger]

@nikomatsakis: we could potentially just define Eq, Ord, etc. for @T and @mut T where T is Const or Owned (much like I plan on doing for storing any type in std::rc), and then figure out a way to deal with cycles for non-Const, non-Owned types later. I have a DeepClone trait in a pull request right now with the same issue for managed boxes (so I left out an impl).

[nikomatsakis]

Yes. I'd be fine with that as well. If we updated the coherence check as I'm contemplating doing, this would also mean that end users can define Eq for @t where T is non-Const types as they choose.

[thestinger]

Closing this RFC, I think we've come to a better solution of only providing default impls on types known to be non-cyclic.