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

    <tr>
        <th>Summary</th>
        <td>
            [libc++] Ambiguous call encountered in ranges::count
        </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>
    When using `vector<bool>` with a custom-sized allocator, the `std::ranges::count` and `std::count` algorithms encounter an ambiguous call to the internal function `__libcpp_popcount`, as demonstrated below.

Note: This issue came up while working on #119801.

[Godbolt link](https://godbolt.org/z/eG1n57qGx)

```cpp
#include <exception>
#include <limits>
#include <memory>
#include <vector>
#include <algorithm>
#include <cassert>

template <typename T, typename SIZE_TYPE = std::size_t, typename DIFF_TYPE = std::ptrdiff_t>
class sized_allocator {
  template <typename U, typename Sz, typename Diff>
 friend class sized_allocator;

public:
  using value_type = T;
  using size_type                   = SIZE_TYPE;
  using difference_type             = DIFF_TYPE;
  using propagate_on_container_swap = std::true_type;

  explicit sized_allocator(int i = 0) : data_(i) {}

 template <typename U, typename Sz, typename Diff>
  constexpr sized_allocator(const sized_allocator<U, Sz, Diff>& a) noexcept : data_(a.data_) {}

  constexpr T* allocate(size_type n) {
    if (n > max_size())
      throw std::bad_array_new_length();
    return std::allocator<T>().allocate(n);
  }

  constexpr void deallocate(T* p, size_type n) noexcept { std::allocator<T>().deallocate(p, n); }
  constexpr size_type max_size() const noexcept { return std::numeric_limits<size_type>::max() / sizeof(value_type); }
  int get() { return data_; }

private:
  int data_;

  constexpr friend bool operator==(const sized_allocator& a, const sized_allocator& b) {
    return a.data_ == b.data_;
  }
  constexpr friend bool operator!=(const sized_allocator& a, const sized_allocator& b) {
    return a.data_ != b.data_;
  }
};

int main() {
  using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
  std::vector<bool, Alloc> in(200, true, Alloc(1));
  assert(std::ranges::count(in, true) == 200); // Error: ambiguous call to __libcpp_popcount

  return 0;
}
```

The error message from clang is:

```
/opt/compiler-explorer/clang-trunk-20250110/bin/../include/c++/v1/__algorithm/count.h:59:30: error: call to '__libcpp_popcount' is ambiguous
   59 |     __r = std::__libcpp_popcount(std::__invert_if<!_ToCount>(*__first.__seg_) & __m);
      | ^~~~~~~~~~~~~~~~~~~~~~
```

#### Analysis
When used with `sized_allocator` with smaller integral types, the internal bitwise arithmetic exhibits integral promotions, yielding an `int` result. This does not match any of the three internal function overloads `__libcpp_popcount(unsigned)`, `__libcpp_popcount(unsigned long)`, and `__libcpp_popcount(unsigned long long)`, causing an ambiguous call error.


#### Proposed Solution

Provide a function template that dispatches the call to the appropriate `__libcpp_popcount` overload based on the size of the integral types. Specifically, for all smaller unsigned integer types (`unsigned short`, `uint8_t`, `uint16_t`, etc), dispatch the call to `__libcpp_popcount(unsigned)`. For the remaining larger integral types, dispatch the call to `__libcpp_popcount(unsigned long)` or `__libcpp_popcount(unsigned long long)` according to the `sizeof(type)` values. 

</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJy0WEmP274V_zT05WEMiRp5Ofjg8YyDXIoAmaJoLwIlPVtsKFIlKXsmh3724lGLN6Xpgv9ASGy9feWPFs7Jo0bcsPSFpa8z0frK2M1Zao2WP6ez3JSfm79UqKF1Uh-BLaITFt5YluxyYxRL3tgigrP0FQgoWudN_eTkTyxBKGUKQax8B75CknW-ZMmWJVsr9BFd97kwrfakRejyhulCUEdjpa9qB6jDW7QgNIg6l8fWtA4KoRR4E-xIImuh4NDqwkujSWmWKZkXTZM1phn0kmPCQYm10c5b4bGEHJU5z1m0ZdH2T8YjS7bwXkkH0rkWoRA1QtvAuZIK4WzsD8oKmeBJHK9XUdzLsvTliylzozwoqX-w9JXxVeV9E4Lme8b3x44-N_bI-P4n43v8Eut0-Y8vH4yvezWLqHuKpqGvPJG6UG2JwJIdfhTYUIBUhXuikrX0bopSY23s5xRlKO0jZazAFLEQzqH1PSnaeqwbJXyg-c8GNSXtPbTB8O3717-9Ze9__fYGLHmFseLUOZm_4Xz9ut9PcDbelvJwyHqrhRLOQWi8bGw8YMsXFm0BJh36861DP2-tysOh0wwHK1GXMGmBJS9dyE2bK1mQa2Svm5WTUC1mpDK4_t4xD9QuVCI-_hH7mKFbMQoaLepiQpjExnTdijXWNOIoPGZGZ4XRXkiNNnNn0dzm1dve5zE0APxolCykf4ier6T2IIOGiPE10LSUwouMSOHF8oUtX3tF_1cZoKAhxY_GTrgRaI_F2QXlnc5BFV-AIM-06cbnxmcx7z_deX5l_J3x7bDbkPHVpY56ECMBAHkAxlcaWPIGtfjIiJHxFY12mO6uZr6y5nxJfy7KTFgrPjON50yhPvqqF0oGxRZ9a_VF5jrg9xAi8c-vfNRX8pNBnYwsocQrkRBmQ4m7C_CSt-XLb324URm09a70btxXtbNzm62O5dbufQp0W6OVRTYsvd2ojHwJLLX46PUxvg_GzIHx1WVI7xyjzj6iH2QuRrsOGTlp-K08iXBUjJID02Oq-3VChyeYBm2XtFd6ftXHXcvu4JfU_Lbzekf7ZoZOO-TzK6dgogCTnvH4j_QsaJ_2jP4d8kcZrYXUl2JcrbYt2euW2MP8B4hCPTw0Siu1jxfdETO-HN4l49IcSbdgh-86azTSwRseBRBBS_NC5Ku4H_JeW3888tW_gT-0Si-q1kPRgoGuLwNmgDdryZ_tBPZ5hDh98_VZj_p8dukdgEXH9F4hIKmGGp0TR4SDNTUdevoI0nWtfS_G96bxjO8LUzdSoX2ig8JYtPSOJJ-8bfWPJx7xNIrjiPF9TlHu53PG9z2AIF7GX8KzP8WM77PsgjZIeav9vGLJNl2zZJtEFDwOWRhiZ3z5GD5fgnSXRHU9mFL_7MLuzTJ7e_hNqFhdEaU-ofWZPLBkx3icvZtdYOrX3TbLDtI6P88yh8fuEOELyLL6Zn1DsM_St39O_T2WhvFkfGCrhfp0kmLpUTmWHfom4HzX_wMwd7VQCm0AxkcrVDhf3QDLR7icS3-WDkGE1KOXBeBHJXPp3UW0saY2hDmD_KdEVdIQigCyZQfXLbpW-XmHm0uDDrShAfZFBUJ_gjkEw76yOIXWzQmtMqJ007idr1odbi0lpbVD8b9hBGX08cLd3zN-K3EnVohu4TxePEI7DsD_rmLfrGkMVem7UW0A64HnmzUnWSKIS9wjPPKV8FBK11DG0IVkXV9wRENwzsoApaavNmMSIRdknNRXGDbkkP7bbpjD9wYLeZBk6JPCPRhLOGfsnjE1QRBtJ0cYhy2ikegqY_2lKrRvV9ndi7Bsuzfoi7Ard2O8N9H-Rw0wh72xQcwinRJUIyXscbLj_xczV30AdKv471oHRFEYG6akr18_qgF_DMhjEXX3BTcHFm1n5SYp18lazHATL5NF-pws4-Ws2iR4WC3LNE3EOl6scY3xIk7S9aJMozzPCzGTm2Hb8jhO4-X8eZXzxer5-ZAUz6s0WrPniLKk5kqdarp7zsLNdhNznvLVTIkclQu_B3BOQQ67mbP0dWY3JPWUt0fHniMlnXcXPV56FX5JuBJLX2F7NyvDBT50EjychLPWqs3dRVn6qs3nhaHzgMz1_z011vwdCzqCQgyO8X0fxmnD_xUAAP__oAxaoQ">