[variant2] Formal review

classic Classic list List threaded Threaded
31 messages Options
12
Reply | Threaded
Open this post in threaded view
|

[variant2] Formal review

Boost - Dev mailing list
I. DESIGN
---------

The main design decision of Variant2 is the never-empty guarantee, which
is relevant when replacing the value of a variant. This is done without
overhead if the alternative types are "well-behaving"; if they are not,
then Variant2 falls back to using double storage.

This is a major difference to:

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

   * Boost.Variant which uses a temporary heap object instead. Avoiding
     this internal heap allocation is sufficient grounds for another
     never-empty variant type. In time critical applications heap
     allocation not only introduces indeterministic timing, but may also
     incur priority inversion due to thread synchronization within the
     heap allocator.

Variant2 has several ways to ensure the never-empty guarantee:

   V1. If all alternative types have non-throwing assignment, the variant
       cannot fail during re-assignment.

   V2. If an explicit null state is available, then this is chosen on
       re-assignment error. This is similar to std::variant, except is
       is opt-in.

   V3. If one of the alternative types has a non-throwing default
       constructor, then this is chosen on re-assignment failure.

   V4. Otherwise, the variant will remain it its old state (due to double
       storage) if re-assignment fails.

Criterion V3 is possibly surprising because the variant may change to
another type not anticipated by the user. This should be opt-in instead
(e.g. using a tag.)

I am missing a function to get the index of a type to work with the
index() function. Something similar to holds_alternative() but that
returns the index instead of a boolean. This useful in switch
statements, when we want to avoid visitors for some reason:

   variant<int, float> var = 1;

   switch (var.index()) {
     case index_of<int>(var): /* Do int stuff */ break;
     case index_of<float>(var): /* Do float stuff */ break;
   }

It would also be beneficial for performance reasons to add accessors
that have a narrow-contract, similar to relaxed_get() in Boost.Variant.
The implementation is already there (detail::unsafe_get.)

Better compiler error messages would be desirable. For instance, if we
use an illegal visitor that has different return types, then the
compiler error does not give us any hint about the different return
types.


II. IMPLEMENTATION
------------------

The implementation is high quality. Although it does lots of
meta-programming, most of the style is simple and easy to follow,
especially if you have a rudimentary knowledge of Boost.Mp11.
In a few places, like the visit() return type, the meta-programming
is more hardcore.

variant<T...> defines _get_impl as a public "private" function. This
can be made more safe by using detail::unsafe_get instead of _get_impl
throughout the code. detail::unsafe_get will continue to call _get_impl,
but the former should be made a friend of variant<T...> such that
_get_impl can be made private.

The other public "private" function, variant<T...>::_real_index(), does
not seem to be used and can be removed.

The emplace_impl(mp_false, mp_false, ...) contains two distinct cases
that depend on a compile time condition. If this is split in two, then
the two assert()s can be changed into static_assert()s.

The variant_alternative and get functions have a couple of compiler
workarounds. The code could be made clearer if the workaround is always
used for all compilers. Or does is this related to C++11 constexpr?


III. DOCUMENTATION
------------------

The documentation is mainly aimed at experienced users.

There is no tutorial for people unfamiliar with variant types, nor is
there a design rationale that explains why Variant2 is exists when we
already have Boost.Variant and std::variant.

The reference documentation is adequate, although a bit terse.


IV. MISC
--------

Having written my own variant class (that has a maximum size, and any
type exceeding the limit is allocated on heap) puts me in a good
position to assess Variant2. I was also the review manager of Boost.Mp11
upon which Variant2 is built.

I have spent 5-6 hours reading documentation, reviewing the code, and
writing small test programs.


V. VERDICT
----------

Variant2 fills a hole not covered by Boost.Variant and std::variant.

I vote to CONDITIONALLY ACCEPT Variant2 into Boost, provided that the
following change be made:

   1. The selection of an arbitrary non-throwing type in case of an
      re-assignment failure (criterion V3 in the DESIGN section above)
      should be made optional. By default it should use double storage
      in this case.

I would furthermore like to see improvements to the documentation, as
well as the index_of/safe_get functionality, but neither is a
requirement for acceptance.

I have not reviewed expected<T, E...>.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
On 4/13/19 7:26 PM, Bjorn Reese via Boost wrote:

> Better compiler error messages would be desirable. For instance, if we
> use an illegal visitor that has different return types, then the
> compiler error does not give us any hint about the different return
> types.

A possible solution is to declare a tag and use this in the else-part
of mp_if. E.g.

struct return_types_must_be_the_same;

template<class L> using front_if_same =
mp11::mp_if<mp11::mp_apply<mp11::mp_same, L>, mp11::mp_front<L>,
return_types_must_be_the_same>;

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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?


--
Rainer Deyke ([hidden email])


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
On Sun, Apr 14, 2019 at 10:19 AM Rainer Deyke via Boost <
[hidden email]> 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.

If you have:

struct foo { bar x; .... };

Even though bar provides the basic guarantee, if a bar operation fails, it
is still possible for x to change to a valid (for bar) state that makes the
foo object invalid. This doesn't mean that there's something wrong with the
design of bar, it just means that the basic guarantee does not propagate
automagically.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
On 14.04.19 20:16, Emil Dotchevski via Boost wrote:

> On Sun, Apr 14, 2019 at 10:19 AM Rainer Deyke via Boost <
> [hidden email]> 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 ([hidden email])


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
On Sun, Apr 14, 2019 at 12:53 PM Rainer Deyke via Boost <
[hidden email]> wrote:
>
> On 14.04.19 20:16, Emil Dotchevski via Boost wrote:
> > On Sun, Apr 14, 2019 at 10:19 AM Rainer Deyke via Boost <
> > [hidden email]> 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?

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.

This is orthogonal to maintaining higher-level invariants: if an error
occurs and the result is that a member variant<> object goes in a valid
state which violates the invariants of the containing type, the containing
type has to do work to provide the basic guarantee, with or without the
never-empty guarantee.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
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).

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 14.04.19 22:58, Emil Dotchevski via Boost wrote:

> On Sun, Apr 14, 2019 at 12:53 PM Rainer Deyke via Boost <
> [hidden email]> 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 ([hidden email])


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Sun, Apr 14, 2019 at 4:48 PM Gavin Lambert via Boost <
[hidden email]> wrote:
>
> 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).

Let's say an error occurs, and a member variant's state now violates the
invariants of the enclosing type. If there is a special empty state -- or
if there isn't -- under the basic guarantee you'd catch the exception and
do work to restore the invariants. There is no difference in the recovery
steps, and once they are complete, there is nothing to detect, the object
is as valid as any other.

The benefits of the never-empty guarantee are elsewhere, not during error
handling, in that the presence of the empty state requires the program to
deal with it.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Sun, Apr 14, 2019 at 11:57 PM Rainer Deyke via Boost <
[hidden email]> 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 <
> > [hidden email]> 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.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
On 15.04.19 09:06, Emil Dotchevski via Boost wrote:
> On Sun, Apr 14, 2019 at 11:57 PM Rainer Deyke via Boost <
> [hidden email]> 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<int, bool> 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 ([hidden email])


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
pon., 15 kwi 2019 o 09:06 Emil Dotchevski via Boost <[hidden email]>
napisał(a):

> On Sun, Apr 14, 2019 at 11:57 PM Rainer Deyke via Boost <
> [hidden email]> 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 <
> > > [hidden email]> 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. It is enough if I can see all the control
flows and see that neither of them produces the undesired state.

In the case of variant and its vaueless_by_exception state the undesired
state only occurs when someone is not doing their exception handling right.
So, technically the unwanted state could be constructed. But putting a
defensive if-statement for concealing symptoms of bugs in some other other
function would be the wrong way to go.

Regards,
&rzej;

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
niedz., 14 kwi 2019 o 19:19 Rainer Deyke via Boost <[hidden email]>
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;

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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?


Regards, Phil.



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
pon., 15 kwi 2019 o 16:46 Phil Endecott via Boost <[hidden email]>
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;

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Mon, Apr 15, 2019 at 3:56 AM Andrzej Krzemienski via Boost <
[hidden email]> wrote:

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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Mon, Apr 15, 2019 at 8:16 AM Andrzej Krzemienski via Boost <
[hidden email]> wrote:
>
> pon., 15 kwi 2019 o 16:46 Phil Endecott via Boost <[hidden email]>
> 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.

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

"All invariants are intact": f.e. even after std::vector::op= fails, the
target vector is guaranteed to be in a perfectly valid state. By analogy,
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.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
pon., 15 kwi 2019 o 21:46 Emil Dotchevski via Boost <[hidden email]>
napisał(a):

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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [variant2] Formal review

Boost - Dev mailing list
wt., 16 kwi 2019 o 16:47 Steven Watanabe via Boost <[hidden email]>
napisał(a):

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

Yes, this is what I am encouraging. Treating "effective invariant" as the
same precondition applied to every observer function, as you propose is
impractical, therefore I would rather introduce a new notion. This
shouldn't be that surprising. In the end an ordinary invariant is also the
same precondition and postcondition applied to every function in the
interface: it is a "shorthand notation".


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

It would be very helpful for me if I were demonstrated such example. This
would allow me to revise my claims.

Regards,
&rzej;


>
> > * 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
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
12