[Bug c++/107850] New: std::erase_if (map) forces predicate to takes a const value_type

[Bug c++/107850] New: std::erase_if (map) forces predicate to takes a const value_type

[chgros at synopsys dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

            Bug ID: 107850
           Summary: std::erase_if (map) forces predicate to takes a const
                    value_type
           Product: gcc
           Version: 12.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: chgros at synopsys dot com
  Target Milestone: ---

g++11 will compile this program, but g++ 12.1.0 will not, because it complains
that the predicate cannot take a const.
The standard definition of erase_if (reproduced here for comparison purposes)
indicates that g++11 is right in this case; this is a regression.

#include <map>
#include <string>

using namespace std;

template<typename Pred>
int erase_if_by_std(map<string, string> &c, Pred pred)
{
    auto original_size = c.size();
    for (auto i = c.begin(), last = c.end(); i != last; ) {
        if (pred(*i)) {
            i = c.erase(i);
        } else {
            ++i;
        }
    }
    return original_size - c.size();
}

int main(int argc, char const * const *argv)
{
    auto pred = [&](pair<string const, string> &p) {
        if(p.first.size() == 2) {
            return true;
        } else {
            p.second.resize(3);
            return false;
        }
    };
    map<string, string> m;
    erase_if_by_std(m, pred);
    std::erase_if(m, pred);
}

[Bug libstdc++/107850] [12/13 Regression] std::erase_if (map) forces predicate to takes a const value_type

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|std::erase_if (map) forces  |[12/13 Regression]
                   |predicate to takes a const  |std::erase_if (map) forces
                   |value_type                  |predicate to takes a const
                   |                            |value_type
   Target Milestone|---                         |12.3

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Looks like it was caused by r12-5431-g5f40d34b6dd3 .

[Bug libstdc++/107850] [12/13 Regression] std::erase_if (map) forces predicate to takes a const value_type

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I have very little sympathy for this use case, predicates that can't be called
with const arguments are always wrong. I'm inclined to say the standard should
be fixed to match our new behaviour.

[Bug libstdc++/107850] [12/13 Regression] std::erase_if (map) forces predicate to takes a const value_type

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2022-11-24

[Bug libstdc++/107850] [12/13 Regression] std::erase_if (map) forces predicate to takes a const value_type

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

--- Comment #3 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:f54ceb2062c7fef294f85ae093914fa6c7ca35b8

commit r13-4306-gf54ceb2062c7fef294f85ae093914fa6c7ca35b8
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Nov 24 21:09:03 2022 +0000

    libstdc++: Call predicate with non-const values in std::erase_if [PR107850]

    As specified in the standard, the predicate for std::erase_if has to be
    invocable as non-const with a non-const lvalues argument. Restore
    support for predicates that only accept non-const arguments.

    It's not strictly nevessary to change it for the set and unordered_set
    overloads, because they only give const access to the elements anyway.
    I've done it for them too just to keep them all consistent.

    libstdc++-v3/ChangeLog:

            PR libstdc++/107850
            * include/bits/erase_if.h (__erase_nodes_if): Use non-const
            reference to the container.
            * include/experimental/map (erase_if): Likewise.
            * include/experimental/set (erase_if): Likewise.
            * include/experimental/unordered_map (erase_if): Likewise.
            * include/experimental/unordered_set (erase_if): Likewise.
            * include/std/map (erase_if): Likewise.
            * include/std/set (erase_if): Likewise.
            * include/std/unordered_map (erase_if): Likewise.
            * include/std/unordered_set (erase_if): Likewise.
            * testsuite/23_containers/map/erasure.cc: Check with
            const-incorrect predicate.
            * testsuite/23_containers/set/erasure.cc: Likewise.
            * testsuite/23_containers/unordered_map/erasure.cc: Likewise.
            * testsuite/23_containers/unordered_set/erasure.cc: Likewise.
            * testsuite/experimental/map/erasure.cc: Likewise.
            * testsuite/experimental/set/erasure.cc: Likewise.
            * testsuite/experimental/unordered_map/erasure.cc: Likewise.
            * testsuite/experimental/unordered_set/erasure.cc: Likewise.

[Bug libstdc++/107850] [12 Regression] std::erase_if (map) forces predicate to takes a const value_type

[chgros at synopsys dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

--- Comment #4 from Charles-Henri Gros <chgros at synopsys dot com> ---
Looking into it further, there may be an implicit requirement that the
predicate does not modify its argument.
https://eel.is/c++draft/algorithms.requirements#6
"When not otherwise constrained, the Predicate parameter is used whenever an
algorithm expects a function object ([function.objects]) that, when applied to
the result of dereferencing the corresponding iterator, returns a value
testable as true.
In other words, if an algorithm takes Predicate pred as its argument and first
as its iterator argument with value type T, it should work correctly in the
construct pred(*first) contextually converted to bool ([conv]).
The function object pred shall not apply any non-constant function through the
dereferenced iterator.
Given a glvalue u of type (possibly const) T that designates the same object as
*first, pred(u) shall be a valid expression that is equal to pred(*first)."
I'm unfortunately not well-versed enough in C++ legalese to tell what "possibly
const" means in that context, nor "apply any non-constant function".
And while I understand that a "predicate" is generally meant to not do
modification, there are fairly frequent use cases for "apply this potentially
modifying operation, and depending on its result remove the element from the
container". And in practice, this works (e.g. std::remove_if, your own earlier
version of erase_if, other compilers' version...).
Maybe I should go to LEWG and lobby to remove that limitation. In the
meanwhile, I'll probably just keep my own, perhaps slightly less optimal
removal algorithms.

[Bug libstdc++/107850] [12 Regression] std::erase_if (map) forces predicate to takes a const value_type

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Charles-Henri Gros from comment #4)
> Looking into it further, there may be an implicit requirement that the
> predicate does not modify its argument.
> https://eel.is/c++draft/algorithms.requirements#6

See paragraph 4. That only applies to the Algorithms clause, not the Containers
clause. So it doesn't apply to std::erase_if for maps. It *does* apply to
std::erase_if for sequence containers, because those are defined in terms of
std::remove_if, which is defined in the Algorithms clause. It doesn't apply to
std::erase_if for sets, but *first is always const for those anyway so it's
irrelevant.

> I'm unfortunately not well-versed enough in C++ legalese to tell what
> "possibly const" means in that context,

A "glvalue u of type (possibly const) T" means u is a T& or const T&. Your
predicate would fail that requirement (if it applied here) because it cannot be
called with const T& at all, so pred(u) isn't a valid expression.

> nor "apply any non-constant function".

It means you can't modify the argument.

> And while I understand that a "predicate" is generally meant to not do
> modification, there are fairly frequent use cases for "apply this
> potentially modifying operation, and depending on its result remove the
> element from the container".

You can write your own "modify and remove if" algo for that.

> And in practice, this works (e.g.
> std::remove_if, your own earlier version of erase_if, other compilers'
> version...).

It's undefined behaviour to do that with std::remove_if.

> Maybe I should go to LEWG and lobby to remove that limitation. In the
> meanwhile, I'll probably just keep my own, perhaps slightly less optimal
> removal algorithms.

There is no such restriction on std::erase_if for maps today, but I'll be
lobbying the committee to *add* it!

[Bug libstdc++/107850] [12 Regression] std::erase_if (map) forces predicate to takes a const value_type

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
IMHO https://cplusplus.github.io/LWG/issue3031 should have applied to these
functions too.

[Bug libstdc++/107850] [12 Regression] std::erase_if (map) forces predicate to takes a const value_type

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
See also https://cplusplus.github.io/LWG/issue2542 which was another change in
the same vein. Generally, we're getting stricter about rejecting predicates
like yours, because reasoning about the program because harder (and sometimes
implementing those algorithms because unreasonably complex) if predicates have
non-obvious side effects like modifying elements.

[Bug libstdc++/107850] [12 Regression] std::erase_if (map) forces predicate to takes a const value_type

[chgros at synopsys dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

--- Comment #8 from Charles-Henri Gros <chgros at synopsys dot com> ---
Thanks for all the comments. I agree that for consistency this should be
rejected, though my preference would still be to make remove_if/erase_if more
useful in practical cases (this happens dozens of times in codebase, just for
map. For vector, it's likely a lot more). The predicate should be called
exactly once per element so lack of side effect on the element is not really
relevant. Anyway, that's a discussion for another forum.

[Bug libstdc++/107850] [12 Regression] std::erase_if (map) forces predicate to takes a const value_type

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The problem with side effects is not that they happen more than once, but that
they happen at all. The algorithm is called "erase_if" so it's surprising if it
actually mutates the remaining elements, rather than just removing some. What
you want is a different algorithm, and so should have a different name.

[Bug libstdc++/107850] [12 Regression] std::erase_if (map) forces predicate to takes a const value_type

[chgros at synopsys dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

--- Comment #10 from Charles-Henri Gros <chgros at synopsys dot com> ---
I'd be happy with any algorithm that meets my needs, though the presence of a
different algorithm that does the same thing that the existing algorithm
currently does, or at least subsumes all the existing use cases of the current
algorithm (likely with no performance loss), seems redundant to me. Anyway I'm
planning to take this to LEWG, I'm pretty sure we agree something needs to be
done either way.

[Bug libstdc++/107850] [12 Regression] std::erase_if (map) forces predicate to takes a const value_type

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

--- Comment #11 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:ee5ab84e5f15b6d7c488bc371e4fb0304543844f

commit r12-9489-gee5ab84e5f15b6d7c488bc371e4fb0304543844f
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Nov 24 21:09:03 2022 +0000

    libstdc++: Call predicate with non-const values in std::erase_if [PR107850]

    As specified in the standard, the predicate for std::erase_if has to be
    invocable as non-const with a non-const lvalues argument. Restore
    support for predicates that only accept non-const arguments.

    It's not strictly nevessary to change it for the set and unordered_set
    overloads, because they only give const access to the elements anyway.
    I've done it for them too just to keep them all consistent.

    libstdc++-v3/ChangeLog:

            PR libstdc++/107850
            * include/bits/erase_if.h (__erase_nodes_if): Use non-const
            reference to the container.
            * include/experimental/map (erase_if): Likewise.
            * include/experimental/set (erase_if): Likewise.
            * include/experimental/unordered_map (erase_if): Likewise.
            * include/experimental/unordered_set (erase_if): Likewise.
            * include/std/map (erase_if): Likewise.
            * include/std/set (erase_if): Likewise.
            * include/std/unordered_map (erase_if): Likewise.
            * include/std/unordered_set (erase_if): Likewise.
            * testsuite/23_containers/map/erasure.cc: Check with
            const-incorrect predicate.
            * testsuite/23_containers/set/erasure.cc: Likewise.
            * testsuite/23_containers/unordered_map/erasure.cc: Likewise.
            * testsuite/23_containers/unordered_set/erasure.cc: Likewise.
            * testsuite/experimental/map/erasure.cc: Likewise.
            * testsuite/experimental/set/erasure.cc: Likewise.
            * testsuite/experimental/unordered_map/erasure.cc: Likewise.
            * testsuite/experimental/unordered_set/erasure.cc: Likewise.

    (cherry picked from commit f54ceb2062c7fef294f85ae093914fa6c7ca35b8)

[Bug libstdc++/107850] [12 Regression] std::erase_if (map) forces predicate to takes a const value_type

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107850

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #12 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 12.3