A variant for the everyday Joe

July 1, 2015 | By David Sankel | Filed in: C++.

There’s been a lot of discussion lately on the design of a standard variant type for C++. To be sure, there are several difficult decisions that need to be made and many of these are contentious. This post aims to put forward the rationale for the choices made at the Lenexa C++ Committee meeting for a std::variant design.

Motivation

Lets review what we are trying to model with a variant. Mathematically we are attempting to model a discriminated union. More concretely, if we have types T1, T2, ..., TN we want a variant<T1,T2,...,TN> to have a value of type T1, a value of type T2, … , or a value of type TN.

Variants are incredibly useful in practice. Say you allow your user to store a domain name or an IP address in a configuration file. Once you parse that, what data structure will you hold it in? Here’s one option:

While this approach is quite common and will certainly work, there are several drawbacks. The first and foremost of these drawbacks is that this methodology makes it easy to write incorrect code. Consider the following example:

The above function will work just fine until place.hasIpAddress() == true. Given the proliferation of auto-completion, the writer of the code may have never noticed that a precondition existed on the domainName() method. One could argue that the writer of greet was sloppy and got what he deserved. True as that may be, we’d really like to eliminate this kind of error if at all possible.

The second problem with the above methodology is that extending the data structure to support more alternatives (such as a NetBIOS name in the above example) is problematic. Aside from the overhead of all the extra code, call sites need to be inspected carefully to be sure they are correct with the new alternatives. Consider the following getIpAddress function:

Finally, the space overhead of DomainNameOrIpAddress is less than ideal. Because we only need to store one of a name or an ip address at a time, we would like sizeof(DomainNameOrIpAddress) to be something like sizeof(bool) + max(sizeof(IpAddress), sizeof(DomainName)).

The ideal variant

Given the drawbacks of the aforementioned approach and the frequency of this pattern, it seems prudent to write some generic code that makes lives easier. std::variant to the rescue. 1

We use simple assignment to initialize a variant and modify its value.

We would use a visit member function to do something with the value within a variant.

The visit function used above has the nice property that it will only compile if all the alternatives are handled. We can also handle multiple cases at once using overload sets.

With this hypothetical variant implementation we’ve removed heaps of boilerplate, made it much more difficult to write incorrect code, made a straightforward way for people to add alternatives without having to search their code for uses, and, with a clever implementation that uses C++ unions, solves the space problem.

The final consideration for our ideal variant is its exception safety. Recall the four exception safety levels 2:

  1. No-throw guarantee, also known as failure transparency: Operations are guaranteed to succeed and satisfy all requirements even in exceptional situations. If an exception occurs, it will be handled internally and not observed by clients.
  2. Strong exception safety, also known as commit or rollback semantics: Operations can fail, but failed operations are guaranteed to have no side effects, so all data retain their original values.
  3. Basic exception safety, also known as a no-leak guarantee: Partial execution of failed operations can cause side effects, but all invariants are preserved and no resources are leaked. Any stored data will contain valid values, even if they differ from what they were before the exception.
  4. No exception safety: No guarantees are made.

Because our variant will necessarily be calling operations on its alternatives which may only have basic exception safety, the no-throw guarentee is out of the question. That leaves us with strong exception safety as being the most ideal level.

So everything is great … except we can’t have this variant.

Why we can’t have the ideal variant

The reason we cannot have the ideal variant boils down to exception safety issues. Consider the following code:

Here is the sequence of events that occurs during the assignment.

  1. The DomainName destructor is called.
  2. place‘s internal index is set to that corresponding to IpAddress.
  3. The IpAddress‘s move constructor is called.

If an exception is thrown during #3, we need to consider what state place should have. With strong exception safety, we need to revert back to the original DomainName. This is impossible, however, due to #1. The only way we can maintain strong exception safety, unfortunately, is to make the variant twice as big as we desired at the outset.

Relaxing our variant to only have basic exception safety doesn’t improve things. variant‘s move assignment cannot safely set the variant to some other value because that could throw as well. If the assignment operation does nothing special to handle exceptions, then we’ve got a variant with its invariants broken. That option implies no exception safety.

How to fix? Some options considered.

The alternatives each attempt to supply basic exception safety to variants and each comes with its own drawbacks. These drawbacks tend to fall into three areas: adding complex criteria as to which types are allowed to be in a variant, giving all variants an injected state called “empty”, and allowing variants the possibility of becoming “invalid”.

Restricting allowed types with complex criteria

First lets look at the alternatives that restruct the types that can be used with variant. The least restrictive of these would be the requirement that at least one of the alternatives has a no-throw default constructor. In the case of an exception on assignment, the type with the nothrow default constructor could be safely used to set the value of the variant and we gain basic exception safety.

How frequently does one come across a variant that does not include a default no-throw alternative? As it turns out, they occur quite frequently. In example above it is entirely reasonable for the designer of ‘IpAddress’ and ‘DomainName’ to not include a default constructor at all being there are no reasonable defaults. Because use of a variant would force undesirable modifications to either ‘IpAddress’ or ‘DomainName’, this design clearly breaks the open-closed principle (open to extension, closed to modification).

Another variation of restricting allowed alternatives is to require every alternative of a variant to have a no-throw move-constructor. If this is the case, the variant doesn’t have to worry about an exception being thrown in assignment. How many classes fail to abide by this restriction? Well, pretty much every use of the common PIMPL idiom requires allocation in their move-constructors in order to maintain invariants in the copied-from object.

In sum, all the options restricting the use of variant to friendly types remove a significant number of use-cases. The restrictions have the added drawback of being difficult to teach.

The injected “empty” state

This solution extends the number of values the variant can have. In this case, a variant<T1,T2,...,TN> has a value of type T1, a value of type T2, … , a value of type TN, or is “empty”. If there is an exception during assignment, the variant simply becomes empty. The benefit is that this variant has no restrictions at all on its alternative types.

Because the majority of variants are not modeling values that have an inherent “empty” state (std::optional being a notable exception), user code will need to document nonempty preconditions for almost every function that takes a variant as a parameter.

Usually this solution is also accompanied with the behavior that a default constructed variant is an “empty” variant. When it is so easy to create an “empty” variant, it further necessitates documentation of preconditions and careful checks to prevent unwanted behavior.

The “invalid” state

The “invalid” state solution is an attempt to have our cake and eat it too. This is the solution that achieved consensus at the Lenexa C++ Comittee meeting and is hereafter referred to as the Lenexa variant. Similar to the injected “empty” state, the variant can have a value that is none of its alternatives. Also similar to the injected “empty” state, if there is an exception during assignment, the variant becomes this special value. The key differences are as follows:

  • The state is called “invalid” instead of “empty”.
  • The only ways for a variant to get into an invalid state are to get assigned to another invalid variant, or be the destination of an assigment that throws. 3
  • The operations related to inspecting the variant’s contents have a validity precondition. Note that the valid() method, which returns a boolean corresponding to whether or not the variant is valid, has no preconditions.
  • The “invalid” state does not change the semantics of the code during normal operations. With the exception of exception handlers, all code can treat variant<T,U> as if it only held values of type T and values of type U.

The Lenexa variant attains basic exception safety by specifying valid() == true preconditions on functions that wouldn’t make sense on a variant that is the result of a throwing assignment.

It is important to emphasize that invalid variants only come up in exception handling code and only need special treatment there. The rest of the code can operate as if all variants were valid. The only way a function can get passed an invalid variant is if someone, somewhere swallowed an exception without cleaning up properly. If that happens you’ve got a bug somewhere and have bigger problems.

One might wonder where exactly the “invalid” state variant would be treated differently in exception handling code. Lets take a look at the scenarios where this comes up.

In the following example we try to recover from an allocation error by repeatedly attempting to run a calculation until enough memory is freed up to do the assignments. Note that in this example the exception handling code would be the same for both the ideal variant and the variant with the “invalid” state solution.

In this next example we are providing a guarantee that if the calculation or some assignment fails, neither name nor place is modified. This code will only provide that guarentee if all the alternatives in a variant are no-throw copy-constructable. This condition applies to all the variant options we’ve considered thus far.

Note again that there is no difference in the handling code between the ideal variant and the variant with the “invalid” state solution.4

Finally in the next example we have a contrived situation where handling with the ideal variant and the Lenexa variant actually differ.

In this case, the ideal variant would print out the original value of place. The non-ideal variants, aside from the Lenexa variant, would print out some undetermined value of place. The Lenexa variant would have undefined behavior.

Below is a modification of this function that works properly with the Lenexa variant.

Although there is indeed a difference in this exception handling code, the original code is already suspect. If there is an exception thrown during assignment with an object that only meets the basic exception guarentees, the value of the assigned-to object is generally unpredictable. Inspecting it has dubious value.

Conclusion

The only usage difference between the Lenexa variant and the ideal variant is in how to accomplish strange, esoteric feats in assignment throw recovery code. This leads me to the conclusion that the Lenexa variant stands out as the best of all the alternatives proposed thus far for C++ developers as a whole.

Acknowledgements

A special thanks to Eric Niebler for encouraging me to make this post and for his invaluable feedback. Also thanks to Axel Naumann for his proposal and the others on the committee for the excellent discussion on what the best std::variant should look like.


  1. Note that one implementation of variant, Boost.Variant, has been around and widely used for many years. 
  2. The exact wording was taken from the Wikipedia article on exception safety
  3. The Lenexa paper, strictly speaking, doesn’t allow variants in the invalid state to be copied. According to the author, this was an unintentional bug in the paper. 
  4. Eric Niebler pointed out that we can get the desired guarentee without restricting the alternative types using the ideal variant but none of the others. In this case the code would be as follows:


Tags: ,

Comments are closed here.