<algorithm>: debug checks for predicates are observable

[AlexGuteniev]

Describe the bug Debug version std::min_element assumes that the range is not modified while working on it.

It triggers the following check: https://github.com/microsoft/STL/blob/5be7d49c243979231dff35919d3a3d813d75d714/stl/inc/xutility#L1589-L1598

This assertion is triggered when std::min_element is used on array of std::atomic values that are incremented independently by concurrent threads.

DevCom-222276 reporter asks:

Are there any limitations in the standard about std::min_elements() that I should know?

Additional context

• Skipped libcxx tests: https://github.com/microsoft/STL/blob/06827feb4cdc4d2328dfbfab9fd5302de6058dd9/tests/libcxx/expected_results.txt#L586-L589

Also tracked by DevCom-222276 and Microsoft-internal VSO-592348 / AB#592348.

[AlexGuteniev]

[alg.sorting]/4 sorts it out, I think:

The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering. If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations: (4.1) comp(a, b) && comp(b, c) implies comp(a, c) (4.2) equiv(a, b) && equiv(b, c) implies equiv(a, c)

[alg.sorting] applies to min_element, along with other sorting algorithms. With values modified along the way (no matter if by means of atomics or otherwise), even irreflexive relation part is violated (comp(x, x) may be true), the same story with transitive relations.

[BillyONeal]

The standard is clear in its requirements here but I think we kept this open internally because we might want to consider removing the extra _Pred debugging checks for algorithms that normally would need to call _Pred exactly N or exactly N-1 times. (As opposed to an algorithm like sort where an incorrect _Pred can corrupt memory)

[StephanTLavavej]

Several different thoughts:

• I don't think that, in principle, STL algorithms should be required to tolerate elements whose values change during the algorithm call, or predicates whose answer changes when repeatedly invoked on the same elements, even if we're technically not allowed to call predicates repeatedly
• The "misbehaving predicate" debug checks, while bending and slightly breaking the rules of the Standard in various places, are capable of diagnosing something that users get wrong all the time (I am surprised how often - although I don't have hard data as to how many bogus predicates are written and detected)
• But these days, it should be possible (in theory) for static analysis to notice that something is being passed as a comparator to STL algorithms/containers and look for common patterns that result in comp(x, x) being true. This is perhaps not as good as checking at runtime, but wouldn't be value-dependent or Standard-questionable.

Maybe removing the debug checks (and adding comments) for the exact-invocation algorithms is a reasonable compromise.

[AlexGuteniev]

• I don't think that, in principle, STL algorithms should be required to tolerate elements whose values change during the algorithm call, or predicates whose answer changes when repeatedly invoked on the same elements, even if we're technically not allowed to call predicates repeatedly

How about this? https://github.com/microsoft/STL/blob/5be7d49c243979231dff35919d3a3d813d75d714/tests/std/tests/P1135R6_atomic_flag_test/test.cpp#L33

I think Standard intentionally does not prohibit it.

[AlexGuteniev]

What possibly Standard could is to support reporter's scenario. Still it looks like complicated Standard change with little motivation.

[BillyONeal]

I think Standard intentionally does not prohibit it.

The standard does actually prohibit that example. http://eel.is/c++draft/transform.reduce#8.2

What possibly Standard could is to support reporter's scenario. Still it looks like complicated Standard change with little motivation.

It could specify the exact calling order, for example http://eel.is/c++draft/alg.shift#2

[AlexGuteniev]

The standard does actually prohibit that example.

I'm not sure what "modify" means here. The atomic_ref themselves are not modified, only predicate results, by modifying targets of atomic_ref

[BillyONeal]

It effectively means 'insofar as the algorithm can tell'.

[AlexGuteniev]

Skipped libcxx tests: https://github.com/microsoft/STL/blob/06827feb4cdc4d2328dfbfab9fd5302de6058dd9/tests/libcxx/expected_results.txt#L586-L589

[AlexGuteniev]

I notice that we don't validate predicates for min / max.

[BillyONeal]

I notice that we don't validate predicates for min / max.

I removed debugging checks for them because:

• The "impossible" behavior caused by bad predicates doesn't happen for min or max as it would, for example, sort or map.
• It's a reasonable expectation for min or max to invoke the predicate only once.

I think there was also a use case where we wanted to use min/max in a "core" header which means they can't have debug checks, but it's been long enough I don't remember details there.

I don't think any of these apply to minmax_element and friends.

[AlexGuteniev]

What do you think about having them on clamp? Would you remove them from clamp either?

[BillyONeal]

What do you think about having them on clamp? Would you remove them from clamp either?

clamp is kind of borderline. It is in the min/max family but it is morally ordering the 3 inputs... I probably would personally error on the side of not touching it unless there's a concrete user program illegitimately broken by the additional check. However, I wouldn't argue too strongly against removing debug checks there either (whereas I would for min_element et al.).

Seems like a decision for current maintainers though.

[StephanTLavavej]

We talked about this at the weekly maintainer meeting and have no strong feelings about this - specifically, we're not inclined to remove the debug checks from clamp if they aren't actively causing trouble for users.

[AlexGuteniev]

• But these days, it should be possible (in theory) for static analysis to notice that something is being passed as a comparator to STL algorithms/containers and look for common patterns that result in comp(x, x) being true. This is perhaps not as good as checking at runtime, but wouldn't be value-dependent or Standard-questionable.

My recent experience shows that a lot of people tend to neglect running any static analysis, but run debug builds pretty regularly.

My opinion currently is that:

• The DevCom issue should be resolved as won't fix.
• For those tests (but not all other libc++ tests), test matrix should be change to exclude this debugging option.

[StephanTLavavej]

While I agree that the DevCom issue should be resolved as wontfix, we currently don't have a way to use a different test matrix for a subset of libcxx tests (that suite is set up to use a single matrix for everything). Disabling IDL=2 for the entire suite would be extremely impactful so we wouldn't want to do that - need to consider other alternatives.