[libc++] Ambiguous call encountered in {ranges, std}::{count, find} algorithms

[winner245]

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, and the std::ranges::find and std::find algorithms encounter a similar ambiguous call to the internal function __libcpp_ctz, as demonstrated below.

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

Godbolt link

#include <exception>
#include <iostream>
#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: call to '__libcpp_popcount' is ambiguous
  }
  
  {
    using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
    std::vector<bool, Alloc> in(200, false, Alloc(1));
    in[in.size() - 2] = true;
    assert(std::ranges::find(in, true) == in.end() - 2); // error: call to '__libcpp_ctz' is ambiguous
  }

  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);
      |                              ^~~~~~~~~~~~~~~~~~~~~~


/opt/compiler-explorer/clang-trunk-20250112/bin/../include/c++/v1/__algorithm/find.h:112:56: error: call to '__libcpp_ctz' is ambiguous
  112 |       return _It(__first.__seg_, static_cast<unsigned>(std::__libcpp_ctz(__b)));
      |                                                        ^~~~~~~~~~~~~~~~~

Analysis

When used with sized_allocator with smaller integral types, the internal bitwise arithmetic in count.h exhibits integral promotions, yielding an int result. This results in no single best viable function among the viable set with (__libcpp_popcount(unsigned), __libcpp_popcount(unsigned long), and __libcpp_popcount(unsigned long long)), causing an ambiguous call error. Similarly, an integral promotion occurs in the internal bitwise logic of find.h, resulting in no single best viable function among three overloads of __libcpp_ctz.

Proposed Solution

Provide a function template that dispatches the call to the appropriate __libcpp_popcount (for count.h) or __libcpp_ctz (for find.h) based on the size of the integral types:

• For all smaller unsigned integer types (unsigned short, uint8_t, uint16_t, etc), dispatch the call to __libcpp_popcount(unsigned) or __libcpp_ctz(unsigned).
• For the larger integral types, dispatch the call to __libcpp_popcount(unsigned long) or __libcpp_popcount(unsigned long long) for count.h according to the sizeof(type) values. Similarly, dispatch the call to the rest __libcpp_ctz overloads for find.h.