Should the `Borrow` trait lead to a minimal type for comparisons?

libs
1

I've been thinking about the Borrow trait, for reasons that I'll come to a little further on. But first, some observations:

  1. the signature of the trait's borrow method necessitates that the Borrowed value is some subset of the memory borrowed by &self; and
  2. the trait requires that "Eq, Ord and Hash must be equivalent for borrowed and owned values".

Can't we therefore conclude that whatever state is used by the Self type to implement Eq, Ord and Hash must also be within the subset of its memory that is used by the Borrowed type? Indeed, that state must be within every such Borrowed type supported by the Self type.

Shouldn't it therefore be possible to specify a minimal type T which includes (only) that state, such that all Borrowed types transitively derived from any given Self can also implement Borrow<T>?

Moreover, Eq, Ord and Hash only need be explicitly implemented for that minimal T, with implicit implementations inferable for any type that implements Borrow<T>. Thus the trait's logic requirement is enforced.

I'm not necessarily proposing that any of this should be done, only observing that it could be (at least in theory, absent stability concerns etc).

The particular use-case that got me to thinking about this was that posed in the following StackOverflow question:

Here the solution is probably to create a map type that holds the runtime-defined comparator, but if that comparator is defined in terms of the key type K then the convenience of accessing the map via borrowed versions of the key (e.g. of type Q where K: Borrow<Q>) becomes very much more complicated: somehow the comparator needs to be converted to work in terms of such borrowed type(s). It seems to me that, instead, the comparator only need be defined in terms of the minimal type T, which all lookups (whether using key type K or some borrowed type Q thereof) will be able to borrow.

It may well be that such complexity is not required in this case, or indeed that the solution can be implemented with explicit knowledge of the actual types in use, but nevertheless I can't help wondering if perhaps the current design of Borrow lacks some important/useful expressivity here?

2

It's an interesting theoretical observation, but doesn't quite match what's actually true or possible, and I don't think there's anything actionable at the moment.

Here's a type from which you can borrow memory that is not a subset of self and which uses distinct types for (Hash, Eq) and (Ord).

There's not necessarily a minimal type either.

Also, those requirements cannot be relied upon for soundness. And you can also implement Borrow without implementing the other traits.

Also, I can store a transitive type as the key in a HashMap, get it back later, and then pass it to some other function with an Ord bound but not a Borrow bound.

Borrow's reflective implementation precludes a non-magical blanket transitive implementation.

Ignoring coherence, Borrow being transitive would likely lead to the types of inference struggles that AsRef has.

1 Like
3

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.