Implementability of std::optional

[Nikolay Ivchenkov]

[This thread is based on the recent discussion "Implementation of assignment in std::optional and Core issue 1404: Object reallocation in unions" on SG12 reflector (about undefined/unspecified behavior)].

----------------------------------------------------------------------

The following concerns are related to the suggested implementation of optional - see
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3672.html
https://github.com/akrzemi1/Optional/blob/master/optional.hpp

Consider the following example:

    #include "optional.hpp"
    #include <iostream>

    struct A
    {
        constexpr A(int &x) : ref(x) {}
        int &ref;
    };

    int main()
    {
        int n1 = 0, n2 = 0;
        std::experimental::optional<A> opt = A(n1);
        opt.emplace(n2);
        opt->ref = 1;
        std::cout << n1 << " " << n2 << std::endl;
    }

Here initialization of variable opt implies initialization of union member storage_.value_ (which has type A). Then expression opt.emplace(n2) destroys object storage_.value_ via explicit destructor call and creates new object by placement form of new-expression (using forwarded n2 in the new-initializer). All public functions that provide access to the stored value (operator->(), operator *(), value(), etc.), obtain pointer/reference through object expression storage_.value_.

This is a simplified version of the above code:

    #include <iostream>

    #define FORWARD(x) static_cast<decltype(x) &&>(x)

    template <class T>
        union U
    {
        constexpr U(T &&x) : value_(FORWARD(x)) {}
        unsigned char dummy_;
        T value_;
    };

    template <class T>
        struct optional
    {
        constexpr optional(T &&x) : storage_(FORWARD(x)) {}
        template <class... Params>
            void emplace(Params &&... params)
        {
            storage_.value_.~T();
            new (&storage_.value_) T(FORWARD(params)...);
        }

        U<T> storage_;
    };

    struct A
    {
        constexpr A(int &x) : ref(x) {}
        int &ref;
    };

    int main()
    {
        int n1 = 0, n2 = 0;
        optional<A> opt2 = A(n1);
        opt2.emplace(n2);
        opt2.storage_.value_.ref = 1;
        std::cout << n1 << " " << n2 << std::endl;
    }

The question is: What may happen at line

    opt->ref = 1;

in the former code or

    opt2.storage_.value_.ref = 1;

in the latter (simplified) code?

According to N3485 - 3.8/7,

    If, after the lifetime of an object has ended and before the
    storage which the object occupied is reused or released, a new
    object is created at the storage location which the original
    object occupied, a pointer that pointed to the original object, a
    reference that referred to the original object, or the name of the
    original object will automatically refer to the new object and,
    once the lifetime of the new object has started, can be used to
    manipulate the new object, if:

    [...]
    — the type of the original object is not const-qualified, and, if
      a class type, does not contain any non-static data member whose
      type is const-qualified or a reference type, and
    [...]

In our case the cited condition is not satisfied, because A has a non-static data member of a reference type — ref.

I presume that the intention behind 3.8/7 was to allow optimizations described below:

    #include <iostream>

    struct X
    {
        int &ref;
    };

    void f(X &);

    int main()
    {
        int n = 0;
        X x{n};
        f(x);
        x.ref = 5;
        std::cout << n << std::endl;
    }

Here a compiler is allowed to assume that

    x.ref = 5;

is equivalent to

    n = 5;

and therefore

    std::cout << n << std::endl;

is equivalent to

    std::cout << 5 << std::endl;

regardless of the definition of f (which may be unknown for compiler). There is no legal way to modify reference x.ref after its initialization so that it would refer to a different location. Even if we overwrite the storage of x by construction of a new object of type X at address &x (our mysterious f could do such thing), a compiler may assume that reference x.ref is untouched.

The same applies to the original example with optional: it looks like a compiler is free to assume that opt->ref or opt2.storage_.value_.ref still refers to n1 (as if the accessed ref would be member of the old object) rather than n2 (to which new ref is supposed to refer). Such a behavior may be unexpected for some programmers.

There are several ways to handle the issue. It's possible to:

1) reflect the limitations of the suggested implementation in the specification of std::optional;

2) find a reliable portable (and potentially less effective) implementation without limitations regarding to members of reference/const-qualified types;

3) acknowledge that an effective implementation of std::optional should rely on some compiler-specific behavior in order to avoid troubles with members of reference/const-qualified types;

4) make two templates: std::optional (which can use std::aligned_storage) with normal support of assignment but without support of constexpr semantics, and std::literal_optional (which can use unions in order to implement constexpr semantics);

5) introduce special rules for union members in order to make such tricks with unions well-defined;

6) reconsider the existing core rules in 3.8/7 more widely (not only with regard to unions).

There may be other options. Which direction is the most preferable?

[DeadMG]

Even if we overwrite the storage of x by construction of a new object of type X at address &x (our mysterious f could do such thing), a compiler may assume that reference x.ref is untouched.

If the Standard indeed says this, then that's hideously broken. A trivial example not involving optional would be, say, the last element of a std::vector. It's quite legal and normal for the user to overwrite reference locations by destructing the original object and reconstructing a new one in it's place. There's no way this optimization can present under as-if or present sane results in many conditions. 

[Nikolay Ivchenkov]

On Friday, May 31, 2013 5:42:45 PM UTC+4, DeadMG wrote:

A trivial example not involving optional would be, say, the last element of a std::vector. It's quite legal and normal for the user to overwrite reference locations by destructing the original object and reconstructing a new one in it's place.

We can do that:

    #include <iostream>
    #include <new>
    #include <vector>

    struct A
    {

        A(int &x) : ref(x) {}
        int &ref;
    };

    int main()
    {

        std::vector<A> v;

        int n1 = 0, n2 = 0;

        v.emplace_back(n1);
        A *p = &v.back();

        p->~A();
        A *q = new(p) A(n2);

        q->ref = 1; // q->ref shall refer to n2
        p->ref = 2; // p->ref may refer to n1

[Ville Voutilainen]

I suppose the vector internally has a pointer to the beginning of its buffer, which is practically
a pointer to the first element, but since we reallocated a new element in its place, the internal

pointer in the vector may or may not refer to the first element?

[Nikolay Ivchenkov]

On Friday, May 31, 2013 7:47:22 PM UTC+4, Ville Voutilainen wrote:

I suppose the vector internally has a pointer to the beginning of its buffer, which is practically

a pointer to the first element, but since we reallocated a new element in its place, the internal

pointer in the vector may or may not refer to the first element?

I presume that implementation may use a pointer to void in order to safely hold the address of the beginning of the allocated storage. Pointers to void do not point to any objects and such aggressive optimizations should not be applied to them.

BTW, issue 1280 describes similar case - see
http://www.open-std.org/jtc1/sc22/wg21/prot/14882fdis/cwg_closed.html#1280
(with message 19275)

Unfortunately, issue 1280 was closed without any informative comments. Few comments on 1280 can be found in

http://wiki.edg.com/twiki/bin/view/Wg21bloomington/CoreWorkingGroup

[Andrzej Krzemieński]

There are several ways to handle the issue. It's possible to:

1) reflect the limitations of the suggested implementation in the specification of std::optional;

2) find a reliable portable (and potentially less effective) implementation without limitations regarding to members of reference/const-qualified types;

3) acknowledge that an effective implementation of std::optional should rely on some compiler-specific behavior in order to avoid troubles with members of reference/const-qualified types;

4) make two templates: std::optional (which can use std::aligned_storage) with normal support of assignment but without support of constexpr semantics, and std::literal_optional (which can use unions in order to implement constexpr semantics);

5) introduce special rules for union members in order to make such tricks with unions well-defined;

6) reconsider the existing core rules in 3.8/7 more widely (not only with regard to unions).

There may be other options. Which direction is the most preferable?

The safest bet, I guess, will be to drop the requirement that std::optional be a literal type.

Someone in this list (I cannot find the post anymore) also suggested changing the rules for core constant expressions so that std::aligned_storage is allowed in the implementation of literal std::optional. Namely: using reinterpret_cast in core constant expressions. Although I didn't give it enough thought to be confident it would fix the problem.

Regards,
&rzej

[Ville Voutilainen]

On 3 June 2013 09:54, Andrzej Krzemieński <akrz...@gmail.com> wrote:

Someone in this list (I cannot find the post anymore) also suggested changing the rules for core constant expressions so that std::aligned_storage is allowed in the implementation of literal std::optional. Namely: using reinterpret_cast in core constant expressions. Although I didn't give it enough thought to be confident it would fix the problem.

Off the top of my head, we could also entertain the idea of having a compiler support library function that

is constexpr and converts aligned_storage to pointers of other type. Even if that's a rather specific

"patch", I do think we want to avoid the can of worms that will open if reinterpret_cast is allowed
in constant expressions.

Anyway, these things probably won't fix the issue with destroying+placement-constructing.

[Andrzej Krzemieński]

Hi,
I remember that at some point someone mentioned that std::optional (with its constexpr requirements) is not implementable in C++14. Is a defect report for that reported in C++ Standard Core Language Active Issues? (I couldn't find one)

Regards,
&rzej

[Ville Voutilainen]

I have filed an NB comment, FI 15, which covers that list of possible solutions.
http://open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3733.pdf, page 12.

[Marshall Clow]

On Sep 11, 2013, at 9:35 AM, Marshall Clow <mclow...@gmail.com> wrote:

> On Sep 11, 2013, at 7:05 AM, Andrzej Krzemieński <akrz...@gmail.com> wrote:
>
>> Hi,
>> I remember that at some point someone mentioned that std::optional (with its constexpr requirements) is not implementable in C++14. Is a defect report for that reported in C++ Standard Core Language Active Issues? (I couldn't find one)
>

> Hrm; I thought I reported one - but I don't see it either. Apparently I forgot :-(
> My paper (n3749) describes the problem, and suggests a fix.
>
> An example of code that fails:
>
> std::optional<int> o1{1};
> static_assert ( o1 < 2, "1 < 2" );

D'oh!

constexpr std::optional<int> o1{1};
static_assert ( o1 < 2, "1 < 2" );


-- Marshall

Marshall Clow Idio Software <mailto:mclow...@gmail.com>

A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
-- Yu Suzuki

[Marshall Clow]

On Sep 11, 2013, at 7:05 AM, Andrzej Krzemieński <akrz...@gmail.com> wrote:

> Hi,
> I remember that at some point someone mentioned that std::optional (with its constexpr requirements) is not implementable in C++14. Is a defect report for that reported in C++ Standard Core Language Active Issues? (I couldn't find one)

Hrm; I thought I reported one - but I don't see it either. Apparently I forgot :-(
My paper (n3749) describes the problem, and suggests a fix.

An example of code that fails:

std::optional<int> o1{1};
static_assert ( o1 < 2, "1 < 2" );