<algorithm>: Double forwarding in std::ranges::clamp causes unwanted moving

[Fulgen301]

Describe the bug

STL/stl/inc/algorithm

Lines 10600 to 10608 in 8674b3d

	auto&& _Temp = _STD invoke(_Proj, _Val);
	if (_STD invoke(_Pred, _STD forward<decltype(_Temp)>(_Temp), _STD invoke(_Proj, _Lo))) {
	return _Lo;
	}
	// The double forward is safe because regular_invocable requires that the invocation of the predicate not
	// modify _Temp in a manner observable to equality-preserving expressions.
	if (_STD invoke(_Pred, _STD invoke(_Proj, _Hi), _STD forward<decltype(_Temp)>(_Temp))) {
	return _Hi;
	}

As the projection function in the following test case returns a non-const copy of the argument that is taken by const reference and the comparator takes its arguments by value, std::forward causes _Temp to be moved instead of copied when calling the comparator, resulting in causing an std::out_of_range exception on the second comparator invocation. From my understanding of the C++ standard, both the projection and the comparator are conforming to its requirements, although I am not too sure about it.

Both libstdc++ and libc++ don't exhibit this behavior.

Command-line test case

C:\Temp> type repro.cpp
#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <vector>

bool less(std::vector<int> a, std::vector<int> b)
{
    return a.at(0) < b.at(0);
}

void print(const std::vector<int>& x)
{
    std::cout << "[";
    for (bool first = true; auto v : x)
    {
        if (!first)
        {
            std::cout << ", ";
        }
        std::cout << v;

        first = false;
    }
    std::cout << "]\n";
}

std::vector<int> my_identity(const std::vector<int> &value)
{
    return value;
}

int main()
{
    std::vector<int> value{5};
    std::vector<int> lo{3};
    std::vector<int> hi{7};
    print(value);

    try
    {
        print(std::ranges::clamp(value, lo, hi, less, my_identity));

        std::cout << "Test succeeded" << std::endl;
    }
    catch (const std::out_of_range &)
    {
        std::cout << "Test failed" << std::endl;
    }
}


C:\Temp>cl /EHsc /W4 /WX /std:c++latest .\repro.cpp
Microsoft (R) C/C++-Optimierungscompiler Version 19.38.32919 für x64
Copyright (C) Microsoft Corporation. Alle Rechte vorbehalten.

"/std:c++latest" wird als Vorschau auf die Sprachfeatures aus dem neuesten C++-Arbeitsentwurf
 zur Verfügung gestellt, und wir sind gespannt auf Fehler und Verbesserungsvorschläge.
Beachten Sie jedoch, dass diese Features ohne Mängelgewähr und ohne Unterstützung bereitgestellt werden und Funktionen während der Weiterentwicklung
 des Arbeitsentwurfs jederzeit geändert oder entfernt werden können.
Ausführliche Informationen finden Sie unter https://go.microsoft.com/fwlink/?linkid=2045807.

repro.cpp
Microsoft (R) Incremental Linker Version 14.38.32919.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:repro.exe
repro.obj

C:\Temp>.\repro.exe
[5]
Test failed

Expected behavior

No std::out_of_range exception should be thrown.

STL version

Microsoft Visual Studio Community 2022
Version 17.8.0 Preview 1.0

[frederick-vs-ja]

Your comparator doesn't meet the semantic requirements of std::regular_invocable - it can modify arguments that are std::vector<int> rvalues by moving. And the arguments you provided happened to be modified. So the call to std::ranges::clamp resulted in undefined behavior.

See also

• std::regular_invocable on cppreference
• [concept.regularinvocable]

[AlexGuteniev]

it can modify arguments that are std::vector<int> rvalues by moving

I don't get it.
It does not modify any elements, and if it did, this would be on a copy.

[frederick-vs-ja]

It does not modify any elements, and if it did, this would be on a copy.

But the copy may be obtained from move construction, so it is considered able to modify the argument when used in std::invoke.

[StephanTLavavej]

I agree that N4950 [concept.regularinvocable]/1 "The invoke function call expression shall be equality-preserving ([concepts.equality]) and shall not modify the function object or the arguments." forbids less(std::vector<int> a, std::vector<int> b).

We're required to cache the projection (we get only 3 invocations, not 4), so the question is what value category we present to the comparator. The Standard depicts the original value category, so I agree that our approach is correct. That said, this Standardese is admittedly squirelly.

[AlexGuteniev]

I hate that. Non-range algorithms allowed functors taking params by value 😞

[StephanTLavavej]

We looked at libc++'s implementation and they are non-conformantly invoking the projection 4 times instead of 3. (N4950 [alg.clamp]/5 is unambiguous.)

The possible changes for us are (just listing them without any order of preference):

1. Invoke the predicate 4 times, defying the Standard but matching libc++ (we don't know what libstdc++ is doing).
2. No change, we conform to the Standard as written.
3. Cache the invocation as auto _Temp and present _Temp as an lvalue both times.
4. Cache the invocation as auto&& _Temp and present _Temp as an lvalue both times.
5. Cache the invocation as auto&& _Temp (like today), but present _Temp as an lvalue during the first comparison, and only forward it on the second comparison (suggested by @strega-nil-ms).

We could also raise this as an LWG issue due to the implementation divergence and potential for surprising users. After talking about this at the weekly maintainer meeting, we are united in our desire for the LWG to tell us what to do.

[AlexGuteniev]

5. Cache the invocation as auto&& _Temp (like today), but present _Temp as an lvalue during the first comparison, and only forward it on the second comparison (suggested by @strega-nil-ms).

I hope this was the intention, but was underspecified due to an oversight

[frederick-vs-ja]

(we don't know what libstdc++ is doing)

Currently libstdc++ chooses option 4 (cache the invocation as auto&& _Temp and present _Temp as an lvalue both times).

https://github.com/gcc-mirror/gcc/blob/8e71ad9e782195d1285b85b2eb8f127572d5be2d/libstdc++-v3/include/bits/ranges_algo.h#L2947-L2953

[frederick-vs-ja]

Invoke the predicate 4 times, defying the Standard but matching libc++

MSVC STL used to behave like this until #1898.

See #1898 (comment). CC @timsong-cpp.

[timsong-cpp]

Any of 3-5 makes the algorithm underconstrained because indirect_strict_weak_order doesn't say anything about invocability with iter_reference_t&, only iter_reference_t.

[Fulgen301]

Invoke the predicate 4 times, defying the Standard but matching libc++

I reported libc++'s standard violation and they're now classifying it as a bug (llvm/llvm-project#64717), so going down that route might end up swapping the behavior with libc++.

[frederick-vs-ja]

Any of 3-5 makes the algorithm underconstrained because indirect_strict_weak_order doesn't say anything about invocability with iter_reference_t&, only iter_reference_t.

Curiously, they didn't seem to render the algorithm underconstrained before P2609R3...

[timsong-cpp]

Any of 3-5 makes the algorithm underconstrained because indirect_strict_weak_order doesn't say anything about invocability with iter_reference_t&, only iter_reference_t.

Curiously, they didn't seem to render the algorithm underconstrained before P2609R3...

It's harder to construct an example but they do exist: https://gcc.godbolt.org/z/3fsdbTx5Y

[frederick-vs-ja]

I think this should be closed as invalid, see also LLVM-68413.

[StephanTLavavej]

We talked about this at the weekly maintainer meeting, and now that libc++ agrees with our behavior, we believe that we have no reason to keep this issue open. Of course, if someone would like to file an LWG issue to further clarify the Standard here then that is entirely welcome (but please don't tell us and libc++ to do something different now 😹).