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

    <tr>
        <th>Summary</th>
        <td>
            PSTL partial_sort.cc test fails with libstdc++ debug mode
        </td>
    </tr>

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

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

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

<pre>
    This test fails using `-D_GLIBCXX_DEBUG` with libstdc++:

https://github.com/llvm/llvm-project/blob/e3c9327bc493286bf420d1520df8217ae559f5c3/pstl/test/std/algorithms/alg.sorting/partial_sort.pass.cpp#L138

The problem is that `__pstl::__tbb_backend::__merge_func::split_merging` (shouldn't that be a reserved name?) does:

https://github.com/llvm/llvm-project/blob/f96e85b9494f549976fac3947756e6da1fcc572b/pstl/include/pstl/internal/parallel_backend_tbb.h#L1017

which aborts because the range is not correctly sorted w.r.t `_M_comp`, as required by `std::upper_bound`.

The range looks like this:

```
$1 = std::__cxx1998::vector of length 1284, capacity 1284 = {{val = 0}, {val = 5290}, {val = 9862}, {val = 8699}, {val = 5471}, {val = 4810}, {
    val = 6176}, {val = 1400}, {val = 5025}, {val = 3246}, {val = 2547}, {val = 8814}, {val = 2463}, {val = 8800}, {val = 3074}, {val = 5741}, {
    val = 5234}, {val = 736}, {val = 4895}, {val = 6803}, {val = 2363}, {val = 5351}, {val = 6719}, {val = 7967}, {val = 732}, {val = 1399}, {val = 7586}, 
  {val = 4659}, {val = 3800}, {val = 6956}, {val = 4087}, {val = 9090}, {val = 2293}, {val = 8702}, {val = 2263}, {val = 7765}, {val = 3233}, {
    val = 8440}, {val = 3918}, {val = 8259}, {val = 6439}, {val = 6465}, {val = 6794}, {val = 3656}, {val = 10018}, {val = 4621}, {val = 9397}, {
    val = 4973}, {val = 584}, {val = 9046}, {val = 6530}, {val = 2474}, {val = 4118}, {val = 2970}, {val = 162}, {val = 4850}, {val = 9401}, {val = 7748}, 
  {val = 9509}, {val = 2923}, {val = 4425}, {val = 8349}, {val = 6766}, {val = 6719}, {val = 6773}, {val = 3783}, {val = 4205}, {val = 4759}, {
    val = 6976}, {val = 8123}, {val = 2739}, {val = 3136}, {val = 4309}, {val = 4286}, {val = 6792}, {val = 4048}, {val = 8908}, {val = 664}, {
    val = 3774}, {val = 9019}, {val = 9710}, {val = 111}, {val = 1214}, {val = 8581}, {val = 2996}, {val = 6409}, {val = 3152}, {val = 7150}, {
    val = 3878}, {val = 7415}, {val = 10073}, {val = 3057}, {val = 238}, {val = 1314}, {val = 9776}, {val = 7011}, {val = 5097}, {val = 8734}, {
    val = 6524}, {val = 1794}, {val = 6578}, {val = 9263}, {val = 9962}, {val = 5640}, {val = 3271}, {val = 1229}, {val = 4441}, {val = 6932}, {
    val = 1893}, {val = 2968}, {val = 425}, {val = 6356}, {val = 2994}, {val = 6671}, {val = 4658}, {val = 743}, {val = 2801}, {val = 2563}, {val = 7893}, 
  {val = 1433}, {val = 4731}, {val = 2441}, {val = 4490}, {val = 4970}, {val = 8787}, {val = 3987}, {val = 6734}, {val = 3605}, {val = 7474}, {
    val = 2979}, {val = 152}, {val = 8805}, {val = 1964}, {val = 10114}, {val = 4166}, {val = 10267}, {val = 6096}, {val = 3360}, {val = 1673}, {
    val = 2742}, {val = 6328}, {val = 7130}, {val = 9098}, {val = 4075}, {val = 8554}, {val = 8509}, {val = 9850}, {val = 1077}, {val = 794}, {
    val = 7465}, {val = 2510}, {val = 5525}, {val = 4659}, {val = 1753}, {val = 216}, {val = 3167}, {val = 493}, {val = 1704}, {val = 1525}, {val = 7967}, 
  {val = 4683}, {val = 6709}, {val = 6493}, {val = 1400}, {val = 1297}, {val = 5412}, {val = 6420}, {val = 7394}, {val = 8772}, {val = 2846}, {
    val = 10136}, {val = 9853}, {val = 9976}, {val = 3709}, {val = 8682}, {val = 8252}, {val = 1939}, {val = 8253}, {val = 4082}, {val = 7765}, {
    val = 5439}, {val = 1345}, {val = 3012}, {val = 4851}, {val = 3098}, {val = 8260}, {val = 2771}, {val = 3591}, {val = 4717}, {val = 9328}, {
    val = 1279}, {val = 9401}, {val = 5758}, {val = 2525}, {val = 5554}, {val = 1809}, {val = 7937}, {val = 1696}, {val = 9203}, {val = 1183}...}
```

This is indeed not partitioned:

```
(gdb) p __val
$2 = (const Num<float> &) @0x7ffff7994e28: {val = 687}
(gdb) p __first[46]
$4 = (Num<float> &) @0x7ffff79930c8: {val = 9397}
(gdb) p __first[47]
$5 = (Num<float> &) @0x7ffff79930cc: {val = 4973}
(gdb) p __first[48]
$6 = (Num<float> &) @0x7ffff79930d0: {val = 584}   <-------- BUG
(gdb) p __first[49]
$7 = (Num<float> &) @0x7ffff79930d4: {val = 9046}
```

The requirement for `upper_bound` is:

> _Preconditions_: The elements `e` of [`first`, `last`) are partitioned with respect to the expression
`!bool(invoke(comp, value, invoke(proj, e)))`.

where that's defined in [alg.sorting.general].

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJysWV1v2zoS_TX0C1GDHH4_-KFu6mKB7uIC2wvcN0MflK2GlryinDT_fiE5SZ34rHcDbGG01UiaOXNmODOkipzbXRfjipk1M3eL4jTu-2H187G4j-lpUfb10-rHvs18jHnkTdGmzE-57XacWfHpbvvt-9_WX_76a3v3df3nN2YFf2zHPU9tmce6YrSefuozE3dMPP-9H8djnmS0YbTZteP-VC6r_sBok9LDyz-fjkP_M1Yjo02Z-pLRJqoqKHJlpYMib8tGk6ilIVE3nqQrojGhMZVitDnmMTHaTJAZbfJYM9oUadcP7bg_5PPFMvfD2Ha76fFiGNsibSfJ8ljkvKyOR0bqu1T-EvmPfeTHoS9TPPCJkX0xTixst7M99Zmpz9vtWJbbsqjuY1e_iA5x2MVtc-qqsyQfUzvO0sm-FZyRz_v-lOqOkRvPisvICz7EHIeHWPOuOESmNowCr_uY_0-UNsFGb8qgg26MDsHZpqhU0M4ZG21dyKaqjKPyN6VtV6VTHS8FYxy6Ip1pLFKK6cX9iYrlfuZRSHeJ93HfVntelP0wZl7GqjjlyMd95EPR7eLEbdePvOqHIVZjeuJTYGLNH5fD8sz437dVfzgyKxh94UXmQ_zXqR1izcun6f4U8Znp0_EYh23Zn7qaWbF8H8yzudT395mn9n7C0L7ndjJy_p0vSUvO1B1_tbHdVr9-yRD8-fIhVmM_8L7hKXa7cc8leT3BrIpjUbXj0yyYVTC3Zm79UKT5SjB3Nz13ITIUgDR4S9dSb0MAGrST11Lt5YXes2Occ_5y30pnr9-SWiCMgsy1VJEGGshoB5B7qcGz2ir0LMKghAMajNPylpeGFHjLKQBc-wCctF4AiKQQcKMMCIR1EgTNBQtocgpEXSoUdWf8qxPPbl86Yw14R0FmbTCIDuEBwCBQthIFFEcngDdEiDrnLMwwpW5F12uNMiVID9AQYsRqBaUIjXUB5JKyiD0pBAKhLYEMCSq4W27q4FC2eYAmCLQmrVEoahqtKC0RcAoOaJCoSGlvUEHTAnjunPb_OYmDESA4FAiwoTUqUV5pFF5nEUlwnVqHuFfOIwwkAAbtLhMPFOKACrGXyEtyKF2VhPVMIfY0eeh7QJEUGi2kIIDUWn3LSeVQrgWBKA9OolyTIH8kobbijQfPUgjIc41YUtIAPpw0N1uq8g4w47QEWSGFgIklDKi6pIBeqZDvwaFscgKxZ0RArdqpm6G0hoBdCYujNYiRAFtACKiaGAtLPKGRRxKhjNcadeVw2WqvvZQetTQKFlV1VHqsQn2BAqTJwgnOGphOCJdH1ZUMbLUXnl3XXKkVqmxOIf2QWa3RiKBhA_EODRkqIKl1aJRTFtVc96a1XUeXggOZAhe998iADBYtAiHRmtQS9RspCI2AVqAypZSF_dfdnI_IaeCRVYTySqIZIYiAEl441GyNgcUYFdgAhwQpHBqKw81YOjiskUFNxBi0VPGwLJ1BK02i6EgUSY0qiHQCJQ7EdblHQCM-mkGsQ3RbjAVu9iShrmC0RKmkCWhwChU57xzaDvjLgRXUYQGHm-BRcAIcpRSkxFuPVjuhGiADGrs8IQxaIL1v9zdgnwr3IVJptCsSKBTao82nguvXE6om5FAXUiagIu8k2h2-qSwgmITKLt4aGIe6H8GFYmDlkR7F3QUFkEuLqm4gtPmXcl54y-VyugcPkJ5Pn9rMp19Xx1jPx13zKeTY9l2s_9sRlN_VJaPAj3y7fSjS68kUzRgY-arv8sj_cTow9aVJfTEy9ZUzstNLTAvxyzVN07gQdCTP1Oc36_bcYIGpph3yyMxaW2ZeH9D6xej_YE6J6r25lw3uLXvu0p75mL3qnb2XDfMte_7Snv2QvVq8s3feinPOmfry6fkPX__57SaAcAnAfQyAfk_w87b_VjLGlxPUQ-xG3vQDZ1a8PTzl1yej6ivf_jHEqu_qOXHzdjI9aYtp1pQnNXF6uW84M2tmxdnF88EtsyIVz1eBF0O8XAPnDwlDzMdYjXzs5_Ph-Os4xJzbvvvtDsmy7xMj33YP_X2cs_9wnPQ_FOkUp_-83jkO_c9JEBmF59-7Y-HHfRzifALPyGVex6adwLTdhP_is8FyF7s4FImZu-f3F_VK1UGFYhFX0gnrhLVWL_YrE6WXRkTb-CYKIyshYjRNI4InZX29aFckSAup5PQTehkKYbyMkhptah0rpkU8FG1apvRwWPbDbtHmfIorPzXARSrKmPL8AYeoi498vsmImLlbDKv56L887TLTIrV5zL-1jO2Y4uqPf_74zt98A6mqy8891190eB3L044f-jouTkNaffj7w4wwM9rMHvw7AAD__6TrmKw">