Variant

[DeadMG]

Are there any existing std::variant proposals? If not, we need to get cracking on one.

[Ville Voutilainen]

On 24 April 2013 19:02, DeadMG <wolfei...@gmail.com> wrote:

Are there any existing std::variant proposals? If not, we need to get cracking on one.

Axel Naumann is going to write one. I intend to help him with it. The realistic target is C++17,

the door on C++14 is closed.

[Fernando Cacciola]

Fantastic news.!

Best

[Andrzej Krzemieński]

Axel Naumann is going to write one. I intend to help him with it. The realistic target is C++17,

the door on C++14 is closed.

Perhaps it is too early, but I can't help bringing this up already. It looks to me that std::variant will require some compiler magic support in order to provide the Never-Empty gurantee. It is essential part of variant, but difficult to achieve. Boost.Variant provides it at the expense of heap memory allocation in copy-assignment. I guess the expectation for std::variant would be that no such heap allocation takes place.

Regards,
&rzej

[Nicol Bolas]

Boost.Variant provides the Never-Empty Guarantee without heap allocation, provided that one of your types has a nothrow default constructor. In which case, in the event of a copy failure, the variant will be assigned one of those values.

I don't see the need to impose direct compiler support, just to provide a no-heap guarantee for variants that can't otherwise get one.

[Nevin Liber]

On 25 April 2013 01:18, Andrzej Krzemieński <akrz...@gmail.com> wrote:

Perhaps it is too early, but I can't help bringing this up already. It looks to me that std::variant will require some compiler magic support in order to provide the Never-Empty gurantee.

What magic support would that be?  I'm not seeing it (but it's still early in the morning :-)).

--
 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com>  (847) 691-1404

[Nevin Liber]

On 25 April 2013 02:13, Nicol Bolas <jmck...@gmail.com> wrote:

Boost.Variant provides the Never-Empty Guarantee without heap allocation, provided that one of your types has a nothrow default constructor. In which case, in the event of a copy failure, the variant will be assigned one of those values.

Sure, and we wouldn't preclude that optimization.  However, if you want that for a type that has a non-throwing default constructor marked noexcept(false) (such as, for instance, a typical implementation of std::vector), you will need magic compiler support.
 

I don't see the need to impose direct compiler support, just to provide a no-heap guarantee for variants that can't otherwise get one.

Note:  a heap allocation is not the only way to get this guarantee.  One could have a variant that has room for two copies of the largest object type, and an implementation may want to make a tradeoff between doing this and doing a heap allocation, depending on the size.

[Andrzej Krzemieński]

W dniu czwartek, 25 kwietnia 2013 16:22:22 UTC+2 użytkownik Nevin ":-)" Liber napisał:

On 25 April 2013 01:18, Andrzej Krzemieński <akrz...@gmail.com> wrote:

Perhaps it is too early, but I can't help bringing this up already. It looks to me that std::variant will require some compiler magic support in order to provide the Never-Empty gurantee.

What magic support would that be?  I'm not seeing it (but it's still early in the morning :-)).

The original implementation in Boost used tricks to implement it without the necessity of free store or double storage. It used memcpy to move the stack-allocated part of the object around. It is described in short in the docs http://www.boost.org/doc/libs/1_53_0/doc/html/variant/design.html#variant.design.never-empty.memcpy-solution.: "move the bits for an existing object into a buffer so we can tentatively construct a new object in that memory, and later move the old bits back temporarily to destroy the old object" While it did work on certain compilers, it was exploiting a UB.

But since it did work on some compilers, this makes me believe that it is implementable at least on certain compilers (UB in the standard may be a well defined behaviour on a particular platform). Every vendor could exploit their own tricks inside the implementation.

Sorry if my reply is vague. I only read about this implementation in Boost archives, and never explored it myself.

Regards,
&rzej

[Fernando Cacciola]

On Thu, Apr 25, 2013 at 12:25 PM, Andrzej Krzemieński <akrz...@gmail.com> wrote:

But since it did work on some compilers, this makes me believe that it is implementable at least on certain compilers (UB in the standard may be a well defined behaviour on a particular platform). Every vendor could exploit their own tricks inside the implementation.

 

I'm almost positive that I seem to recall that, when this was being added to Boost, we regarded the trick as unspecified instead of UB

At the very least, I can't off the top of my head think of a reason for this trick (copy to a different storage then restore it) be anything but unspecified.

And even if it is currently UB, it might be reasonable to change that, similarly to what we did for aligned_storage (which before being added to the std, all actual implementations exploited UB)

Best

--
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com

[Jonathan Wakely]

On Thursday, April 25, 2013 4:36:36 PM UTC+1, Fernando Cacciola wrote:

On Thu, Apr 25, 2013 at 12:25 PM, Andrzej Krzemieński <akrz...@gmail.com> wrote:

But since it did work on some compilers, this makes me believe that it is implementable at least on certain compilers (UB in the standard may be a well defined behaviour on a particular platform). Every vendor could exploit their own tricks inside the implementation.

 

I'm almost positive that I seem to recall that, when this was being added to Boost, we regarded the trick as unspecified instead of UB

[basic.types]/2 says it works for trivially copyable types, which implies it doesn't otherwise, or it wouldn't need saying.

 

At the very least, I can't off the top of my head think of a reason for this trick (copy to a different storage then restore it) be anything but unspecified.

If an object has a non-trivial destructor you cannot reuse its storage without running the destructor.

What if the object to be replaced had started a new thread which sets a timer and calls a member function on the object if it hasn't been destroyed yet. Since you haven't run its destructor (just moved its bytes to new storage) the other thread will do the callback, but might find garbage where it expects to find the object.



 

And even if it is currently UB, it might be reasonable to change that, similarly to what we did for aligned_storage (which before being added to the std, all actual implementations exploited UB)

Why was it UB?

[DeadMG]

I can't help but feel that this won't be necessary for a C++11 Variant. Surely, you could implement the copy assignment operator in terms of copy and swap, like normal. Since swap can now be guaranteed noexcept with move semantics, it seems to me like this should be a fine implementation strategy for strongly exception safe no double storage no heap allocation copy assignment.

[Daniel Krügler]

2013/4/25 DeadMG <wolfei...@gmail.com>:

Why should swap guarantee noexcept? Not every type has move operations
(it will copy instead), not every move operation is noexcept (The
library supports throwing move operations but gives up the strong
exception safety).

- Daniel

[Nevin Liber]

On 25 April 2013 15:13, DeadMG <wolfei...@gmail.com> wrote:

Surely, you could implement the copy assignment operator in terms of copy and swap, like normal.

Could you?  There aren't any "internals" to swap (it's value based, not pointer based), so wouldn't this just be a pessimization?

 

Since swap can now be guaranteed noexcept with move semantics,

Huh?  Where does this come from?  Unless the move constructor/move assignment are marked noexcept, this isn't true.

 

it seems to me like this should be a fine implementation strategy for strongly exception safe no double storage no heap allocation copy assignment.

I don't see how you can avoid it if you want never-empty for arbitrary types.

-- 

[DeadMG]

Frankly, I think that requiring nothrow move would be a superior option. It considerably simplifies the implementation, improves performance, and does not have the requirement of needing a nothrow default constructible type to put in the variant in case of failure. In my opinion, losing the strong exception safety guarantee is something we should only do if we have absolutely no other choice. In this case, we do have a choice.

[Nevin Liber]

On 25 April 2013 15:28, DeadMG <wolfei...@gmail.com> wrote:

Frankly, I think that requiring nothrow move would be a superior option. It considerably simplifies the implementation, improves performance, and does not have the requirement of needing a nothrow default constructible type to put in the variant in case of failure.

You've just swapped one unreasonable (IMO) requirement on the type for another.  You couldn't, for instance, store most of the standard containers in your variant.  I would vote strongly against this.

In my opinion, losing the strong exception safety guarantee is something we should only do if we have absolutely no other choice. In this case, we do have a choice.

 Requiring no-throw move constructors for various standard library components has been tried before.  It didn't work.

[Jeffrey Yasskin]

The implementation can distinguish a couple cases then:

a) At least one member of the variant has a noexcept(true) default constructor.
b) At most one member of the variant has a noexcept(false) move constructor.
c) The variant is either twice the size or allocates on some assignments.

Right? (b) is new with C++11, and the proposal should definitely
include it. Maybe we can get the allocator crowd not to insist on
allocators by telling them to fit in (a) or (b) if they want to
control allocation. I don't have a good feeling for whether
std::variant should forbid (c) entirely, or allow it with
allocation-or-double-memory.

To forbid (c), we'd probably have to give the standard containers
noexcept move constructors. ... Are they missing the noexcept today
because of allocators?

Jeffrey

[Daniel Krügler]

2013/4/25 Jeffrey Yasskin <jyas...@google.com>:

No, I don't think so. We require that the move construction of
allocators is no-throw. I believe the reason here is the same as we
have for not having guaranteed no-throw container default
constructors, because implementations might need to allocate memory
for internal purposes that could fail.

- Daniel

[DeadMG]

Then the real problem here is the lack of support for noexcept allocators.

[Fernando Cacciola]

On Thu, Apr 25, 2013 at 1:57 PM, Jonathan Wakely <c...@kayari.org> wrote:

On Thursday, April 25, 2013 4:36:36 PM UTC+1, Fernando Cacciola wrote:

On Thu, Apr 25, 2013 at 12:25 PM, Andrzej Krzemieński <akrz...@gmail.com> wrote:

But since it did work on some compilers, this makes me believe that it is implementable at least on certain compilers (UB in the standard may be a well defined behaviour on a particular platform). Every vendor could exploit their own tricks inside the implementation.

 

I'm almost positive that I seem to recall that, when this was being added to Boost, we regarded the trick as unspecified instead of UB

[basic.types]/2 says it works for trivially copyable types, which implies it doesn't otherwise, or it wouldn't need saying.

Good point.
 

 

At the very least, I can't off the top of my head think of a reason for this trick (copy to a different storage then restore it) be anything but unspecified.

If an object has a non-trivial destructor you cannot reuse its storage without running the destructor.

Right, I would have replied than in this case you are giving it the storage back, but...

What if the object to be replaced had started a new thread which sets a timer and calls a member function on the object if it hasn't been destroyed yet. Since you haven't run its destructor (just moved its bytes to new storage) the other thread will do the callback, but might find garbage where it expects to find the object.

This is quite valid, even if odd and unlikely, so that settles it.

 

And even if it is currently UB, it might be reasonable to change that, similarly to what we did for aligned_storage (which before being added to the std, all actual implementations exploited UB)

Why was it UB?

I've been trying to remember but I can't. And there is alignment_of plus type_with_alignment in the bag, so I might be confusing them.

[Daniel Krügler]

2013/4/25 DeadMG <wolfei...@gmail.com>:

> Then the real problem here is the lack of support for noexcept allocators.

I assume you mean kind-of-nothrow_t allocate overload in allocators?
This should not be the actual problem, since an implementation could
easily realize the same thing by *attempting* to call Alloc::allocate
within a try/catch block. Essentially the default operator new
overload with std::nothrow_t argument behaves in the same way: It
tries to call the potentially throwing operator new and returns null,
if that throws an exception. The actual problem is that some
implementations *need* this storage and could not be created if that
memory would not exist.

- Daniel

[DeadMG]

No, I mean "If allocation fails, std::terminate()".

[Daniel Krügler]

2013/4/25 DeadMG <wolfei...@gmail.com>:

> No, I mean "If allocation fails, std::terminate()".

A drastic solution IMO. I would prefer that implementations would
instead provide the nothrow-guarantee for default-construction of
potentially zero-capacity containers.

- Daniel

[DeadMG]

I feel that it's the best solution, since the situation that many applications are in is that if they exhaust memory, then this effectively will only occur due to a memory leak. An exception is of little use.

Let me put it another way. In my program, then there is no way I am going to exhaust my 2GB virtual memory limit. But you're saying that I have to pay the price of no strong exception guarantee and having to screw around with default constructible types, because *some other program* would prefer to have an exception on memory allocation failure. This is fundamentally against the C++ philosophy IYAM, but more importantly, plain unnecessary- we have a perfectly good tool to solve this problem and there's no reason not to use it if possible. Let those programs who want memory allocation failures to be exceptions cope with the problem of exception safety when memory allocation might throw.

[Daniel Krügler]

2013/4/25 DeadMG <wolfei...@gmail.com>:

What you are describing here sounds to me like the moral equivalent of
an enforced new-handler that calls std::terminate. If you prefer it
that way, install such a beast, but this is an optional decision and
not what everyone likes to have.

- Daniel

[DeadMG]

I'm not saying it should be enforced. I'm saying that *if* I install an allocator (not a new-handler since that cannot influence exception guarantees) which behaves this way, then the Standard should specify the noexcepts to take advantage of this.

[Nevin Liber]

On 25 April 2013 15:46, Jeffrey Yasskin <jyas...@google.com> wrote:

The implementation can distinguish a couple cases then:

a) At least one member of the variant has a noexcept(true) default constructor.
b) At most one member of the variant has a noexcept(false) move constructor.
c) The variant is either twice the size or allocates on some assignments.

You can also do some optimizations if you have a nonexcept copy constructor when you are doing copy assignment. 

 

 I don't have a good feeling for whether

std::variant should forbid (c) entirely, or allow it with
allocation-or-double-memory.

That is, of course, the crux of the never-empty vs. at-most-one guarantee. :-)

 

To forbid (c), we'd probably have to give the standard containers
noexcept move constructors.

That is probably a non-starter.

[Nevin Liber]

On 25 April 2013 16:36, DeadMG <wolfei...@gmail.com> wrote:

I'm not saying it should be enforced. I'm saying that *if* I install an allocator (not a new-handler since that cannot influence exception guarantees) which behaves this way, then the Standard should specify the noexcepts to take advantage of this.

Then write a proposal (or at least start a new thread, since this has nothing to do with the variant proposal).

-- 

[DeadMG]

Yes, I have totally spammed the wrong thread. My apologies.

[Nevin Liber]

On 25 April 2013 16:36, Nevin Liber <ne...@eviloverlord.com> wrote:

On 25 April 2013 15:46, Jeffrey Yasskin <jyas...@google.com> wrote:

The implementation can distinguish a couple cases then:

a) At least one member of the variant has a noexcept(true) default constructor.
b) At most one member of the variant has a noexcept(false) move constructor.
c) The variant is either twice the size or allocates on some assignments.

You can also do some optimizations if you have a nonexcept copy constructor when you are doing copy assignment. 

Here is what I am thinking:

Move assignment of distinct types:

    If we have a noexcept move constructor or at least one noexcept default constructor:

        Destroy old object

        Move construct new object

    Otherwise

        Move construct new object into alternate space

        Destroy old object

Copy assignment of distinct types:

    If we have a noexcept copy constructor or at least one noexcept default constructor:

        Destroy old object

        Copy construct new object

    Else if we have a noexcept(false) copy constructor, no noexcept default constructors, and a noexcept move constructor:

        Copy construct new object on the stack

        Destroy old object

        Move construct new object from the stack into the variant

    Otherwise either do what Boost.Variant does OR:

        Copy construct new object into alternate space

        Destroy old object

I *think* that covers all the cases.

-- 

[Alex B]

Before trying to solve the never-empty guarantee problem, I think we should examine the design of the variant class.

 

The design of boost::variant has the following particularity: "By default, a variant default-constructs its first bounded type"

 

I never felt comfortable with that part of the design of boost::variant. It always felt odd to me that the order of the bounded types matter. In my opinion, a default constructed variant should not have one of its types selected by default. In my personal implementation of a variant class, there is what I call a "null" or "disengaged" or "no type" state. If we think of a variant as being an index representing the selected type along with an aligned storage large enough to hold any of the types of the variant, there would be no extra cost of adding a null state. It could simply be represented by a special index (let's say -1).

 

template <class... Types>

class variant

{

   int selected_type; // value is an index among Types... or -1 if no selected type

   std::aligned_storage<MaxLen, MaxAlign> data;

   ...

 

There could be a nullvar value that would represent a variant with no type selected (similar to nullopt that is part of the std::optional proposal). For this and a few other things, the variant class would benefit from having a design inspired in part by std::optional.

 

Why am I bringing this? Because if there is a null state, then the "never empty" problem becomes much simpler. In fact, the problem could then be called "never empty when not nullvar". The copy assignment of distinct types could simply be:

- Destroy old object

- Set selected type as nullvar (could be omitted if copy constructor is noexcept)

- Copy construct new object

- Set selected type as new type

 

If the copy constructor throws, the variant remains in a nullvar state, which is a valid state.

 

So, do you think of any problem of having this nullvar state? Maybe there was a reason for not including one in boost::variant but I can't see one apart from being a design choice.

[Nicol Bolas]

On Monday, April 29, 2013 8:26:56 PM UTC-7, Alex B wrote:

Before trying to solve the never-empty guarantee problem, I think we should examine the design of the variant class.

 

The design of boost::variant has the following particularity: "By default, a variant default-constructs its first bounded type"

 

I never felt comfortable with that part of the design of boost::variant. It always felt odd to me that the order of the bounded types matter. In my opinion, a default constructed variant should not have one of its types selected by default. In my personal implementation of a variant class, there is what I call a "null" or "disengaged" or "no type" state. If we think of a variant as being an index representing the selected type along with an aligned storage large enough to hold any of the types of the variant, there would be no extra cost of adding a null state. It could simply be represented by a special index (let's say -1).

 

template <class... Types>

class variant

{

   int selected_type; // value is an index among Types... or -1 if no selected type

   std::aligned_storage<MaxLen, MaxAlign> data;

   ...

 

There could be a nullvar value that would represent a variant with no type selected (similar to nullopt that is part of the std::optional proposal). For this and a few other things, the variant class would benefit from having a design inspired in part by std::optional.

 

Why am I bringing this? Because if there is a null state, then the "never empty" problem becomes much simpler.

No it doesn't. OK, it does, but only because you're using wordplay to redefine the problem away.

You can not have a "never empty" guarantee if the variant can be empty. You're basically deciding that variants will have an empty state, and therefore the user will have to deal with the possibility of a variant being in the empty state. But we're not going to actually call it "empty"; we'll call it "nullvar".

I fail to see how "nullvar" is in any way different from being "empty". You still need to define what it means to use a visitor on a "nullvar" variant. Does it throw an exception? Does it simply fail to call any visitation function? Does the user get to have a particular operator() overload that is called on the "nullvar" state? If the latter is true, does every visitor class now have to have this overload?

In fact, the problem could then be called "never empty when not nullvar". The copy assignment of distinct types could simply be:

- Destroy old object

- Set selected type as nullvar (could be omitted if copy constructor is noexcept)

- Copy construct new object

- Set selected type as new type

 

If the copy constructor throws, the variant remains in a nullvar state, which is a valid state.

 

So, do you think of any problem of having this nullvar state? Maybe there was a reason for not including one in boost::variant but I can't see one apart from being a design choice.

The reason not to do this is the same reason to not have a variant that can be empty at all: every user will have to account for the possibility of using an empty variant, even if they do not want to.

With the actual "never empty" guarantee, you can still have an empty variant. Indeed, you can have almost exactly the same "nullvar" semantics you propose. Just make the first element in the variant `boost::blank`. A default-constructed variant will be of type `blank`. A variant that fails copy construction will be of type `blank`. Boost::variant guarantees this.

This also neatly answers all of those questions I asked earlier about visitation. Since it's an explicit element in the list, you must account for that possibility in your visitors. Which is good.

In the Boost design, a user who doesn't want the "never empty" guarantee doesn't have to pay for it (the presence of `blank` prevents the more expensive copy operation). And a user who does want the "never empty" guarantee, and doesn't want to deal with a "nullvar" state in all of their visitors, will simply not use `blank`.

Everyone wins with the Boost design. So why should we use an implicit "empty" state when those who want to have an empty state can use an explicit one?

Pay only for what you use.

[Nevin Liber]

On 29 April 2013 23:42, Nicol Bolas <jmck...@gmail.com> wrote:

No it doesn't. OK, it does, but only because you're using wordplay to redefine the problem away.

Yes, Alex basically describes at-most-one semantics.

 

In the Boost design, a user who doesn't want the "never empty" guarantee doesn't have to pay for it (the presence of `blank` prevents the more expensive copy operation). And a user who does want the "never empty" guarantee, and doesn't want to deal with a "nullvar" state in all of their visitors, will simply not use `blank`.

Everyone wins with the Boost design.

*Experts* win in the Boost design.  It is not obvious to non-experts that variant<vector<char>, string> will have some copy/move operations that are significantly slower than expected (given that the *only* constructor required to be marked noexcept is the string move constructor).  And, unlike Boost.Variant, we cannot specialize the std type_traits, so there is no choice but to use std::nullopt (or equivalent), which is intrusive in that the user's visitor *must* take it into account.  Even if we invented our own type traits just for variant, you still could only specialize them for non-Standard user defined types, which doesn't apply in the case above.  In addition, the Boost solution makes the tradeoff of speed over keeping things in the heap (ie, makes yet another copy), so you still don't get full control over what happens.  And no one has yet addressed the allocator issue, which I'm pretty sure we'll have to if it can allocate memory and we want the proposal to succeed.

Seriously, the number one question I've been asked about variant at my last two jobs is am I sure that a particular instantiation of variant avoids this performance penalty.

 

So why should we use an implicit "empty" state when those who want to have an empty state can use an explicit one?

To not penalize non-experts for using it.  Like I said, in order to not dictate implementation, I can't see the exception safety guarantee being any more than "on an exception being thrown, the object is left as an unspecified instance of one of the types", and in practice, I don't find such an unknown state as being useful, but I'm certainly willing to be persuaded by others that it is.

[Nicol Bolas]

On Tuesday, April 30, 2013 12:47:35 AM UTC-7, Nevin ":-)" Liber wrote:

On 29 April 2013 23:42, Nicol Bolas <jmck...@gmail.com> wrote:

No it doesn't. OK, it does, but only because you're using wordplay to redefine the problem away.

Yes, Alex basically describes at-most-one semantics.

 

In the Boost design, a user who doesn't want the "never empty" guarantee doesn't have to pay for it (the presence of `blank` prevents the more expensive copy operation). And a user who does want the "never empty" guarantee, and doesn't want to deal with a "nullvar" state in all of their visitors, will simply not use `blank`.

Everyone wins with the Boost design.

*Experts* win in the Boost design.  It is not obvious to non-experts that variant<vector<char>, string> will have some copy/move operations that are significantly slower than expected (given that the *only* constructor required to be marked noexcept is the string move constructor).  And, unlike Boost.Variant, we cannot specialize the std type_traits, so there is no choice but to use std::nullopt (or equivalent), which is intrusive in that the user's visitor *must* take it into account.  Even if we invented our own type traits just for variant, you still could only specialize them for non-Standard user defined types, which doesn't apply in the case above.  In addition, the Boost solution makes the tradeoff of speed over keeping things in the heap (ie, makes yet another copy), so you still don't get full control over what happens.  And no one has yet addressed the allocator issue, which I'm pretty sure we'll have to if it can allocate memory and we want the proposal to succeed.

Seriously, the number one question I've been asked about variant at my last two jobs is am I sure that a particular instantiation of variant avoids this performance penalty.

OK, so how do we do it in a non-expert friendly way that doesn't penalize experts? If you force the variant to have an empty state (and thus force users to do something with a possibly empty state), then there's no way to have a variant that doesn't have an empty state. Which means people have to be forced into checking conditions that they don't need to (the state of being empty is something every visitor should have to account for).

So why should we use an implicit "empty" state when those who want to have an empty state can use an explicit one?

To not penalize non-experts for using it.  Like I said, in order to not dictate implementation, I can't see the exception safety guarantee being any more than "on an exception being thrown, the object is left as an unspecified instance of one of the types", and in practice, I don't find such an unknown state as being useful, but I'm certainly willing to be persuaded by others that it is.

I don't understand why it is that we can't specify what state it will be in. What freedom are you allowing implementations if you do this? You're saying a variant must contain an instance of a type. So you still want to enforce the never-empty guarantee, and therefore the copying penalty that comes along with it. But you don't want the back-door that Boost put into their class that allows you to avoid that penalty.

So what exactly is it that you want: a variant that will always have an empty state? Or a variant that can never have an empty state? I prefer giving the programmer the choice of an empty variant: a variant that can either be empty or not empty, as the user sees fit by adding a class to the variant's parameter list.

That's what's nice about the Boost version: if you want a known state after a copy exception, you can get that. So you can define your variant such that it never is in "such an unknown state". You just have to pay a cost for it by defining a specific member of the variant.

Why do you want to penalize experts (taking away their choices) without doing anything to make the class non-expert friendly?

[Alex B]

You still need to define what it means to use a visitor on a "nullvar" variant.

Fair enough.

Does it throw an exception? Does it simply fail to call any visitation function? Does the user get to have a particular operator() overload that is called on the "nullvar" state? If the latter is true, does every visitor class now have to have this overload?

How about throwing if the variant is in a nullvar state and the visitor doesn't provide a nullvar overload? That way, if you are sure that your variant is not nullvar, don't provide a nullvar overload. Otherwise, 2 choices: provide an overload or surround your call to apply visitor by a try-catch.

As I understand it, the problem that you are raising is that you don't want to penalize the user by forcing him to implement an overload taking a nullvar_t in every of his visitors. As I said, I would not force him to do so (but it would be an option).

I would push it even further. I would not force visitors to provide overloads for all of the types. If visitor::operator() cannot be called for the current type of the variant, then just throw. Let's say that your variant contains 10 types. You *know* that in a specific context, the variant type should be one of only 3 of these types. So why not allow the implementer of the visitor to only provide overloads for the 3 types that he expect? Just throw if the provided overloads cannot accept the current type of the variant (including nullvar_t).

Pay only for what you use.

I couldn't agree more.

Notice that I am not going into the details of how it should be implemented but rather on the intent and high level design of the class that will influence how the user will use it. For instance, I am not sure yet how the class will be able to determine if the visitor is providing a specific overload (maybe it will require some compiler support or maybe that sentence should be rephrased -- what I care for now is the intent).

Final note about the "expert"/"non-expert" argument.

I can't seem to see how it would benefit "experts" to have the variant copy constructed to the original type (from/to alternate space) if a copy/move assignment fails. If the assignment fails, I might not need to use the variant anymore. So that copy that was made to/from alternate space would just be a waste. I personally think that an expert will want control over this; copying back to the original type seems an arbitrary choice to me. But we don't have to agree on this if you agree on what I first suggest...

[Nicol Bolas]

On Wednesday, May 1, 2013 4:43:13 AM UTC-7, Alex B wrote:

Does it throw an exception? Does it simply fail to call any visitation function? Does the user get to have a particular operator() overload that is called on the "nullvar" state? If the latter is true, does every visitor class now have to have this overload?

How about throwing if the variant is in a nullvar state and the visitor doesn't provide a nullvar overload? That way, if you are sure that your variant is not nullvar, don't provide a nullvar overload. Otherwise, 2 choices: provide an overload or surround your call to apply visitor by a try-catch.

As I understand it, the problem that you are raising is that you don't want to penalize the user by forcing him to implement an overload taking a nullvar_t in every of his visitors. As I said, I would not force him to do so (but it would be an option).

I would push it even further. I would not force visitors to provide overloads for all of the types. If visitor::operator() cannot be called for the current type of the variant, then just throw. Let's say that your variant contains 10 types. You *know* that in a specific context, the variant type should be one of only 3 of these types. So why not allow the implementer of the visitor to only provide overloads for the 3 types that he expect? Just throw if the provided overloads cannot accept the current type of the variant (including nullvar_t).

There's a good reason not to do that. One of the nice things about variants are that if you add new elements, you get a compiler error in every piece of code where you forgot handle the new element. Not a runtime error that you may or may not ever hit, a compile-time error that you can't ignore.

Furthermore, if a user knows that it's only in one of three states, it's very easy for them to handle the rest with a: `template<typename T> operator()(const T&) {}` overload. They could even `throw` if they want to. It also happens to make it clear that it's not a mistake for it to not handle the other alternatives; you're explicitly saying that you're doing nothing for them.

The Boost.Variant way, the user has choices: do they want the compiler error or a runtime error? I'd rather those choices be apparent and within the visitor class itself, rather than having different visitation functions or whatever.

To allow a visitation function to throw based on the state of the variant goes against a significant part of the point of using variants rather than something else.

Indeed, this is why I would even say that, if you're going to allow variants to be empty, you should therefore require all users to actually handle the empty state. And that's why I prefer the never-empty guarantee; that way, I get to decide if I want a variant to possibly be empty, and therefore I get to decide whether I want to test for emptiness.

Remember: saying that you throw on an empty variant isn't really much better. That means it is possible to get an empty variant. I would much rather make it my choice whether it is possible for a variant to ever be empty. I really don't like the idea of visitation functions that throw exceptions internally.

Pay only for what you use.

I couldn't agree more.

Notice that I am not going into the details of how it should be implemented but rather on the intent and high level design of the class that will influence how the user will use it. For instance, I am not sure yet how the class will be able to determine if the visitor is providing a specific overload (maybe it will require some compiler support or maybe that sentence should be rephrased -- what I care for now is the intent).

But you can't separate implementation from intent. It's going to have to be implemented at some point, in real systems. And, unless you intend to stick `variant` in Chapter 17, it's not reasonable to define the requirements such that an implementation would have to rely on compiler-specific intrinsics. Most standard library stuff does not, and that's a good thing. People ought to be able to drop in their own version of the standard library and use it effectively, outside of a select few objects which are intrinsic to C++.

A specification which cannot be implemented reasonably isn't terribly useful. That's why the committee likes to standardize existing practice, or at least proven practice from a proof-of-concept implementation.

Boost.Variant is already existing practice. If you're going to suggest significant changes, you should prove those changes with an implementation that works and is better in some respect.

Final note about the "expert"/"non-expert" argument.

I can't seem to see how it would benefit "experts" to have the variant copy constructed to the original type (from/to alternate space) if a copy/move assignment fails. If the assignment fails, I might not need to use the variant anymore. So that copy that was made to/from alternate space would just be a waste.

Then again, they might need it. We don't throw away exception safety just because someone might not use the object.

I personally think that an expert will want control over this; copying back to the original type seems an arbitrary choice to me. But we don't have to agree on this if you agree on what I first suggest...

But what you suggest breaks the never-empty guarantee.

[Alex B]

I see a lot to be discussed here (sorry for the long post).

 

There's a good reason not to do that. One of the nice things about variants are that if you add new elements, you get a compiler error in every piece of code where you forgot handle the new element. Not a runtime error that you may or may not ever hit, a compile-time error that you can't ignore.

Ok.

Furthermore, if a user knows that it's only in one of three states, it's very easy for them to handle the rest with a: `template<typename T> operator()(const T&) {}` overload. They could even `throw` if they want to. It also happens to make it clear that it's not a mistake for it to not handle the other alternatives; you're explicitlysaying that you're doing nothing for them.

There has to be a better way than having to redefine the same templated overload all the time to handle the rest.

Let's forget about the nullvar/empty/blank state (for now).

Imagine that instead of the boost::static_visitor class (that visitors have to derrive form), there would be a std::variant::visitor class (nested). That class would take variadic template parameters that would represent all the types from the variant that need to be supported by the visitor (and those types need to be part of the variant). It will be easier to illustrate this idea with some code (please don't take the design and names chosen for granted; they are only provided to illustrate the intent):

template <class... Types>
class variant
{

 // [...]
public:
 template <class V, class... VTypes>
 struct visitor
 {
 // Compile error if VTypes are not part of Types
 // [...]
 };

 template <class V>
 using complete_visitor = visitor<V, Types...>; // There might be a better name for this

 template <class V, class... VTypes>
 void apply_visitor(const visitor<V, VTypes...>& v)
 {
 // Throw if the current type of the variant is not among VTypes
 };

 // [...]
};

using MyVariantType = variant<int, float, string, vector<int>, list<float>>;
struct MyCompleteVisitor : MyVariantType::complete_visitor
{
 void operator()(int& i) const {}
 void operator()(float& f) const {}
 void operator()(string& s) const {}
 void operator()(vector<int>& v) const {}
 void operator()(list<float>& l) const {}

 // If one of the types in MyVariantType changes or a new one is added,
 // this visitor won't compile unless it is modified accordingly
};
struct MyVisitor : MyVariantType::visitor<float, string>
{
 void operator()(float& f) const {} // Would not compile without this overload
 void operator()(string& s) const {} // Would not compile without this overload

 // Other overloads are not specified, so if the variant is of type int,
 // vector<int> or list<float>, this visitor would throw when being applied
};

MyVariantType v{0}; // variant constructed as int
v.apply_visitor(MyCompleteVisitor{}); // does not throw
v.apply_visitor(MyVisitor{}); // throws
v = 0.0f;
v.apply_visitor(MyVisitor{}); // does not throw

So Boost users would get the same compile-time safety if they make their visitors derive from std::variant<...>::complete_visitor instead of boost::static_visitor.

For users who only care about some of the types, they would now have the choice to only supply overloads for the types they care about.

Everybody wins.

Now how could we integrate nullvar in those visitors? That is another question, but I'm sure it could be done. For example, just accept nullvar_t as one of the types of variant::visitor to force the visitor to define an overload taking a nullvar. Then we could have this defined in the variant class:

 template <class V>
 using complete_visitor_with_nullvar = visitor<V, nullvar_t, Types...>; // For sure we can find a better name for this...

But you can't separate implementation from intent. It's going to have to be implemented at some point, in real systems. And, unless you intend to stick `variant` in Chapter 17, it's not reasonable to define the requirements such that an implementation would have to rely on compiler-specific intrinsics. Most standard library stuff does not, and that's a good thing. People ought to be able to drop in their own version of the standard library and use it effectively, outside of a select few objects which are intrinsic to C++.

A specification which cannot be implemented reasonably isn't terribly useful. That's why the committee likes to standardize existing practice, or at least provenpractice from a proof-of-concept implementation.

Boost.Variant is already existing practice. If you're going to suggest significant changes, you should prove those changes with an implementation that works and is better in some respect.

Do you really expect everyone here to bring an implementation to be able to discuss?

Please remember that we are in a discussion forum. When I (and others) throw out some ideas like this, I don't have a full proposal and all the possible proofs in my hands right now and I think that is what should be expected. If you only care about fully elaborated proposals and papers, then you should skip this kind of thread. (but it would be sad because you are bringing some valid concerns and clarifications about the ideas being thrown)

Then again, they might need it.

How would I do it if I don't need it? Because the guarantee has a cost and for performance I want to be able to avoid it. Ok, I could add boost::blank as the first of my variant types. The thing is that it is not possible to modify the variant declaration. Let's say there is a function in a library taking a ref to a variant with specific types as a parameter (but these types do not include boost::blank). Now I want to implement that library function and inside of it I do a copy assignment from another variant and I want to avoid the guarantee because I want it to be optimal. It would not make sense to have to modify the library interface (adding boost::blank as one of the types of the variant passed as a ref parameter) just to accommodate the implementer.

We don't throw away exception safety just because someone might not use the object.

What do you mean exactly? Do you mean that you consider the nullvar state to be unsafe? It would be a fully valid state (just like nullopt is a valid state for optional).

But what you suggest breaks the never-empty guarantee.

Indeed, that's what I wish: to break that guarantee. For many reasons. There might be some good reasons for this guarantee, but you cannot say that it doesn't have its drawbacks. Personally (and many others), I find it to be more trouble than anything so that's why we shouldn't take it for granted.

[Nicol Bolas]

Not really. The common case for a variant is to check all of the possibilities. That is, the common case is that it is user error to miss checking one of the elements. The way you're proposing means that I have to expend a lot of effort in order to handle that common case.

Plus, it inextricably links the visitor to the variant that uses it. Is that dependency necessary? Why does the visitation code need to have the variant definition? It also means that it's much more difficult to use a visitor with different variant types. Is there a reason that this should be so difficult to handle?

This is a lot to give up just to avoid writing a quick template operator() if you don't want to handle all of the cases.

Also, there is a simpler way than redefining the template operator(), if you're really lazy:

template<typename Ret>struct no_error_visitor : public boost:static_visitor<Ret>
{
  template<typename T> Ret operator() (const T &) {return Ret();}
};

template<> struct no_error_visitor<void> : public boost::static_visitor<>
{
  template<typename T> void operator() {const T&) {}
};

Derive all of your visitors from that. See? Problem solved. You can even make a throwing one.

The default case should push errors as close to compile-time as possible. If the user wants to say that they want runtime errors, or just to transparently handle everything else, they have the tools to do that easily. But by default, we should require the user to write proper, fully-qualified visitors.


 

Now how could we integrate nullvar in those visitors? That is another question, but I'm sure it could be done. For example, just accept nullvar_t as one of the types of variant::visitor to force the visitor to define an overload taking a nullvar. Then we could have this defined in the variant class:

 template <class V>
 using complete_visitor_with_nullvar = visitor<V, nullvar_t, Types...>; // For sure we can find a better name for this...

But you can't separate implementation from intent. It's going to have to be implemented at some point, in real systems. And, unless you intend to stick `variant` in Chapter 17, it's not reasonable to define the requirements such that an implementation would have to rely on compiler-specific intrinsics. Most standard library stuff does not, and that's a good thing. People ought to be able to drop in their own version of the standard library and use it effectively, outside of a select few objects which are intrinsic to C++.
A specification which cannot be implemented reasonably isn't terribly useful. That's why the committee likes to standardize existing practice, or at least provenpractice from a proof-of-concept implementation.
Boost.Variant is already existing practice. If you're going to suggest significant changes, you should prove those changes with an implementation that works and is better in some respect.

Do you really expect everyone here to bring an implementation to be able to discuss?

No, but if you're going to argue against the Boost version, it wouldn't hurt. You're basically saying, "I want X and we'll figure out how to implement it later." That's fine and all, but what good is wanting it if it can't be done?

Please remember that we are in a discussion forum. When I (and others) throw out some ideas like this, I don't have a full proposal and all the possible proofs in my hands right now and I think that is what should be expected. If you only care about fully elaborated proposals and papers, then you should skip this kind of thread. (but it would be sad because you are bringing some valid concerns and clarifications about the ideas being thrown)

But what you suggest breaks the never-empty guarantee.

Indeed, that's what I wish: to break that guarantee. For many reasons. There might be some good reasons for this guarantee, but you cannot say that it doesn't have its drawbacks. Personally (and many others), I find it to be more trouble than anything so that's why we shouldn't take it for granted.

That's great. The wonderful thing about the Boost version is that you can avoid all of those drawbacks easily enough, just by putting an explicit "empty" state into the variant. See? The copying won't allocate memory; if a copy constructor throws, it will go to the blank state. Boost.Variant guarantees this.

So explain why everyone should be forced to handle empty variants? Boost.Variant gives you everything you ask for (except for the fact that you have to actually handle the empty case. But I consider that a good thing over throwing exceptions). So... what's the problem?

[Alex B]

Not really. The common case for a variant is to check all of the possibilities. That is, the common case is that it is user error to miss checking one of the elements. The way you're proposing means that I have to expend a lot of effort in order to handle that common case.

Yes. If you use variant::complete_visitor, you have the same error-checking as boost::static_visitor. So if that's what you want, I don't have any problem with it being your default.

Plus, it inextricably links the visitor to the variant that uses it. Is that dependency necessary? Why does the visitation code need to have the variant definition? It also means that it's much more difficult to use a visitor with different variant types. Is there a reason that this should be so difficult to handle?

I see what you mean. There might be a different way to do it that would avoid it. I think it will work if I make the visitor class not a nested class of variant (put it in namespace scope) and perform the check to verify that the visitor types are all part of the variant types on the call to apply_visitor (at compile-time). Let me think about it.

Also, there is a simpler way than redefining the template operator(), if you're really lazy:
template<typename Ret>struct no_error_visitor : public boost:static_visitor<Ret>
{
  template<typename T> Ret operator() (const T &) {return Ret();}
};
template<> struct no_error_visitor<void> : public boost::static_visitor<>
{
  template<typename T> void operator() {const T&) {}
};
Derive all of your visitors from that. See? Problem solved. You can even make a throwing one.

The problem with doing this is that it won't perform any compile-time checks; visitors will always compile because of the templated overload. With the visitor class I'm proposing, you explicitely define what types should be implemented by the visitor so that the compile-check could be done. If I have a visitor<A, B> my code will not compile if I don't provide overloads taking types A and B.

The default case should push errors as close to compile-time as possible. If the user wants to say that they want runtime errors, or just to transparently handle everything else, they have the tools to do that easily. But by default, we should require the user to write proper, fully-qualified visitors.

As I said, just use complete_visitor as your default and you will get all those compile-time checks.

That's great. The wonderful thing about the Boost version is that you can avoid all of those drawbacks easily enough, just by putting an explicit "empty" state into the variant. See? The copying won't allocate memory; if a copy constructor throws, it will go to the blank state. Boost.Variant guarantees this.
So explain why everyone should be forced to handle empty variants? Boost.Variant gives you everything you ask for (except for the fact that you have to actually handle the empty case. But I consider that a good thing over throwing exceptions). So... what's the problem?

The problem, I explained it in my previous post: most of the time it is not possible to add an explicit empty state. Let me cite what I wrote:

I could add boost::blank as the first of my variant types. The thing is that it is not possible to modify the variant declaration. Let's say there is a function in a library taking a ref to a variant with specific types as a parameter (but these types do not include boost::blank). Now I want to implement that library function and inside of it I do a copy assignment from another variant and I want to avoid the guarantee because I want it to be optimal. It would not make sense to have to modify the library interface (adding boost::blank as one of the types of the variant passed as a ref parameter) just to accommodate the implementer.

To make it shorter, it doesn't make sens to me to change the types of my variant (which could be used all over my code) just to be able, at a specific place in code, to avoid the cost of the guarantee (if I don't need it in that place in code).

[Nicol Bolas]

On Thursday, May 2, 2013 3:48:00 AM UTC-7, Alex B wrote:

Not really. The common case for a variant is to check all of the possibilities. That is, the common case is that it is user error to miss checking one of the elements. The way you're proposing means that I have to expend a lot of effort in order to handle that common case.

Yes. If you use variant::complete_visitor, you have the same error-checking as boost::static_visitor. So if that's what you want, I don't have any problem with it being your default.

Because it should be the default, not "my" default. It is the correct way to write a visitor. It fixes so many problems ahead of time. Forcing users to make it clear what their visitors will handle solves so many issues.

My question is why you don't want it to be the default. You can still get around it if you so desire, as previously outlined. But nine-times-out-of-ten, if a visitor doesn't catch all of the variant options, then the visitor is out of sync with the variant. That is almost certainly a bug.

The default should be the scenario that is least likely to create silently buggy code.

Plus, it inextricably links the visitor to the variant that uses it. Is that dependency necessary? Why does the visitation code need to have the variant definition? It also means that it's much more difficult to use a visitor with different variant types. Is there a reason that this should be so difficult to handle?

I see what you mean. There might be a different way to do it that would avoid it. I think it will work if I make the visitor class not a nested class of variant (put it in namespace scope) and perform the check to verify that the visitor types are all part of the variant types on the call to apply_visitor (at compile-time).

We already have that. It's called boost::apply_visitor. The question is what to do when there's a possible type in the variant which the visitor cannot satisfy. The Boost way lets you choose: you can use a simple template overload to decide what to do. And if you don't (ie: write the least amount of code), you can get a compiler error.

Also, there is a simpler way than redefining the template operator(), if you're really lazy:
template<typename Ret>struct no_error_visitor : public boost:static_visitor<Ret>
{
  template<typename T> Ret operator() (const T &) {return Ret();}
};
template<> struct no_error_visitor<void> : public boost::static_visitor<>
{
  template<typename T> void operator() {const T&) {}
};
Derive all of your visitors from that. See? Problem solved. You can even make a throwing one.

The problem with doing this is that it won't perform any compile-time checks; visitors will always compile because of the templated overload. With the visitor class I'm proposing, you explicitely define what types should be implemented by the visitor so that the compile-check could be done. If I have a visitor<A, B> my code will not compile if I don't provide overloads taking types A and B.

And if your Boost-based visitor doesn't implement operator() for A or B, it won't compile either. Why do we want to force people to put the types in two places instead of one? Isn't that a code smell of some sort, when a design forces you to repeat the same information in two places?

That's great. The wonderful thing about the Boost version is that you can avoid all of those drawbacks easily enough, just by putting an explicit "empty" state into the variant. See? The copying won't allocate memory; if a copy constructor throws, it will go to the blank state. Boost.Variant guarantees this.
So explain why everyone should be forced to handle empty variants? Boost.Variant gives you everything you ask for (except for the fact that you have to actually handle the empty case. But I consider that a good thing over throwing exceptions). So... what's the problem?

The problem, I explained it in my previous post: most of the time it is not possible to add an explicit empty state. Let me cite what I wrote:

I could add boost::blank as the first of my variant types. The thing is that it is not possible to modify the variant declaration. Let's say there is a function in a library taking a ref to a variant with specific types as a parameter (but these types do not include boost::blank).

Stop.

If the person creating that variant (and therefore defining the type for it) did not want that variant to have an empty state, then it does not have an empty state. This means that the creator of that variant has willingly chosen to accept the costs associated with not being empty. And, since you are willingly using that variant, you too have willingly chosen to accept those costs.

Just like if a library writer uses `std::string`, you can't use `std::basic_string<char, ..., some_other_allocator_type>` without copying the data. You must accept the limitations of the types that a library presents you with.

Now I want to implement that library function and inside of it I do a copy assignment from another variant and I want to avoid the guarantee because I want it to be optimal. It would not make sense to have to modify the library interface (adding boost::blank as one of the types of the variant passed as a ref parameter) just to accommodate the implementer.

To make it shorter, it doesn't make sens to me to change the types of my variant (which could be used all over my code) just to be able, at a specific place in code, to avoid the cost of the guarantee (if I don't need it in that place in code).

OK, let's look at the costs of the two approaches: Never-empty (with user-defined emptiness) vs. Empty (with throwing if a visitor doesn't explicitly handle the empty state). Here are the costs:

Empty with throw if empty isn't handled:

* Every visitor, or caller thereof, has a choice:
** Handle the empty state.
** Catch the exception thrown from failing to handle the empty state.
** Do neither and therefore have potentially broken code. Especially if we're talking about a variant instance that was not produced locally. I would consider this option a code smell that would fail code review.

Never-empty (per Boost.Variant's implementation):

* If none of the members of the variant are no-throw default-constructible, copying the variant will invoke memory allocation if and only if the current type held by the variant is not nothrow copy/move-constructible.

Both of these costs will be paid "all over my code". In the first case, you will pay this cost every time you write a visitor or call a visitor that doesn't test for empty. In the second case, you will pay it every time you copy the object, but only if none of the members are no-throw default-constructible (and then, only if that particular value is nothrow copy/moveable).

In one case, the cost will be paid everywhere, no matter what. You will pay either in added checks or difficult-to-test possible brokenness. They are inescapable. In the other case, there is a way to use the object to avoid the cost entirely.

I prefer the option where avoiding the cost is actually possible, rather than the one that forces you to pay for it one way or another.