allow standard library functions to check expensive pre-/postconditions

[gnzlbg]

See also: #44370

There should be a way for standard library functions to check expensive pre-/postconditions, by which I mean preconditions that change the complexity of the standard algorithms (e.g. by making a O(1) algorithm O(log N)).

Example: binary_search requires the input slice to be sorted, otherwise the result is unspecified. Checking if the input slice is sorted makes binary_search O(N) instead of O(log N) (*) defeating the purpose of binary search. Still, such a check is useful to detect logic errors in user programs: it is a violated precondition after all.

So we are at an impasse. What could we do?

We could:

• add a expensive_assert! macro to std
• allow users to configure std with different features (and make this easy to use via cargo)
• add expensive_assert!(input_slice.is_sorted()) to binary_search

An alternative would be to perform this test using debug_assert!. However, making all debug builds exponentially slower is unacceptable.

(*) Since the standard library does not guarantee the complexity of anything, we can actually make binary_search O(N) in debug builds and that would be a backwards compatible change...

[arielb1]

We also shouldn't change binary_search to be O(n) on debug-assertions builds - debug-assertions should be for the last 2x of performance, not for potential order-of-magnitude slowdowns.

[steveklabnik]

This feels like RFC territory to me.

[gnzlbg]

@steveklabnik is it ok to discuss this as a pre-RFC here then or should I post this in the internals forum? I really don't know what the design space is, so even if this turns out to be a mini RFC, I cannot write one yet.

[steveklabnik]

I really don't know what the design space is

Yeah, this makes it not a good issue; issues should have a clear way to resolve them.

A post on the internals forum would be perfect. Thanks!

[gnzlbg]

FWIW: https://internals.rust-lang.org/t/pre-rfc-expensive-pre-postcondition-checks-in-std/5871