Allocator equality

[Amanieu]

https://github.com/rust-lang/rust/pull/103093#issuecomment-1316030920 brought up an interesting use case for testing whether two allocator instances of the same type are compatible. This came up in the context of appending two LinkedLists, which is only possible if they use the same underlying allocator.

One way to do this would be to require all implementations of the Allocator trait to implement Eq by making Eq a supertrait of Allocator. We already have wording to the effect that clones of an allocator can free each other's memory, so we can just extend this by saying that clones of an allocator must be equal to each other as per Eq.

This is expected to be a very cheap operation: for ZST allocators such as Global this is a no-op that always returns true. Foe stateful allocators it is a comparison of the pointers to their internal state.

[Amanieu]

I gave this a try and it's tricker than it seems. The core issue is that requiring Eq would make the Allocator trait non-object-safe.

[zakarumych]

I imagine that LinkedList::try_append would have where A: PartialEq<B> bound, where A and B are allocator types of two linked lists.

And allocator safety guidelines will mention that if two allocators are comparable (there's A: PartialEq<B>) and compare as equal then either can deallocate memory allocated by another. In addition it should prompt that clonable allocators should be comparable and clones be equal.

Additionally there can be trait for stateless allocator types to signal that all instances of that type are equal. For such allocators there can be non-fallible LinkedList::append where A: AlwaysEq<B>

Naturally Global would be AlwaysEq<Global>. And AlwaysEq will be implemented for references like PartialEq