HomePhabricator

[ADT] Shuffle containers before sorting to uncover non-deterministic behavior

Description

[ADT] Shuffle containers before sorting to uncover non-deterministic behavior

Summary:
std::sort and array_pod_sort both use non-stable sorting algorithms.
This means that the relative order of elements with the same key is
undefined. This patch is an attempt to uncover such scenarios by
randomly shuffling all containers before sorting, if EXPENSIVE_CHECKS
is enabled.

Here's the bugzilla for this: https://bugs.llvm.org/show_bug.cgi?id=35135

Reviewers: dblaikie, dexonsmith, chandlerc, efriedma, RKSimon

Reviewed By: RKSimon

Subscribers: fhahn, davide, RKSimon, vsk, mgorny, llvm-commits

Differential Revision: https://reviews.llvm.org/D39245