Re: [boost] [variant2] Formal review

Subject: Re: [boost] [variant2] Formal review
From: Andrzej Krzemienski (akrzemi1_at_[hidden])
Date: 2019-04-16 11:18:45

pon., 15 kwi 2019 o 21:46 Emil Dotchevski via Boost <boost_at_[hidden]>
napisał(a):

> On Mon, Apr 15, 2019 at 3:56 AM Andrzej Krzemienski via Boost <
> boost_at_[hidden]> wrote:
> >
> > pon., 15 kwi 2019 o 09:06 Emil Dotchevski via Boost <
> boost_at_[hidden]
> >
> > napisał(a):
> >
> > > On Sun, Apr 14, 2019 at 11:57 PM Rainer Deyke via Boost <
> > > boost_at_[hidden]> 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_at_[hidden]> 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.
>

I guess you are referring to function std::visit(), which checks for
valueless_by_exception state and if one is detected throws an exception.
Indeed, in the model that I am presenting, this is a useless check. And as
Peter has pointed out, it unnecessarily compromises performance.

>
> 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,

Yes, I am making this point.

> 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.
>

Hmm, interesting conclusion. I can see why one could arrive at it, but this
is not what I am saying. I guess the reason for my messages not getting
across is that I am trying to describe a different model of thinking about
the program correctness. My model is a bit more nuanced, therefore some
concepts cannot be mapped back onto the model "anything that is not
invariant needs to be checked all the time."

But let's still try to do it. You already know I do not like variant2 or
boost::variant solution. You correctly point out that I also should not
like std::variant. So let's consider a yet another variant design, call it
ak_variant, that behaves similarly to std::variant except that it has a
narrow contract on visit() and probably also in comparison operations: it
is UB if you call them and variant is in the valueless_by_exception state.

Now, let's match it against the definition of "Basic exception guarantee"
from cppreference:

"Basic exception guarantee -- If the function throws an exception, the
> program is in a valid state. It may require cleanup, but all invariants are
> intact."

I am not sure what "may require cleanup" should mean here, but I guess our
point of controversy is about the "invariant" part. For the sake of
satisfying this definition, and making ak_variant support "basic exception
safety" as defined in cppreference, lets define ak_variant's invariant so
that valueless_by_exception is considered a "valid" state.

To this, you say:

the "valueless by exception" state in variant must be a valid state, which
> means that various operations may not result in UB even after assignment
> failure.

I claim that this characterization is incorrect. Valid state means type's
invariants should be satisfied, but it does not mean that you do not get UB
when you invoke any operation from the type's interface. Or, to put it in
other words, some (even most) functions in type's interface can have a
narrow contract: it is UB to call them with certain values, and there is
nothing in it that would violate basic exception safety guarantee, or any
other principle commonly accepted in the language. To give one example:
shared_ptr: it is often ok to dereference it, but if it is in null-pointer
state, this state is valid and it is nonetheless UB if you try to
dereference it. I know that you know it. I just want to remove one argument
from this discussion: it is *not* against the basic exception safety
guarantee if in a "valid but unspecified state" you get UB if you try to
invoke some operation. It is the operation's precondition that determine
when you get UB and when not.

Now, the other argument I heard you say is that if this should be the case,
the variant's invariant being weakened, users have to be prepared for this
special state allowed by the invariant and put defensive if statements
everywhere in case they get the valueless_by_exception state, or
alternatively std::variant should perform these defensive checks
internally. And yes, if you stick to this model which says "any state that
invariant allows can occur at any moment in any place" then you have to
conclude that defensive checks are necessary everywhere. 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:

* 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.

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.

Because we can safely assume that these situations never happen, "effective
invariant" is what we will always see in correct programs. Therefore there
is no need to check if "effective invariant" is in place.

This is why I can claim that ak_variant offers basic exception safety (it
preserves "invariant", which is weak), and at the same time no-one needs to
put defensive if-statements inside or outside the variant (because the
"effective invariant" is strong.) And yes, speaking abut two invariants is
confusing and not as simple as single invariant, but I think this
distinction better reflects the reality of the programs.

Of course, in incorrect programs, values that do not satisfy "effective
invariant" will be observed. But in these cases it can be beneficial to
reflect this as UB, for the purpose of better bug detection.

No, going back to your other remark:

"All invariants are intact": f.e. even after std::vector::op= fails, the
> target vector is guaranteed to be in a perfectly valid state.

"Perfectly valid" is an informal term. Formally, vector has a strong
invariant. In my model, a class can have a strong invariant, but is not
required to in order for people not to have to worry about "special
states": it is enough that the "effective invariant" is strong. I have a
question to you. Did you ever in your program make use of this property of
vector that it is in a valid but unspecified state? Did you ever read
values from such a vector in a valid but unspecified state? Did you do with
it anything else than destroy it or reset it?

One final note, the only practical value from basic-exception-safety
operations is that you can be sure your objects will be safely destroyed or
reset. If you make use of these values, you are doing something wrong. That
is my claim, and no-one has so far convinced me that I am wrong.

Of course, there are operations that do not offer strong exception-safety
guarantee, but still offer something more than the basic guarantee, for
instance they guarantee that in case of an exception they will go into some
fallback state, or that they will reset themselves. If you know this, you
can use the object still; but this does not apply to just any
basic-guarantee operation.

I hope this clarifies my perspective a bit.

Regards,
&rzej;