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