microsoft / microsoft/STL

Comparison operators of containers shouldn't unconditionally call `_Unchecked_begin` etc.

Open
#4,040 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug
Dominant language
C++
Stars
11.1k
Forks
1.7k
Avg merge
4d 15h
Merged PRs (30d)
22

Description

Describe the bug

The following program is rejected when using MSVC STL (in C++23 mode), while the program-defined specializations of std::array seem to be well-defined.

#include <array>
#include <cstddef>
#include <iterator>
#include <stdexcept>
#include <utility>

struct Foo {
    friend constexpr auto operator<=>(Foo, Foo) = default;
};

template<std::size_t N>
struct std::array<Foo, N> {
    using value_type = Foo;
    using pointer = Foo*;
    using const_pointer = const Foo*;
    using reference = Foo&;
    using const_reference = const Foo&;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using iterator = Foo*;
    using const_iterator = const Foo*;
    using reverse_iterator = std::reverse_iterator<Foo*>;
    using const_reverse_iterator = std::reverse_iterator<const Foo*>;

    constexpr void fill(const Foo&) {} // Foo is no-op assignable.
    constexpr void swap(array&) noexcept {} // Foo is no-op swappable.

    constexpr iterator begin() noexcept { return elems_; }
    constexpr const_iterator begin() const noexcept { return elems_; }
    constexpr iterator end() noexcept { return elems_ + N; }
    constexpr const_iterator end() const noexcept { return elems_ + N; }

    constexpr reverse_iterator rbegin() noexcept { return reverse_iterator{elems_ + N}; }
    constexpr const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator{elems_ + N}; }
    constexpr reverse_iterator rend() noexcept { return reverse_iterator{elems_}; }
    constexpr const_reverse_iterator rend() const noexcept { return const_reverse_iterator{elems_}; }

    constexpr const_iterator cbegin() const noexcept { return elems_; }
    constexpr const_iterator cend() const noexcept { return elems_ + N; }
    constexpr const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{elems_ + N}; }
    constexpr const_reverse_iterator crend() const noexcept { return const_reverse_iterator{elems_}; }
    
    [[nodiscard]] constexpr bool empty() const noexcept { return false; }
    constexpr size_type size() const noexcept { return N; }
    constexpr size_type max_size() const noexcept { return N; }

    constexpr reference operator[](size_type n) { return elems_[n]; }
    constexpr const_reference operator[](size_type n) const { return elems_[n]; }
    constexpr reference at(size_type n) { return n < N ? elems_[n] : throw std::out_of_range{"bad array<Foo> access"}; }
    constexpr const_reference at(size_type n) const
    { return  n < N ? elems_[n] : throw std::out_of_range{"bad array<Foo> access"}; }
    constexpr reference front() { return elems_[0]; }
    constexpr const_reference front() const { return elems_[0]; }
    constexpr reference back() { return elems_[N - 1]; }
    constexpr const_reference back() const { return elems_[N - 1]; }

    constexpr pointer data() noexcept { return elems_; }
    constexpr const_pointer data() const noexcept { return elems_; }

    Foo elems_[N];
};

template<>
struct std::array<Foo, 0> {
    using value_type = Foo;
    using pointer = Foo*;
    using const_pointer = const Foo*;
    using reference = Foo&;
    using const_reference = const Foo&;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using iterator = Foo*;
    using const_iterator = const Foo*;
    using reverse_iterator = std::reverse_iterator<Foo*>;
    using const_reverse_iterator = std::reverse_iterator<const Foo*>;

    constexpr void fill(const Foo&) {} // Foo is no-op assignable.
    constexpr void swap(array&) noexcept {} // Foo is no-op swappable.

    constexpr iterator begin() noexcept { return nullptr; }
    constexpr const_iterator begin() const noexcept { return nullptr; }
    constexpr iterator end() noexcept { return nullptr; }
    constexpr const_iterator end() const noexcept { return nullptr; }

    constexpr reverse_iterator rbegin() noexcept { return reverse_iterator{end()}; }
    constexpr const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator{end()}; }
    constexpr reverse_iterator rend() noexcept { return reverse_iterator{begin()}; }
    constexpr const_reverse_iterator rend() const noexcept { return const_reverse_iterator{begin()}; }

    constexpr const_iterator cbegin() const noexcept { return nullptr; }
    constexpr const_iterator cend() const noexcept { return nullptr; }
    constexpr const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{end()}; }
    constexpr const_reverse_iterator crend() const noexcept { return const_reverse_iterator{begin()}; }
    
    [[nodiscard]] constexpr bool empty() const noexcept { return true; }
    constexpr size_type size() const noexcept { return 0; }
    constexpr size_type max_size() const noexcept { return 0; }

    // Perhaps these functions of std::array<T, 0> shouldn't be constexpr as an invocation is always throwing or UB.
    reference operator[](size_type) { std::unreachable(); } // UB
    const_reference operator[](size_type) const { std::unreachable(); } // UB
    reference at(size_type) { throw std::out_of_range{"bad array<Foo, 0> access"}; }
    const_reference at(size_type) const { throw std::out_of_range{"bad array<Foo, 0> access"}; }
    reference front() { std::unreachable(); } // UB
    const_reference front() const { std::unreachable(); } // UB
    reference back() { std::unreachable(); } // UB
    const_reference back() const { std::unreachable(); } // UB

    constexpr pointer data() noexcept { return nullptr; }
    constexpr const_pointer data() const noexcept { return nullptr; }

    unsigned char dummy_[1];
};

static_assert(std::array<Foo, 0>{} == std::array<Foo, 0>{});
static_assert(!(std::array<Foo, 0>{} < std::array<Foo, 0>{}));
static_assert(std::array<Foo, 0>{} <=> std::array<Foo, 0>{} == std::strong_ordering::equal);

static_assert(std::array<Foo, 1>{} == std::array<Foo, 1>{});
static_assert(!(std::array<Foo, 1>{} < std::array<Foo, 1>{}));
static_assert(std::array<Foo, 1>{} <=> std::array<Foo, 1>{} == std::strong_ordering::equal);

int main() {}

Command-line test case

Godbolt link

Expected behavior

The program compiles. For program-defined container specializations, comparison operators should not call _Unchecked_begin/_Unchecked_end.

For contiguous containers/views, it seems OK to unconditionally call member data and size. For other containers, it may be needed to fall back to begin/end when _Unchecked_begin/_Unchecked_end are unavailable.

STL version

Microsoft Visual Studio Community 2022
Version 17.8.0 Preview 1.0

Additional context

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the linked Godbolt reproduction and inspect the STL comparison-operator implementation that handles container comparisons, focusing on its _Unchecked_begin and _Unchecked_end calls. Done means the supplied C++23 program compiles and all listed static assertions pass for both zero- and one-element std::array specializations.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
devtools
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.