How is BTreeMap written to be robust against Ord impl?

From the Rustonomicon, unsafe Rust has to be very careful about trusting Safe Rust, and it takes BTreeMap as an example, which says it should be written robust against Ord implementations which aren't actually total.

I find it is hard to understand this, and I want to see the code example. But when I looked into the BTreeMap's source code, I found it is very very long and complicated. Could anyone show me a code example about how unsafe Rust be written robust against wrong-implemented safe code?

In the docs for the Ord trait, they talk about various requirements that a correct implementation of must meet. For example, if A<B and B<C, then A<C. The problem is that while the trait docs say that ordering relations have these properties, you could implement it in a way that doesn't follow them. For example, you could implement it such that a.cmp(b)==Ordering::Greater for all a and b. By itself, this incorrect implementation doesn't pose a threat to memory safety, and without unsafe code, it never will. However, you could write unsafe code is that only correct if the implementation of Ord is valid. It's not easy to come up with an example of this off the top of my head, but it could go a little bit like this:

  1. You compare A and B, and find that A<B.
  2. You compare B and C, and find that B<C.
  3. You assume that this means A<C, and store some value somewhere based on that assumption.
  4. Later on, you compare A and C, and find that A>C.
  5. You read a value from the place that you would have stored it if A was greater than C, which is uninitialized because you previously assumed A was less than C based on the properties Ord implementations should have.

It essentially boils down to one piece of advice: assume that people using your interface might be writing broken code, and make sure that your code will never do anything invalid as a result of mistakes they made.