match (order(lhs), order(rhs)) {
(lhs_, rhs_) if lhs_ < rhs_ => std::cmp::Ordering::Less,
(lhs_, rhs_) if lhs_ > rhs_ => std::cmp::Ordering::Greater,
(lhs_, rhs_) if lhs_ == rhs_ => lhs.cmp(rhs),
}

I get the following error:

2 src/main.rs|26 col 15 error 4| non-exhaustive patterns: `(_, _)` not covered
3 || |
4 || 26 | match (order(lhs), order(rhs)) {
5 || | ^^^^^^^^^^^^^^^^^^^^^^^^ pattern `(_, _)` not covered
6 || |
7 || = help: ensure that all possible cases are being handled, possibly by adding wildcards or more match arms
8 || = note: the matched value is of type `(i32, i32)`

Is this a compiler bug? Or am I missing something?

Doesn't seem like a "bug" to me; exhaustiveness checking is hard. The compiler can't figure out that there are no other possibilities remaining. Instead of being explicit about the equality, you could just write a catch-all case without the if guard.

I realized that an adversary type could implement Ord in a way where a value could be simultaneously neither less than, greater than or equal. Such type would therefore need a catch all value because my code would not describe all possibilities.

So itâ€™s not a compiler bug, just a help suggestion that could be explained better.

Sure, although in this specific case, the type is known to be the primitive i32, which, for all intents and purposes, could be trusted with correctly implementing a strict total order.

You can rewrite the match so it is exhaustive by invoking Ord::cmp once, instead of 3 times using <, >, and == separately:

use std::cmp::Ordering;
match order(lhs).cmp(&order(rhs)) {
Ordering::Less => Ordering::Less,
Ordering::Greater => Ordering::Greater,
Ordering::Equal => lhs.cmp(rhs),
}

Also, this code in particular is just the standard â€ślexicographical comparisonâ€ť operation (using another ordering if the first one is equal), so you can make it even simpler using the built-in Ordering::then_with: