[Bug libstdc++/99713] New: Add _GLIBCXX_CHECK_PREDICATES that violates runtime guarantees and ensures predicates are valid

[Bug libstdc++/99713] New: Add _GLIBCXX_CHECK_PREDICATES that violates runtime guarantees and ensures predicates are valid

[fiesh at zefix dot tv]

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

            Bug ID: 99713
           Summary: Add _GLIBCXX_CHECK_PREDICATES that violates runtime
                    guarantees and ensures predicates are valid
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: fiesh at zefix dot tv
  Target Milestone: ---

This is an extension of https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60519

A very nasty kind of bugs stems from invalid predicates to standard library
functions like sort or unique.  They will introduce UB but might not even
trigger since the predicate is not applied to all possible tuples, leading to
bugs that will only manifest in certain situations.

Alas there's no way to establish the correctness of a predicate at compile
time, it's trivial to code the halting problem in it.  Furthermore the
predicate only needs to satisfy its requirements for the ranges that it is
applied to.

Therefore I'd like to suggest a flag that enables checking the predicates
satisfy what's expected of them for the entire range supplied in all function
that make such expectations -- preferably checking what the standard mandates
even if it's more than what the function requires in its implementation.  (For
example I'm pretty sure that std::unique doesn't actually care if its predicate
is transitive, but this assumption might turn out to not be safe for the future
when some sort of parallelization kicks in.  I wouldn't be surprised if a lot
of people used std::unique to eliminate close-enough duplicates from ranges of
doubles, which is UB.)

As a reference for what I'm talking about, here's what we use internally to
catch some bugs.  std::sort could then just call `assert(isCompare(begin, end,
pred))`.

namespace wstd {
        //! Check if a predicate is reflexive for a given range
        /*!
         * The worst case time complexity of this check is N many applications
of pred, where N is the distance from begin to end.
         */
        template <typename It, typename Pred>
        constexpr bool isReflexive(It const begin, It const end, Pred const &
pred)
        {
                for (auto iter = begin; iter != end; ++iter) {
                        if (!pred(*iter, *iter)) {
                                return false;
                        }
                }
                return true;
        }

        //! Check if a predicate is irreflexive for a given range
        /*!
         * The worst case time complexity of this check is N many applications
of pred, where N is the distance from begin to end.
         */
        template <typename It, typename Pred>
        constexpr bool isIrreflexive(It const begin, It const end, Pred const &
pred)
        {
                for (auto iter = begin; iter != end; ++iter) {
                        if (pred(*iter, *iter)) {
                                return false;
                        }
                }
                return true;
        }

        //! Check if a predicate is symmetric for a given range
        /*!
         * The time complexity of this check if O(N^2) many applications of
pred, where N is distance from begin to end.
         */
        template <typename It, typename Pred>
        constexpr bool isSymmetric(It const begin, It const end, Pred const &
pred)
        {
                for (auto iter0 = begin; iter0 != end; ++iter0) {
                        for (auto iter1 = begin; iter1 != end; ++iter1) {
                                if (pred(*iter0, *iter1) && !pred(*iter1,
*iter0)) {
                                        return false;
                                }
                        }
                }
                return true;
        }

        //! Check if a predicate is asymmetric for a given range
        /*!
         * The time complexity of this check if O(N^2) many applications of
pred, where N is distance from begin to end.
         */
        template <typename It, typename Pred>
        constexpr bool isAsymmetric(It const begin, It const end, Pred const &
pred)
        {
                for (auto iter0 = begin; iter0 != end; ++iter0) {
                        for (auto iter1 = begin; iter1 != end; ++iter1) {
                                if (pred(*iter0, *iter1) && pred(*iter1,
*iter0)) {
                                        return false;
                                }
                        }
                }
                return true;
        }

        //! Check if a given predicate is transitive on a given range
        /*!
         * Note that this has time complexity of O(N^3) applications of pred,
where N is the distance from begin to end.
         */
        template <typename It, typename Pred>
        constexpr bool isTransitive(It const begin, It const end, Pred const &
pred)
        {
                for (auto iter0 = begin; iter0 != end; ++iter0) {
                        for (auto iter1 = begin; iter1 != end; ++iter1) {
                                for (auto iter2 = begin; iter2 != end; ++iter2)
{
                                        if (pred(*iter0, *iter1) &&
pred(*iter1, *iter2) && !pred(*iter0, *iter2)) {
                                                return false;
                                        }
                                }
                        }
                }
                return true;
        }

        //! Check if a given predicate is an equivalence relation for a given
range
        template <typename It, typename Pred>
        constexpr bool isEquivalenceRelation(It const begin, It const end, Pred
const & pred)
        {
                return isReflexive(begin, end, pred) && isSymmetric(begin, end,
pred) && isTransitive(begin, end, pred);
        }

        //! Check if a given predicate is a strict weak ordering for a given
range
        template <typename It, typename Pred>
        constexpr bool isStrictWeakOrdering(It const begin, It const end, Pred
const & pred)
        {
                return isIrreflexive(begin, end, pred) && isAsymmetric(begin,
end, pred) && isTransitive(begin, end, pred);
        }

        //! Check if a given predicate satisfies the Compare requirement
        template <typename It, typename Pred>
        constexpr bool isCompare(It const begin, It const end, Pred const &
pred)
        {
                auto const equiv = [&pred](auto const & lhs, auto const & rhs)
{ return !pred(lhs, rhs) && !pred(rhs, lhs); };
                // Note that we do not need to fully check that equiv is an
equivalence relation:
                // * Since pred is irreflexive, equiv is reflexive.
                // * equiv is symmetric simply because of the symmetry of `&&`.
                return isStrictWeakOrdering(begin, end, pred) &&
isTransitive(begin, end, equiv);
        }
} // namespace wstd