This is the updated qsort comparator verifier.
Since we have vec::qsort(cmp), the patch uses the macro argument counting
trick to redirect only the four-argument invocations of qsort to qsort_chk.
I realize that won't win much sympathies, but a patch doing mass-renaming
of qsort in the whole GCC codebase would win even fewer, I suspect.
The macro ENABLE_FULL_QSORT_CHECKING could be used to enable full O(n^2)
checking, but there's no accompanying configure.ac change. I'm not sure
that would be useful in practice, so I'd rather turn it into #if 0.
The suppression in genmodes was needed because it's not linked with vec.o.
* genmodes.c (calc_wider_mode): Suppress qsort macro.
* system.h [CHECKING_P] (qsort): Redirect to qsort_chk.
(qsort_nochk): New macro.
(qsort_chk): Declare.
(qsort_disable_checking): Declare.
* vec.c (qsort_chk_error): New static function.
(qsort_disable_checking): Define.
(qsort_chk): New function.
---
gcc/genmodes.c | 2 +-
gcc/system.h | 11 +++++++
gcc/vec.c | 95 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 107 insertions(+), 1 deletion(-)
diff --git a/gcc/genmodes.c b/gcc/genmodes.c
index f7eaeef..01a0e65 100644
--- a/gcc/genmodes.c
+++ b/gcc/genmodes.c
@@ -880,7 +880,7 @@ calc_wider_mode (void)
for (i = 0, m = modes[c]; m; i++, m = m->next)
sortbuf[i] = m;
- qsort (sortbuf, i, sizeof (struct mode_data *), cmp_modes);
+ (qsort) (sortbuf, i, sizeof (struct mode_data *), cmp_modes);
sortbuf[i] = 0;
for (j = 0; j < i; j++)
diff --git a/gcc/system.h b/gcc/system.h
index b091794..0f44942 100644
--- a/gcc/system.h
+++ b/gcc/system.h
@@ -1170,4 +1170,15 @@ helper_const_non_const_cast (const char *p)
/* Get definitions of HOST_WIDE_INT. */
#include "hwint.h"
+/* qsort comparator consistency checking machinery. */
+#if CHECKING_P
+/* Except in release-checking compilers, redirect 4-argument qsort calls. */
+#undef qsort
+#define _5th(_1, _2, _3, _4, _5, ...) _5
+#define qsort(...) _5th (__VA_ARGS__, qsort_chk, 3, 2, qsort, 0) (__VA_ARGS__)
+#endif
+#define qsort_nochk (qsort)
+void qsort_chk (void *, size_t, size_t, int (*)(const void *, const void *));
+extern unsigned qsort_disable_checking;
+
#endif /* ! GCC_SYSTEM_H */
diff --git a/gcc/vec.c b/gcc/vec.c
index d612703..5d9f1e9 100644
--- a/gcc/vec.c
+++ b/gcc/vec.c
@@ -31,6 +31,12 @@ along with GCC; see the file COPYING3. If not see
#include "coretypes.h"
#include "hash-table.h"
#include "selftest.h"
+#ifdef GENERATOR_FILE
+#include "errors.h"
+#else
+#include "input.h"
+#include "diagnostic-core.h"
+#endif
/* vNULL is an empty type with a template cast operation that returns
a zero-initialized vec<T, A, L> instance. Use this when you want
@@ -42,6 +48,95 @@ along with GCC; see the file COPYING3. If not see
they cannot have ctors/dtors. */
vnull vNULL;
+/* Report qsort comparator CMP consistency check failure with P1, P2, P3 as
+ witness elements. */
+ATTRIBUTE_NORETURN ATTRIBUTE_COLD
+static void
+qsort_chk_error (const void *p1, const void *p2, const void *p3,
+ int (*cmp) (const void *, const void *))
+{
+ if (!p3)
+ {
+ int r1 = cmp (p1, p2), r2 = cmp (p2, p1);
+ error ("qsort comparator not anti-commutative: %d, %d", r1, r2);
+ }
+ else if (p1 == p2)
+ {
+ int r = cmp (p1, p3);
+ error ("qsort comparator non-negative on sorted output: %d", r);
+ }
+ else
+ {
+ int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3);
+ error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3);
+ }
+ internal_error ("qsort checking failed");
+}
+
+unsigned qsort_disable_checking;
+
+/* Wrapper around qsort with checking that CMP is consistent on given input.
+
+ Strictly speaking, passing invalid (non-transitive, non-anti-commutative)
+ comparators to libc qsort can result in undefined behavior. Therefore we
+ should ideally perform consistency checks prior to invoking qsort, but in
+ order to do that optimally we'd need to sort the array ourselves beforehand
+ with a sorting routine known to be "safe". Instead, we expect that most
+ implementations in practice will still produce some permutation of input
+ array even for invalid comparators, which enables us to perform checks on
+ the output array. */
+void
+qsort_chk (void *base, size_t n, size_t size,
+ int (*cmp)(const void *, const void *))
+{
+ if (!CHECKING_P || qsort_disable_checking)
+ return (qsort) (base, n, size, cmp);
+ (qsort) (base, n, size, cmp);
+#ifdef ENABLE_FULL_QSORT_CHECKING
+#define LIM(n) (n)
+#else
+ /* Limit overall time complexity to O(n log n). */
+#define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n))
+#endif
+#define ELT(i) ((const char *) base + (i) * size)
+#define CMP(i, j) cmp (ELT (i), ELT (j))
+#define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp)
+#define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp)
+ size_t i1, i2, i, j;
+ /* This outer loop iterates over maximum spans [i1, i2) such that
+ elements within each span compare equal to each other. */
+ for (i1 = 0; i1 < n; i1 = i2)
+ {
+ /* Position i2 one past last element that compares equal to i1'th. */
+ for (i2 = i1 + 1; i2 < n; i2++)
+ if (CMP (i1, i2))
+ break;
+ else if (CMP (i2, i1))
+ return ERR2 (i1, i2);
+ size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2);
+ /* Verify that other pairs within current span compare equal. */
+ for (i = i1 + 1; i + 1 < i2; i++)
+ for (j = i + 1; j < i1 + lim1; j++)
+ if (CMP (i, j))
+ return ERR3 (i, i1, j);
+ else if (CMP (j, i))
+ return ERR2 (i, j);
+ /* Verify that elements within this span compare less than
+ elements beyond the span. */
+ for (i = i1; i < i2; i++)
+ for (j = i2; j < i2 + lim2; j++)
+ if (CMP (i, j) >= 0)
+ return ERR3 (i, i1, j);
+ else if (CMP (j, i) <= 0)
+ return ERR2 (i, j);
+ }
+#undef ERR3
+#undef ERR2
+#undef CMP
+#undef ELT
+#undef LIM
+}
+
/* Vector memory usage. */
struct vec_usage: public mem_usage
{
--
1.8.3.1
