Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the purpose of having an empty pair base class?

Tags:

c++

libstdc++

libstdc++'s implementation of pair has the following oddity

template<typename, typename> class __pair_base
  {
    template<typename T, typename U> friend struct pair;
    __pair_base() = default;
    ~__pair_base() = default;
    __pair_base(const __pair_base&) = default;
    __pair_base& operator=(const __pair_base&) = delete;
  };

template<typename T, typename U>
  struct pair
  : private __pair_base<T, U>
{ /* never uses __pair_base */ };

__pair_base is never used, neither can it, considering it's empty. This is particularly confusing since std::pair is required to be conditionally structural

pair<T, U> is a structural type if T and U are both structural types.

And having private bases makes it non-structural.

like image 556
Passer By Avatar asked Nov 20 '20 14:11

Passer By


1 Answers

tl;dr This is the result of a really long series of hacks to implement the insane overload/explicit rules of std::pair and maintain ABI compatibility. It is a bug in C++20.


Disclaimer

This is more of a "fun" ride along with the standard library authors down memory lane then some insightful language level revelation. It shows how extremely complicated C++ has became that implementing a pair, of all things, is a herculean task.

I tried my best recreating the history, but I'm not one of the authors.

Pair Primer

std::pair is much more than simply

template<typename T, typename U>
struct pair
{
    T first;
    U second;
};

There are 8 different constructors listed on cppreference, and for an implementer, it's even more: every conditionally explicit constructor is actually two constructors, one for implicit, another for explicit.

Not all of these constructors participate in overload resolution, if they did, there would be ambiguity everywhere. Instead, there are many many rules governing when each does, and every combination of the aforementioned cases have to be written and disabled manually by SFINAE.

This culminated to 5 bug reports throughout the years on the constructors alone. Now about to become 6 ;)

Prologue

The first bug is about short-circuiting the checks of convertibility of the pair parameters if the types are the same.

template<typename T> struct B;
template<typename T> struct A
{
    A(A&&) = default;
    A(const B<T> &);
};

template<typename T> struct B
{
    pair<A<T>, int> a;
    B(B&&) = default;
};

Apparently, if they checked convertibility too early, the move constructor gets deleted due to the circular dependency and how B is still incomplete within A.

nonesuch

This however changed the SFINAE properties of pair. In response, another fix was implemented. This implementation enabled previously invalid assignment operators, and so the assignment operators were turned off manually by changing their signatures

struct nonesuch
{
    nonesuch() = delete;
    ~nonesuch() = delete;
    nonesuch(nonesuch const&) = delete;
    void operator=(nonesuch const&) = delete;
};

// ...
pair& operator=(
    conditional_t<conjunction_v<is_copy_assignable<T>,
                                is_copy_assignable<U>>,
                  const pair&, const nonesuch&>::type)

Where nonesuch is a dummy type that essentially makes this overload uncallable. Or is it?

no_braces_nonesuch

Unfortunately, even though you couldn't ever create a nonesuch

pair<int, int> p = {};  // succeeds
p = {};  // fails

you could still initialize it with braces. Since delete doesn't resolve overload resolution, this is a hard failure.

The fix was to create no_braces_nonesuch

struct no_braces_nonesuch : nonesuch
{
    explicit no_braces_nonesuch(const no_braces_nonesuch&) = delete;
};

The explicit turns off participation in overload resolution. Finally, the assignment is uncallable. Or is it...?

__pair_base v1

There is, unfortunately, another way to initialize an unknown type

struct anything
{
    template<typename T>
    operator T() { return {}; }
};

anything a;
pair<int, int> p;
p = a;

The authors realized they could solve this "easily" by leveraging the default generated special member functions: they could be not declared at all if you have a base that is non-assignable

class __pair_base
  {
    template<typename T, typename U> friend struct pair;
    __pair_base() = default;
    ~__pair_base() = default;
    __pair_base(const __pair_base&) = default;
    __pair_base& operator=(const __pair_base&) = delete;
  };

All unit tests passed, and things are looking bright. Unbeknownst, the shadow of an evil bug looms ominously on the horizon.

__pair_base v2

ABI broke.

How is that even remotely possible? Empty bases are optimized out aren't they? Well, no.

pair<pair<int, int>, int> p;

Unfortunately, empty base optimization only applies if the base class subobjects are non-overlapping with other subobjects of the same type. In this case, the __pair_base of the inner pair overlaps with the one of the outer pair.

The fix was "simple", we templatize __pair_base to ensure they are different types.

Structural Types

C++20 came, and it requires that pair be structural types. This requires that there is no private bases.

template<pair<int, int>>
struct S;  // fails

So ends our journey. This reminds me of Chandler Carruth's quick survey at cppcon: "who can build a C++ compiler in a year if they needed to?" Only current compiler writers think they could, given how complicated C++ is. Apparently, I don't even know how to implement std::pair.

like image 155
Passer By Avatar answered Nov 08 '22 02:11

Passer By