<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/61816>61816</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [libc++] Revert the bitset sort optimization
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          ldionne
      </td>
    </tr>
</table>

<pre>
    ```
 [release/16.x][libc++] Revert the bitset sort optimization

    Part of the bitset sort optimization can cause code using an invalid
    comparator to go out-of-bounds, which is potentially dangerous. This
    was an unintended consequence of the original patch, or at least the
    fact that we didn't have anything in place to catch that or announce
    that to vendors was unintended.

    More specifically, std::sort assumes that the comparison predicate is a
    strict weak order (which is a pre-condition to the algorithm). However,
    in practice, some predicates may not satisfy the pre-condition in subtle
    ways. While that is technically a user problem, we need a good answer
    for how to handle this given that we know this exists in the wild and
    unconditionally reading out-of-bounds data is not a great answer. We
    can't weaken the preconditions of the algorithm, however letting this
    situation happen without even a way of diagnosing the issue is pretty bad.

    Hence, this patch reverts the optimization from release/16.x so that we
    can buy a bit of time to figure out how to properly handle and communicate
 this change in the LLVM 17 release.

    The bitset sort optimization was 4eddbf9f10a (aka https://llvm.org/D122780).
    This patch is not a pure revert of the patch, I also fixed up the includes
    a bit.

 Differential Revision: https://reviews.llvm.org/D146421
```

/branch ldionne/llvm-project/ldionne-z-revert-sort-16.x
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyUVV-L2zgQ_zTOy5DgyImTPORht8vSgxaOo1yfx9LEnqss-SQ5afrpj5Hzt4XCgXchtvTT78_MCGPk1hHti_VrsX6b4Zg6H_bWsHeOZo03531Rl5enfCvKFyjWr4EsYaRCvS_rxfdi_VasXy03ulCv8qzf4C86UkiQOoKGU6QE0YcEfkjc8w9M7N0EdwEFgD9RFhx-uwc0yt8YCbQ3BGNk1wI6YHdEy-aOpn0_YMDkAyQPrQc_prk_zBs_OhML9QFOHesOOMLgE7nEaO0ZDLqWgh_jAr50HO94J4xyzujYJXKGDGjvIv07ktN0pe0Dt-zQwoBJd3KID4AJxK1sxh3vgFreYIITgWHjCrVJ0OGRAN05daKLHQwWNYkCLYjTBsF0zo9OP-DlL8nDkZzxIWa-d7KLn83-7ANBHEjzgbUoF7IxmaJ6KaqX7DvGOPYUL8gdXSzl6B0MgQxrTCT-4R02psBaJOE38MFQgEJtb0aj7Jtr7wznMJPPuGhbHzh1faF2C_joT1I7hfpwhxUjAurEmjJP39OdQoQez-B8goiJ4-GcQZ9PYgdxbJKlx0DPcQFfO7Y0SeQIiXTnJj8AYYwUYAi-sdTngiFwRAYQWu8NoIsnCg-J-gCdP4mqDp3JsByh5SO5W9LfnKyQ9_SdY4rCTOie2AriQwGP7kY_8wmERoriqY7BYEJhLvIR2kCYLsQW8PVBrcapwCQZcleHbifEawU_ZPFB1EgUYCklOTo9dUTkNE5N2eEwkIMTp86PCUgEoxgsqIaxdT5O-6Ve4pirZgiU0hka_LU4P0pPCYFsVO4lCHmgxKnNHifCIfgengcSRH81_MkBaEbJteFpznCfO-vA7RhIfL3GNwQ_ULDna47opNv7fnS54C6YmZzuZGBcU_z06e_PsNxc6fwi7MvvRpt07IqMaQ67w7JE6Rz8htClNERpS_VeqHdrj_3Ch7ZQ729LpTbbUprm8YSbY7eqGETe5N815tt8-gPQRvHgOxkYhykip-1o6CHq7Nmzmjc-HChMc1OmPUcZ6dXLT3wDHZlOcfHEe1Wv1PKC9ny5XP6r9yag0x1cLqKL8PkQ_D-kk_ycPsx_zCdhc_FzLuHPzL4yu2qHM9ov6225VKt6V8-6_VavVaVwa8pqtV1vVutGqWVZV7VSa011NeO9KlVVVmqnlsvtsl4sq812V9flitRmU27qYlVSj2xvama5mve1rJ5ZbMjGfJMq5eg0lXqhlFysYZ8FNGMbi1VppfXvKImTzVfw_75DZ2Ow-2fHW07d2Cy07y-u_WpeJhYL9Z6J_xcAAP__X0ilVA">