On 14.04.19 20:16, Emil Dotchevski via Boost wrote:

On Sun, Apr 14, 2019 at 10:19 AM Rainer Deyke via Boost < boost@lists.boost.org> wrote:

...

On 13.04.19 19:26, Bjorn Reese via Boost wrote:

...

* std::variant which enters an invalid (valuless_by_exception) state. While that may be appropriate for some use cases, there are others where it is not. For instance, the variant may be used for a state machine where the alternative types are function object types to be invoked when events arrive. Having a valueless state is the wrong choice for this use case.

Wait. I don't understand how never-empty is an advantage in this example.

The invariants of the state machine can still be broken.

It is not the job of variant to maintain the invariants of the state machine, that is the job of the state machine.

Yes, but the question was about the benefits of the never-empty guarantee. If the never-empty guarantee doesn't help with maintaining higher level invariants, then what benefit does it bring? -- Rainer Deyke (rainerd@eldwood.com)

On 15/04/2019 08:58, Emil Dotchevski wrote:

...

Yes, but the question was about the benefits of the never-empty guarantee. If the never-empty guarantee doesn't help with maintaining higher level invariants, then what benefit does it bring?

If the design allows for one more state, then that state must be handled: various functions in the program must check "is the object empty" and define behavior for that case. The benefit of the never-empty guarantee is that no checks are needed because the object may not be empty.

As I've said elsewhere, I don't see the difference between "is this empty" and "did this unexpectedly change type", except that the former is easier to detect (and hence better).

On 14.04.19 22:58, Emil Dotchevski via Boost wrote:

On Sun, Apr 14, 2019 at 12:53 PM Rainer Deyke via Boost < boost@lists.boost.org> wrote:

...

Yes, but the question was about the benefits of the never-empty guarantee. If the never-empty guarantee doesn't help with maintaining higher level invariants, then what benefit does it bring?

If the design allows for one more state, then that state must be handled: various functions in the program must check "is the object empty" and define behavior for that case. The benefit of the never-empty guarantee is that no checks are needed because the object may not be empty.

No. A function is not required to check its invariants and preconditions. If a function is defined as taking a non-empty variant, then it is up to the caller to make sure the variant is not empty before passing it to the function. If the function is a member of the same object as the variant and the object requires that the variant is non-empty as an invariant, then it is up to the other member functions of the object to maintain that invariant. In both cases the function can just assume that the variant is non-empty. -- Rainer Deyke (rainerd@eldwood.com)

On 15.04.19 09:06, Emil Dotchevski via Boost wrote:

On Sun, Apr 14, 2019 at 11:57 PM Rainer Deyke via Boost < boost@lists.boost.org> wrote:

...

No. A function is not required to check its invariants and preconditions. If a function is defined as taking a non-empty variant, then it is up to the caller to make sure the variant is not empty before passing it to the function.

The point is, there will be checks, in various functions (e.g. in "the caller"),

No checks are necessary, unless a variants passes from a context where an empty state is allowed to one where it isn't. If the empty state can only be entered via exception, then the only context in which an empty state can exist is in the aftermath of an exception, where we would have to either replace the empty variant with a non-empty variant or allow the variant to leave the scope. But we would have to do this even with a never-empty variant in order to maintain our invariants, so the actual code would be no different in either case.

except if we know the state is impossible, A.K.A. the never-empty guarantee.

We can know that the state is impossible even if the guarantee is not an intrinsic property of the variant type. variant v = 1; do_something_with(v); Here 'do_something_with' is called with an argument that is never empty - and never a boolean, and never an integer other than 1. -- Rainer Deyke (rainerd@eldwood.com)

On Mon, Apr 15, 2019 at 3:56 AM Andrzej Krzemienski via Boost < boost@lists.boost.org> wrote:

pon., 15 kwi 2019 o 09:06 Emil Dotchevski via Boost

napisał(a):

...

On Sun, Apr 14, 2019 at 11:57 PM Rainer Deyke via Boost < boost@lists.boost.org> wrote:

...

On 14.04.19 22:58, Emil Dotchevski via Boost wrote:

...

On Sun, Apr 14, 2019 at 12:53 PM Rainer Deyke via Boost < boost@lists.boost.org> wrote:

...

Yes, but the question was about the benefits of the never-empty guarantee. If the never-empty guarantee doesn't help with

maintaining

...

...

...

...

higher level invariants, then what benefit does it bring?

If the design allows for one more state, then that state must be handled: various functions in the program must check "is the object empty" and define behavior for that case. The benefit of the never-empty guarantee is that no checks are needed because the object may not be empty.

No. A function is not required to check its invariants and preconditions. If a function is defined as taking a non-empty variant, then it is up to the caller to make sure the variant is not empty before passing it to the function.

The point is, there will be checks, in various functions (e.g. in "the caller"), except if we know the state is impossible, A.K.A. the never-empty guarantee.

...

If the function is a member of the same object as the variant and the object requires that the variant is non-empty as an invariant, then it is up to the other member functions of the object to maintain that invariant. In both cases the function can just assume that the variant is non-empty.

For someone to be able to assume, someone has to do the checking, or else we have the never-empty guarantee.

This is a popular misunderstanding of preconditions and invariants. In order to guarantee that some state of the object never occurs, I do not have to check this anywhere.

But we do, std::variant does in fact have checks. The point you're making is that the checks are not needed if we specify that calling e.g. visit after assignment failure is UB, but that violates the basic guarantee. Once we introduce the empty state, logically, either we have checks or we lose the basic guarantee. But maybe you also think that the basic guarantee is useless.

AMDG On 4/16/19 5:18 AM, Andrzej Krzemienski via Boost wrote:

<snip>However, I propose to depart from this model and adapt a more nuanced one. Let's introduce a new term: "effective invariant": this is a constraint on object's state much as "invariant". It determines what values an object can assume in a program where programmers adhere to the important principles that are necessary for programs to be correct. We can list some of them:

This is nonsense. Either something is an invariant or it isn't. If it isn't an invariant, then it's a precondition of every function that assumes that it is true. Handling it in this manner isn't wrong, per se, but it is more complex and therefore more error prone. You can't have your cake and eat it, too. Calling it an "effective invariant," just encourages treating it as if it were a real invariant.

* Destructors do not throw exceptions, even if they fail to release resources

* Objects that threw from the operation with basic exception safety, which does not guarantee any other special behavior on exception, are never read: they are either destroyed or reset,

Never read is too strong. A more correct statement is that the object's state should not affect the observable behavior of the program. Speculative execution is fine, for example, as long as the result is eventually thrown away. This mainly applies to destructors that do some kind of actual work, which is relatively rare, but does happen.

* Objects that are moved from, unless they explicitly guarantee something more, are only destroyed or reset.

This is a very different case from an exception, as you should usually know statically whether an object has been moved from and many types do define the state of an object after a move.

There may be more of rules like this, which seem quite uncontroversial. Note the order: I do not introduce these rules because I want to define "effective invariant". these rules are already in place and programmers, hopefully, strive to implement them in their programs.

These rules are more or less reasonable, but the reason that they aren't hard-and-fast is that they're consequences of the underlying semantics of the operations in question. In Christ, Steven Watanabe

Le mardi 16 avril 2019 à 08:47 -0600, Steven Watanabe via Boost a écrit :

AMDG

On 4/16/19 5:18 AM, Andrzej Krzemienski via Boost wrote:

...

<snip>However, I propose to depart from this model and adapt a more nuanced one. Let's introduce a new term: "effective invariant": this is a constraint on object's state much as "invariant". It determines what values an object can assume in a program where programmers adhere to the important principles that are necessary for programs to be correct. We can list some of them:

This is nonsense. Either something is an invariant or it isn't. If it isn't an invariant, then it's a precondition of every function that assumes that it is true. Handling it in this manner isn't wrong, per se, but it is more complex and therefore more error prone. You can't have your cake and eat it, too. Calling it an "effective invariant," just encourages treating it as if it were a real invariant.

I don’t see this as nonsense. Let’s divide functions in three categories : * the ones that have additional requirements over the invariants : these preconditions are set / documented at the function signature level * the ones that expect the "effective invariant" to be true. This is most functions, no definition/documentation of precondition should be mandatory * the ones that can really accept an object in any state. This is special function, usually error handling ones. This is also defined / documented. I do think that it makes a lot of sense. I think reasoning that way is an improvement over ending up with preconditions such as is_not_valueless(v) everywhere in your code (or, worse, actually handling such exceptional states in places it will never happen). There’s a real symetry, and one way is actually closer to the programmer’s intent, and less error prone. Just to make an analogy, consider a raw C pointer. Your functions can either allow it to be nullptr, or assume it is not (up to the caller to honor the precondition). Whether you consider that the default is to allow everything, and documenting if you do not, or that the default is to forbid nullptr, unless explicitely allowed, is more a convention than anything else. You’ll find both ways in documentations. Regards, Julien

wt., 16 kwi 2019 o 18:09 Peter Dimov via Boost napisał(a):

Andrzej Krzemienski wrote:

...

Let's introduce a new term: "effective invariant": this is a constraint on object's state much as "invariant". It determines what values an object can assume in a program where programmers adhere to the important principles that are necessary for programs to be correct. We can list some of them:

* Destructors do not throw exceptions, even if they fail to release resources

* Objects that threw from the operation with basic exception safety, which does not guarantee any other special behavior on exception, are never read: they are either destroyed or reset,

* Objects that are moved from, unless they explicitly guarantee something more, are only destroyed or reset.

"Effective invariants" have been tried before, and abandoned each time. This is basically the notion of "singular values", also known affectionately as "zombie objects". The most famous instance is probably two-phase construction, but signaling NaNs are another example. The idea is that these singular zombies "never occur" in the mythical correct program, so it's fine to make accesses to them undefined behavior.

What I hear you describe is types with weak invariants, where the zombie state can be set very easily in the normal (not requiring special attention) parts of the program: ``` float x = std::numeric_limits<float>::quiet_NaN(); TwoPhaseInitResource r {}; r.initialize("params"); use(r); r.release_resources(); // risk: r could still be used here ``` I agree with you that this subject of easily obtained zombie state has been explored, and I agree with you that types that expose it are dangerous and had best be avoided. I would never want to promote in the slightest degree a design like that. However, you seem to be missing the distinction which I find very important: a "zombie" state that can only occur in *very special situations* (which correspond to the incorrect programs) is something substantially different than "zombie" states that can occur everywhere. I have never read or heard of "zombie states in very special circumstances" having been explored. Therefore I consider the problem new and worth exploring. If "zombie states in very special circumstances" have been explored also and I am just ignorant of the work, I would welcome a correction, ideally in form of a link. Regarding the "never occur" part, I do not use the relation "`zombie states in very special circumstances` only occur in incorrect programs" to claim that "`zombie states in very special circumstances` never occur in programs". Programs will have incorrect parts and they will likely result in "zombie states in very special circumstances" occurring in the program. However, in places where a program has a bug, it is better (and for sure: not worse) to reflect this as UB, than to make the program appear correct on the surface and have it do random things according to the well specified rules of the abstract machine. This is because UB is a well understood manifestation of a bug that tools like static analyzers can track and report. Whereas superficial fixes that cover up user bugs are opaque to the automated tools. Let me give you one example. There are three ways to address the situation where a two-phase-init Resource type can be used when it is not initialized: ``` Resource r {}; // phirst phase init use(r); // what to do? r.initialize("params"); // second phase init ``` Option 1: We can call it UB: Put an assertion and/or explicit UB declaration understood by the compiler (such as __builtin_unreachable(), or __builtin_assume()). Option 2: try to "fix" someone else's bug: if `r` does not contain a value, initialize it on the fly with some invented initialization parameters and go on making use of the now initialized resource. No UB, so some group of people is satisfied with this solution. Option 3: redesign the interface, so that the user is forced to change his logic, and this change alone removes bugs. The redesign is to change a two-phase-init interface to a RAII-like interface. Then making bugs is impossible. So, option 3 is superior; provided that it is implementable. If it is not for some reason, option 1 is superior to 2, because option 2 conceals the bug from tools and from code reviewers. I treat the situation in the variant as such: unable to go with option 3, so we should prefer option 1 to option 2.

Typically, after a decade or so of experience, "never" is determined to occur much more frequently than previously thought, and the idea is abandoned, until its next discoverer.

I make a promise that if you convince me that "zombie states in very special circumstances" are as bad as "zombie states everywhere" I will document this, put it in my blog and somewhere in Boost docs, so that if such discussion should be rehashed in the future there will be an easily accessible link that people can be pointed to.

There are two main problems with this school of thought: one, creating a dormant zombie object is the worst possible thing that can happen in a program, because the "undefined behavior" can occur much later in a context far removed from the one that caused the error. Two, abiding by the rules that govern the supposedly correct programs is too cumbersome and there's no enforcement and no immediate feedback (compile- or run time) when they are broken.

Again, I am not convinced that you are seeing the distinction between "zombie states in very special circumstances" and "zombie states everywhere". I agree with you on "zombie states everywhere". Regards, &rzej;

śr., 17 kwi 2019 o 16:32 Peter Dimov via Boost napisał(a):

Andrzej Krzemienski wrote:

...

However, you seem to be missing the distinction which I find very important: a "zombie" state that can only occur in *very special situations* (which correspond to the incorrect programs) is something substantially different than "zombie" states that can occur everywhere.

In a correct program using two-phase init, zombie states also cannot occur. The same rule is in effect: a correct program should never access a partially constructed object. There's nothing that makes the situation of a partially constructed object being observed any less special or *very special* than in what you suggest.

The distinction that I see is quite clear: In the case of two-phase init, you have to do nothing and the zombie object is observable. Usually these types have a default constructor. You construct, forget to initialize in some path (because you are catching exceptions too soon), and then you get a bug: because you failed to do something. In case of observing the state of the moved-from objects, or objects that threw from operation that guaranteed only an unspecified albeit valid state, you have to voluntarily do some action do get it. It cannot be done by omission: you have to put an explicit std::move or cast, and you know you are doing something potentially dangerous that requires special attention. Or, you have to put an explicit try-catch block, and you know you are doing something that requires special attention: because of stack unwinding many functions that were supposed to be called were canceled and now after the catch subsequent functions will be invoked and they may depend on the side effects of the functions that were canceled. In both this cases you have to voluntarily do something to get to this state. So the difference is: can you get to the zombie state by omission or can you get to the zombie state voluntarily. Another important difference is that in many cases a two-phase init class can be redesigned so that it is a RAII-like class, and then their users cannot make an omission bug. In case of moved-from state or unspecified (albeit valid) state, it is impossible to avoid the voluntarily put bugs: they can only be concealed. I will try to explain it later in this reply.

The problem is not one to be solved by putting asterisks around words. The problem, as I said, is that the rules governing correct programs are hard to enforce, and their violation is detected much too late, in parts of the program that have done nothing to violate the rules.

Yes. I acknowledge this as a serious problem.

With your rules, when the following very special situation throws:

x1 = std::move(x2);

you now have x1 singular, because no basic exception safety, and x2 singular, because moved-from. Now whether the program is correct or not depends on whether one of x1 or x2 escapes unscathed.

Yes, I think we agree up to this point. A correct program should make sure that if the above operation fails, unless we know either of the objects guarantees some concrete state after the throw, both objects should be removed from the scope or reset to a known state.

This is hard to diagnose statically - not that anyone has even tried -

Agreed: hard to diagnose, and it is to be expected that in real-life programs that are often incorrect this will happen.

and will not be diagnosed at runtime until two hours later an unrelated part of the program tries to access x1 or x2,

Yes: the symptoms may appear much later in unrelated parts of the program that themselves are correct.

in which case you'll have a crash ("fast fail"),

I disagree: in the worse case it will not be a crash, but a program will continue its operations and give an impression that it is working fine, but it will be doing something else than the programmer expected. A self driving car will be reporting that all the systems are functioning normally, but it will be crashing into people. This is fare worse than the application crash.

except it won't be fast, and it will tell you nothing about what caused it or who was at fault.

Yes.

There's really not that much difference between the above and

x1.init( f() );

except this one is easier to diagnose statically.

I have explained the difference above. So, let's now explore an alternative situation. x1 = std::move(x2); This throws, and leaves the objects in an unspecified (albeit "valid") state, an exception handling is stopped prematurely, so that the objects remain in scope and the programmer makes no attempt to put their values into a known state. The only guarantee we have now is that no operation on `x1` or `x2` will cause an UB. But we have no guarantee as to the correctness or consequences of this program. A program cannot be expected to work correctly if it uses unspecified values: you depend on the values of the variables, but you do not care if they were selected at random. In case of UB we at least had some probability that UB at some point would be detected and the program stopped (self driving car would report malfunction in one of its redundant systems), but now we have the guarantee that no malfunction will be reported and the program will be perceived as working correctly and the car will be crashing into people. So, I agree with you that the case with UB is bad. But the alternative -- random values instead of UB -- is even worse. If we map this situation onto the design of `variant`. Setting some default constructed T upon throw is considered, at least by me, the worst possible path. Leaving it in zombie state is better, although I acknowledge the FUD over UB. Providing strong or semi-strong guarantee is also a better solution: because in this case all my talk about objects surviving the stack unwinding no longer apply.

...

Again, I am not convinced that you are seeing the distinction between "zombie states in very special circumstances" and "zombie states everywhere". I agree with you on "zombie states everywhere".

You're constructing a strawman of your choosing and setting it on fire.

Peter, It is clear that you do not agree with me, but do some parts of what I say make sense to you? Regards, &rzej;

czw., 18 kwi 2019 o 19:57 Nevin Liber via Boost napisał(a):

On Thu, Apr 18, 2019 at 2:41 AM Andrzej Krzemienski via Boost < boost@lists.boost.org> wrote:

...

x1 = std::move(x2);

...

This throws, and leaves the objects in an unspecified (albeit "valid") state, an exception handling is stopped prematurely, so that the objects remain in scope and the programmer makes no attempt to put their values into a known state. The only guarantee we have now is that no operation on `x1` or `x2` will cause an UB.

Not true. The only operations you can perform on those objects are either (a) ones with no preconditions or (b) those where the preconditions are checked first and found to be valid.

To put more context to this remark, the quoted text is me trying to explore Peter's variant or another type with strong invariant, where the guarantee is fulfilled by inventing values on the fly. I agree with your statement, that in practically any type we will have functions with narrow contract. But I think it misses the core of the disagreement, which I believe to be: can you still do a lot of things with this object or only a very narrow subset of things? The goal of the never-empty basic guarantee is to have less UB's in the code (or less defensive checks).

The problem with an illegal-to-observe zombie state is that it adds an unexpected precondition to copy/move construction, and that precondition is viral. For instance, having such a precondition breaks the following:

void ByRef(vector<PossiblyZombieObject>& v) { v.resize(v.capacity() + 1); // error if v contains any zombie objects }

or even

void ByValue(vector<PossiblyZombieObject> v) { /* ... */ } // error if v contains any zombie objects

And even if callees decided that want to protect against this (and let me reiterate, that should never be a requirement), they cannot, precisely because the zombie state is illegal-to-observe.

A std::variant in the valueless_by_exception state is copy/move constructible because that state is observable, and that is by design. Specifically, valueless_by_exception is not a zombie state, but it is a weakening of the invariants from "exactly 1 of n types" to "at most 1 of n types". How much that matters is ultimately what we are debating.

Thanks for this observation. Maybe my adapting the word "zombie state" was unfortunate as it may imply things that I never wanted to imply. In the model that I would like to propose with "strict invariant" and an "effective invariant" there is basically no problem with copying and moving the "special state". The special state is the difference between the "effective invariant" and "strict invariant" , in case of variant it is .valueless_by_exception(). This state can simply be propagated during move/copy. This preserves the information about the bug. However, any situations were I can imagine this would be needed would be again in the places that one should not have in the program: where you allow the objects that threw from the basic-guarantee operation to survive, or their state to survive. Even your examples above. If you are manipulating a PossiblyZombieObject in a vector and it throws, the object gets "corrupted" and unless you reset it to a known state it corrupts the entire vector, so either you have to reset the vector or destroy it. Resizing at this point is surely a bug. A second thought. I say the special state should never be observed, but it is a bit of a simplification. There is one situation where observing the special state makes sense: it is in the function valueless_by_exception() for variant, and in general case it could be called is_in_weak_state() or some such. If not anything else, it would be used to describe preconditions of other functions, and it could be used in clever ways for assisting static analysis or debugging. However correct programs should never have a need for the users of a given type to call this function to "check" if an object is in special state: in correct programs it is never observed. Regards, &rzej;

On 17/04/2019 05:07, Emil Dotchevski wrote:

...

I guess you are referring to function std::visit(), which checks for valueless_by_exception state and if one is detected throws an exception.

https://github.com/llvm-mirror/libcxx/blob/master/include/variant

I counted 20+ checks, but actually even if the runtime cost was zero, the empty state is one more thing the user has to think about, one more thing that could go wrong -- but only in the context of error handling where writing unit tests, debugging and QA are all extra difficult.

That's just an example of poor design/optimisation, though. The valueless state should be treated as just another index position exactly like any other (ironically, pretty much exactly how Peter's "non-valueless" variant does). Then checking for the valueless state is precisely identical to checking for any other state, so it does come for free.

On 4/16/19 1:18 PM, Andrzej Krzemienski via Boost wrote:

to depart from this model and adapt a more nuanced one. Let's introduce a new term: "effective invariant": this is a constraint on object's state much as "invariant". It determines what values an object can assume in a program where programmers adhere to the important principles that are necessary for programs to be correct. We can list some of them:

* Destructors do not throw exceptions, even if they fail to release resources

Quoting [1]: "The basic guarantee: that the invariants of the component are preserved, and no resources are leaked." [1] https://www.boost.org/community/exception_safety.html

pon., 15 kwi 2019 o 16:46 Phil Endecott via Boost napisał(a):

Emil Dotchevski wrote:

...

If the design allows for one more state, then that state must be handled: various functions in the program must check "is the object empty" and define behavior for that case.

I think that's often not really the case; at least, it is not a large burden.

It seems to me that in many/most cases, the empty state is essentially transient; it can exist between the throw in the assignment and the end of the variant's scope:

void f() { variant<...> v{42}; v = something; // throw in assignment; v is empty foo(); // skipped blah(); // skipped // v is destructed }

You can only observe the empty state if you have a try/catch inside the scope of the variant. Or possibly something with a dtor that accesses the variant. If you limit yourself to not doing that, then you can ignore the possibility of empty in the rest of your logic.

What do others think? Do you believe that it would be common to catch the exception thrown during the variant assignment and not "fix up" the variant's value, such that code after the catch could see the variant in its empty state?

"Common" may not be the right word here. If there were practical use cases in correct programs that do it that are not common we would have to strive even more to address this case. But my position is that programs that correctly handle exceptions, and where people understand what a basic guarantee is and is not, *never* do this. Of course, we can invent many pervert examples that do this, but I cannot think of any in the program that handles exceptions in a correct way: never tries to observe the state of the object that threw from basic-guarantee operation. Regards, &rzej;

niedz., 14 kwi 2019 o 19:19 Rainer Deyke via Boost napisał(a):

On 13.04.19 19:26, Bjorn Reese via Boost wrote:

...

* std::variant which enters an invalid (valuless_by_exception) state. While that may be appropriate for some use cases, there are others where it is not. For instance, the variant may be used for a state machine where the alternative types are function object types to be invoked when events arrive. Having a valueless state is the wrong choice for this use case.

Wait. I don't understand how never-empty is an advantage in this example.

If the alternative types are function pointer types, then never-empty provides no improvement over valueless-by-exception. On an exception, the variant will simply contain a typed nullptr instead of being empty.

If the alternative types are non-empty function objects, then never-empty provides at best a marginal improvement over valueless-by-exception. On an exception, the variant will contain a wrong (default-constructed) function object.

If the alternative types are empty function objects, then the benefit of never-empty is still marginal. The variant will still contain a wrong function object, albeit one drawn from the pool of correct function objects. The invariants of the state machine can still be broken. Also, if the alternative types are empty function objects, then there is no reason for why their constructors should ever throw, so the never-empty guarantee should never come into play in the first place.

What am I missing here?

A global state machine is a very good illustration of the problem. std::variant cannot address this use case and everyone can see it immediately. We need a type with strong exception safety guarantee. variant2 (or Boost.Variant) cannot handle this use case either. But because of the misunderstanding of what the "select random value" guarantee offers, some programmers may be deceived and believe that this would work. This is why I like std::variant better: it does not try to confuse you about what you can and cannot do. Regards, &rzej;