[boost] [variant2] Andrzej's review -- design

Subject: [boost] [variant2] Andrzej's review -- design
From: Andrzej Krzemienski (akrzemi1_at_[hidden])
Date: 2019-04-02 16:27:21

Hi Everyone,

First of all, I wanted to thank Peter for writing this non-trivial library
and sharing it with the community.

This is not a full review yet. I just wanted to discuss the design first,
especially the never-empty guarantee. And I am going to rehash the old
argument.

The core of variant2 is its never-empty guarantee and the mechanism to
achieve it: a number of different algorithms chosen depending on what the
potentially stored types permit. In fact this mechanism is not much
different than the one present in boost::variant.

The issue to solve is what happens in copy/move assignment of variant<X, Y>
when we have to change the stored type from X to Y. X has to be destroyed
and Y initialized. But if the initialization of Y throws we would be left
without either X (already destroyed) or Y (not successfully constructed).
(The same problem applies to member function emplace()). Except for the
last step boost::variant and variant2 try to apply the same sequence:

1. If all the subtypes have noexcept initialization, no safety measures
need to be taken.
2. If sub-types have noexcept move constructor, a temporary local storage
is used and the backup value is moved to and from it.
3. If one of the subtypes is a special type boost::blank or std::monostate
respectively, in case of a throw this type is default constructed in the
variant.
4. If there is any nothrow-default-constructible subtype in the variant, it
gets default-constructed upon exception.

If neither of the above can be applied, the two libraries apply different
approaches. variant2 is big enough to fit two unions of X and Y within its
storage. This way it does not have to destroy the X when initializing the
Y. boost::variant, for the additional storage uses heap allocated memory.
Interestingly, the double storage as in variant2 has been considered in the
initial design of boost::variant but rejected by the community, because it
added spacial overhead even for use cases that never invoked variant's
assignment. This is described in the Rationale section of boost::variant
documentation:
https://www.boost.org/doc/libs/1_69_0/doc/html/variant/design.html#variant.design.never-empty

In boost.variant, only these programs pay for the overhead that really
invoke the assignment operator.

Neither of the solutions seems strictly superior than the other. The double
storage could be thought as better because it seems to be able to cover use
cases where heap allocations are banned altogether. On the other hand, in
these applications it is difficult to imagine that X and Y would be
throwing exceptions in move constructors or during initialization. One
inferiority of boost::variant is that it can fail for its own reasons
unrelated to failures of X and Y. Even if no operations on X and Y throw
during the assignment of variant, the variant can still throw because it
allocates memory. Some people believe that an application cannot recover
from bad_alloc anyway, but this is not a universally held view.

To me, the important question is, do we really need the never-empty
guarantee. It was an unquestionable requirement for the initial design of
boost::variant. Now, variant2 is advertised as an allegedly superior
solution to std::variant, because the latter does not provide the
never-empty guarantee, even though the cost of providing it is significant.
But I myself fail to see the *practical* value of the never-empty guarantee.

The argument I hear is that, we want to make it an invariant that either X
or Y is stored in variant. I agree with this goal in general, but the costs
and contortions required to satisfy it outweigh the benefit. Now, I hear
that if the invariant is weakened everyone will have to check everywhere if
any variant is in a valueless_by_exception state. This seems to be
confirmed by the semantics of std::variant::visit(), which requires that
valueless_by_exception is checked and an exception thrown on valueless.
This last part is indeed strange in std::variant, but I do not agree that
the fix is to provide a never-empty guarantee at the cost of compromising
run-time performance and complicating the design.

I can think of the following alternative design. The invariant of a variant
(pun intended) allows for a valueless_by_exception state. There is no way
to get to this state other than by throwing form the initialization of Y in
variant's assignment or .emplace() operation. Calling .visit() on a
valueless variant is UB. The destructor and reset functions such as
assignment and .emplace() can handle the valueless state. This is almost
what std::variant does except for UB in .visit().

Why I find this superior to variant2.
1. It is simpler, faster and smaller.
2. Observing the valueless state can only happen when somebody is handling
exceptions incorrectly. And in that case this is exception handling
strategy that needs to be fixed: not the variant's guarantees.

It should be noted that variant2 DOES NOT PROVIDE A STRONG EXCEPTION SAFETY
GUARANTEE. The never-empty guarantee has a certain negative effect of
confusing people so that they are led to believe that they have strong
exception safety. But they don't. even expert programmers in this forum
expressed their surprise that changing from X to Y in variant<X, Y, Z> can
get them a variant storing Z. Sometimes it is even trickier: X may be a
container that currently stores 10 elements. You assign Y, and after the
exception you get an X that stores zero elements. Because of these
problems, the only reasonable thing to do is to follow the advice from Dave
Abraham's article: https://www.boost.org/community/exception_safety.html
To quote the relevant part, "If a component has many valid states, after an
exception we have no idea what state the component is in; only that the
state is valid. The options for recovery in this case are limited: either
destruction or resetting the component to some known state before further
use."

If this principle is followed no-one will ever observe the
valueless_by_exception state. This also applies to variant2. If this
principle from Dave Abrahams is followed, no-one will ever benefit from the
never-empty guarantee (but people will still pay the costs of providing
it). You cannot do anything meaningful with variant that threw other than
destroy or reset it. (But it is probably best to destroy it.) If objects
are allowed to survive the stack unwinding, they should either offer a
strong exception safety guarantee, or you have to have some very detailed
knowledge of a given particular type how its state gets modified under
exceptions, but this is usually very difficult and best left to experts.

I have started a thread in this list a while ago, requesting for an example
of code that *correctly handles exceptions* (does not stop stack unwinding
at random places), where the programmer would make use of the never-empty
guarantee , and chose something else than destroying or resetting the
variant. And although I received some generic statements, referring to the
purity of the design, strength of the invariants, and the easiness of
thinking or "correctness", none of the proponents of the never-empty
guarantee gave such an example. Which might be an indication that the
problem we are solving may be nonexistent. I am not sure of this claim, but
I have not seen any convincing example either.

I believe that we are facing one of this problems where the strong
invariants of the type need to be weakened due to practical considerations.
I can see no correctness issues with valueless state other than in programs
that are already exception-unsafe.

Also, I have heard claims that if someone is fine with valueless state they
should put std::monostate as one of the types and the same effect without
double buffering is achieved. But this is not true. Variant with monostate
can get the degenerate state in a correct program; often: in the variant
constructor. Now I really have to special-case it whenever I inspect the
variant object, which is a nightmare: this is really a weak invariant in an
allegedly strong-invariant variant. In contrast, for std::variant you only
get the valueless state in the program that incorrectly handles exceptions:
no need to special-case the valueless_state when doing visitation..

variant2 is not a replacement for std::variant, as the choice to support
never-empty guarantee at the cost of more expensive operations and
increased object size is not necessarily superior. Even if my view is not
generally held, it has to be acknowledged that the issue is controversial.
Variant2 cannot replace boost::variant either. This is not only about
supporting pre c++11, but also for different trade-offs in never-empty
guarantee, which were deemed inferior in boost::variant design. variant2 is
ismply a third point in the multi-dimensional design space of different
trade offs for variant-like libraries.

On a different subject, one thing that is missing from both:
boost::variant, and std::variant, is the narrow-contract observers for the
specific stored type, useful when I know by other means what is currently
stored in the variant object. This is something the third variant
implementation has a chance to change, however it chose to follow its
predecessors. This seems somewhat counter to the spirit of C++. We
requested a similar thing of Niall's Outcome library, and the
narrow-contract observers were added.

Below is the comparison between boost::variant, std::variant and variant2.
I do not know how to make a table in the email discussion interface, so I
will have to make it with a list.

1. Works in pre-c++11 dialects
* boost::variant: yes
* std::variant: no
* variant2: no

2. Size of variant<X, Y> (when X and Y are unfriendly)
* boost::variant: sizeof(void*) + SXY (SXY is the size of union{X x; Y y;})
* boost::variant: sizeof(int) + SXY
* variant2::variant: sizeof(int) + 2 * SXY

3. Uses heap allocations
* boost::variant: yes
* std::variant: no
* variant2: no

4. Throws its own exceptions in assignment
* boost::variant: yes
* std::variant: no
* variant2: no

5. Fast (narrow contract) access to X alternative.
* boost::variant: no
* std::variant: no
* variant2: no

7. Strong exception-safety guarantee
* boost::variant: no
* std::variant: no
* variant2: no

8. Never-empty guarantee
* boost::variant: yes
* std::variant: no
* variant2: yes

9. Throws its own exceptions in visitation
* boost::variant: no
* std::variant: yes
* variant2: no

Regards,
&rzej;