<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:

STL/stl/inc/xutility

Lines 1589 to 1598 in 5be7d49

	constexpr bool _Debug_lt_pred(_Pr&& _Pred, _Ty1&& _Left, _Ty2&& _Right) noexcept(
	noexcept(_Pred(_Left, _Right)) && noexcept(_Pred(_Right, _Left))) {
	// test if _Pred(_Left, _Right) and _Pred is strict weak ordering, when the arguments are the cv-same-type
	const auto _Result = static_cast<bool>(_Pred(_Left, _Right));
	if (_Result) {
	_STL_VERIFY(!_Pred(_Right, _Left), "invalid comparator");
	}
	return _Result;
	}

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:
  

  STL/tests/libcxx/expected_results.txt

  Lines 586 to 589 in 06827fe

  	# Predicate count assertions - IDL2 is slightly bending the Standard's rules here.
  	std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp FAIL
  	std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp FAIL
  	std/algorithms/alg.sorting/alg.min.max/minmax_init_list_comp.pass.cpp FAIL

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?

STL/tests/std/tests/P1135R6_atomic_flag_test/test.cpp

Line 33 in 5be7d49

assert(std::transform_reduce(par, ptrs.begin(), ptrs.end(), 0, std::plus{}, test_and_set) == dups);

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:

STL/tests/libcxx/expected_results.txt

Lines 586 to 589 in 06827fe

	# Predicate count assertions - IDL2 is slightly bending the Standard's rules here.
	std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp FAIL
	std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp FAIL
	std/algorithms/alg.sorting/alg.min.max/minmax_init_list_comp.pass.cpp FAIL

[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.