Are AsRef and Borrow supposed to be deterministic?

[kpreid]

@kornel

the exact wording for "don't do weird stuff with it, because you'll get garbage-in-garbage-out, but not UB, and unsafe code still needs to be careful about implementations that are weird?"

2¢: I think that it would be good if there was a single place this concept was defined, rather than wording it anew for each trait where it comes up.

In a previous thread, there was quite a long discussion about how this it is hard to define and the existing library documentation for HashMap could be taken as meaning “may do absolutely anything, but not UB”, which is not really a useful claim since “anything” could be taken to include modifying application/system state in ways that might not be technically UB but are equally destructive to the desired functioning of a program. Here's what I wrote trying to define this concept; talking about the other end — the code that uses the trait — and Hash rather than Borrow, but I think it is the same general principle.

@kpreid

One way to look at this problem is in terms of causality and encapsulation. The things which make UB uniquely bad are:

• UB may cause an effect that is “action at a distance” from the source of it: it can arbitrarily modify any other part of the program state, so the consequences do not follow the laws of causality that programmers normally assume or that language and library documentation promises, such as (especially with Rust's single-ownership rules) a value not observably changing unless modified by its owner, a borrow, or interior mutability.
• UB can violate invariants across abstraction boundaries: for example, corrupting the contents of private fields of a struct such that it no longer obeys the invariants maintained by the code to which those fields are visible. Narrowly, we can identify this as “encapsulation”; we could also consider it unwanted causality that bypassed the code that wanted to maintain the invariant.

So, I propose that where HashMap currently says “will not result in undefined behavior”, the spirit of the message is “will not violate causality or encapsulation”. We declare it will not violate causality, meaning that it does not affect what a programmer would consider unrelated data; we declare it will not violate encapsulation, meaning that even the things that it interacts with will not enter states that they cannot have entered merely by the HashMap returning values which are valid by its function signatures.

Hmm, that last clause suggests a more formal condition: The HashMap may do anything that is all of:

1. not-UB / memory-safe,
2. implied by its function signatures (return wrong values, panic, loop, etc.), and
3. does not otherwise affect any state (except by returning results or calling callback functions according to point 2) that would not be dropped when the HashMap is.

The above is talking about HashMap, not Hash, but that's just the opposite end of the contract — though harder to nail down, since it's not clear what the abstraction/encapsulation-boundary is for “thing that uses Borrow or Hash”.

So, I think that this is a coherent concept, but it is not simple and so it deserves its own name and reference page, not just an attempt to explain it in each trait or type whose contract involves it.