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

    <tr>
        <th>Summary</th>
        <td>
            [libc++] Erroneous internal capacity evaluation causes SIGSEGV in `vector<bool>`
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            libc++
      </td>
    </tr>

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

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

<pre>
    The internal capacity evaluation in `vector<bool>` is incorrect when evaluating `__external_cap_to_internal(0)`, resulting in an erroneous return value: `__external_cap_to_internal(0) = 288230376151711744` (`0x400000000000000`), while the correct result should be `__external_cap_to_internal(0) = 0`. Furthermore, this incorrect evaluation has propagated to other public APIs, causing a SIGSEGV error when compiling a program that calls `flip()` on `vector<bool>`, demonstrated as follows: 

[Godbolt Link](https://godbolt.org/z/3GGKofjjP)

```cpp
#include <iostream> 
#include <vector>

int main() {
  std::vector<bool> v;
 v.flip();
}
```
The complication error: 

```
Program returned: 139
Program stderr
Program terminated with signal: SIGSEGV
```

### Root cause analysis
The incorrect evaluation occurs due to the following faulty implementation of `__external_cap_to_internal`:

https://github.com/llvm/llvm-project/blob/8d2b070f07969f8358c93b9cf56834806fdc3efa/libcxx/include/__vector/vector_bool.h#L117-L119

The issue arises because `__n - 1` wraps around to become `size_type(-1) = 18446744073709551615` (`0xFFFFFFFFFFFFFFFF`) when `__n == 0`. A correct implementation should avoid this wrap-around behavior  for any `__n >= 0`.

### Proposed solution

To avoid the wrap-around arithmetic, the return statement can be rewritten as:

```cpp
return __n ? (__n - 1) / __bits_per_word + 1 : size_type(0);
```

or 

```cpp
return (__n + __bits_per_word - 1) / __bits_per_word;
``` 
This will automatically fix the SIGSEGV compilation error associated with `flip()`.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJyUVk1v4zYQ_TX0ZRCDor4PPiSbKFh0D0F30atBUaOIW4oUSMqO99cXpGTHcbvt1iCQxOTMPL6Z90LunHzViDuSP5D8ccNnPxi7O0qt0bIs37SmO-2-DQhSe7SaKxB84kL6E-CBq5l7aTRIDaSgBxTeWJJ-ao1RJH0iBQXpQGphrEXh4TigvoTp1xCz3-Pbkngv-LT3Zn8uRFhFCatJQQn7BBbdrGKQ1MA1oLVGo5kdWPSz1RCyIknvfykpkPQRWFWxlKZlkeRJmSRllgXAhFWkoPQtox8-EUYdkBwHqRD8gHC-1oIN3GBm1UGLvw4hpN1CM1s_oB2NxVDADx9Iu6J54A4mayb-yj124A2YEAjT3Cop4P7lswsJBJ9dYIrD18_PX5-e_4hs2YV-YcZJqmV7subV8hH8wD0IrpQL0Hslp8BC5B7Mz1obKnU4Gu28jXC4g94oZY4utoHeh5U_PJuuNcrDF6n_JPkjYdXg_RTOENYQ1rwu-1tjXwlrfhDWpM_Pv5n--_eXAGFJU9BliWkKf7JUaqHmDoGkn6Rx3iIfSfoEf9s8A39aEkntYeRSL_cDUj4Qeg_gfBfwpPe394QDSeORw_aKlvgVKR-vkRF6_y3OxDgpKZZ-RdqvyLg6-7JSv0wvhvKQpPXVjvMdWnv1hUc7Sh2pPko_QFAuVyFwbfNNiYWLZcHvxvg4GAhcc3Vy0q2I_3HSjBCzddDNGKYsDPvS2jA3PZ-VP4EcJ4Ujar9G9P8x9gUNFEdYNwMg_TC3W2FGwhqlDucfd5M131F4wppWmZawpupYS0va07Iu6r5K80rUaVuLPi-qNKto0XcixZ6HBLIVb2-ENessENbs92t3WbP8sg9N3g6EpV-SpLz7kiTruEVanJsRuJUOHbS4UBdvqOEOkiCNo-WTA27NrKMYWxRmjIec_IF7f5qQsOouOas9qbKsKLOMlmlJ6zxPiiS_tpzm5rN4ziLbtTJJH9994_7iQDe9WJ2IH4zsFjsJUO9WpC0O_CCNBeiNBa5P78mfLslv5-fFmsk47MAZNYciK1PmUgU_FOFW-mFEL8ViaXj2aee5j1BBcB3M0uLRSu9RA3eXCbkR_Bq7gGwCYec2BGpZA_t9K73bT2j3R2M7IOwBEgjauG4FfRfvR50YeyvRD3XXeiHpbaGfY7gpBHGuQiukUsBnb0buZTDdE_TyLVJ0tuvFo688BLhzRsh37d_a9HbT7dKuTmu-wV1SpkWSMsbyzbATXUWTjBVljmUl0hazNKm7ihUZrzlvi43cMcpymtCCsryk-TatK9onNOk51iJDJBnFkUu1DaIMNr2J2tglLClZsVG8ReXiA4KxIDvCHuJi4UFhd1HK7fzqSEaVdN695_HSq_j0uArLH-Hp8r_9Xx8dUZLuQtpP3yCb2ard_7aceEdHWLNe87BjfwUAAP__bF3gJw">