reinterpret_cast question

[Daniel]

Is it safe to do this?


template <class T>
class A<T>
{
public:
typedef std::pair<const std::string, T> value_type;

A(const std::string& key, const T& value)
: data_(key,value)
{
}

value_type& data()
{
return reinterpret_cast<value_type&>(data_);
}

private:
std::pair<std::string, T> data_;
};

int main()
{
A<std::string> a("key","value");
A<std::string>::value_type& data = a.data();
}

Thanks,
Daniel

[Daniel]

Is it safe to do this?

template <class T>
class A

[Öö Tiib]

There are some implicit conversions between pairs that differ by
constness of elements. Those convenience implicit conversions can
actually be invisible and non-obvious source of inefficiency when
dealing with 'std::map' for example.

However what you do is outright wrong I believe. The classes
'std::pair<std::string const, std::string>' and 'std::pair<std::string,
std::string>' are still different classes and 'reinterpret_cast' between
references to such different classes is not guaranteed to work.

[Daniel]

On Sunday, August 7, 2016 at 9:16:36 PM UTC-4, Öö Tiib wrote:
>
> what you do is outright wrong I believe. The classes
> 'std::pair<std::string const, std::string>' and 'std::pair<std::string,
> std::string>' are still different classes and 'reinterpret_cast' between
> references to such different classes is not guaranteed to work.

Thanks,
Daniel

[Alf P. Steinbach]

The classes have the same layout and the cast just adds `const`-ness. So
in practice it's technically safe.

Weasel word "technically": at the design level it's unsafe. For
presumably the reason why `data_` doesn't have first item `const` (which
forces the cast), is that you want class `A` to be copy assignable. And
then the value of the apparent `const` first item that client code has
just got a reference to, can change underneath.

You'd probably get some really perplexed client code that way.

• • •

Nothing is said about the design level, the *why*s of this code.

E.g. are you returning a reference as an optimization, or in order to
let client code modify the second item of the pair?

How reasonable alternatives are depend on the larger view of what this
is used for, I believe.

• • •

Anyway, remember the old adage: first make the code correct, and only
then make it fast.


Cheers & hth.,

- Alf

[Mr Flibble]

On 08/08/2016 09:53, Alf P. Steinbach wrote:
> On 08.08.2016 00:10, Daniel wrote:
>> Is it safe to do this?
>>
>> template <class T>
>> class A
>> {
>> public:
>> typedef std::pair<const std::string, T> value_type;
>>
>> A(const std::string& key, const T& value)
>> : data_(key,value)
>> {
>> }
>>
>> value_type& data()
>> {
>> return reinterpret_cast<value_type&>(data_);
>> }
>>
>> private:
>> std::pair<std::string, T> data_;
>> };
>>
>> int main()
>> {
>> A<std::string> a("key","value");
>> A<std::string>::value_type& data = a.data();
>> }
>
> The classes have the same layout and the cast just adds `const`-ness. So
> in practice it's technically safe.

Technically undefined behaviour is unsafe.

/Flibble

[Daniel]

On Monday, August 8, 2016 at 4:53:28 AM UTC-4, Alf P. Steinbach wrote:
>
> Weasel word "technically": at the design level it's unsafe. For
> presumably the reason why `data_` doesn't have first item `const` (which
> forces the cast), is that you want class `A` to be copy assignable. And
> then the value of the apparent `const` first item that client code has
> just got a reference to, can change underneath.

I think we can safely dismiss that concern. If you really believed that, you'd
have to call the associative containers - map, multimap, etc. - unsafe, as
they have std::pair<const Key,Value> value_type, and are copy assignable. In
my example, 'A' could easily be made copy assignable with std::pair<const
std::string, T> by the simple expedient of introducing a pointer, but that's
not the concern here.

> Nothing is said about the design level, the *why*s of this code.
>
> E.g. are you returning a reference as an optimization, or in order to
> let client code modify the second item of the pair?

The context is associative containers where the key/value pairs are stored in
sequence containers, and it is necessary to keep then sorted by the first
item, and where it is necessary to have compatibility with C++ concepts for
associative containers.

>
> How reasonable alternatives are depend on the larger view of what this
> is used for, I believe.
>

After the original post, I thought about looking at the Google b-tree
implementation that supports the STL associative container interface, as it
has the same requirement.

What Google does is define value_type and mutable_value_type

typedef std::pair<const Key, data_type> value_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef std::pair<Key, data_type> mutable_value_type;

define leaf field values as an array of mutable_value_type

mutable_value_type values[kNodeValues];

and use reinterpret_cast to return as a reference or const_reference,

reference value(int i) {
return reinterpret_cast<reference>(fields_.values[i]);
}
const_reference value(int i) const {
return reinterpret_cast<const_reference>(fields_.values[i]);
}

So I guess Google is okay with this.

Daniel

[Daniel]

On Monday, August 8, 2016 at 4:53:28 AM UTC-4, Alf P. Steinbach wrote:

> On 08.08.2016 00:10, Daniel wrote:

> > std::pair<const std::string, T>;

> > std::pair<std::string, T>

> The classes have the same layout and the cast just adds `const`-ness.

Are we sure they have the same layout, though? I found a discussion about that
here.

http://stackoverflow.com/questions/14272141/is-casting-stdpairt1-t2-const-to-stdpairt1-const-t2-const-safe

Daniel

[Mr Flibble]

Who cares? Formally it is undefined behaviour so you shouldn't do it all.

/Flibble

[Daniel]

On Monday, August 8, 2016 at 3:38:55 PM UTC-4, Mr Flibble wrote:
>
> Formally it is undefined behaviour so you shouldn't do it all.
>

Sausages also have undefined behaviour.

Daniel

[Mr Flibble]

Well that was certainly a fucking bizarre thing to say.

/Flibble

[Chris M. Thomasson]

lol. :^)

[Alf P. Steinbach]

No.

But this isn't super-obvious.

C++11 outlines most of the valid portable reinterpretations via
§3.10/10, the paragraph that the g++ folks call the "strict aliasing
rule" because it restricts how one can portably alias an object as
having different types (i.e., reinterpretation).

The view that this is a *formal* rule with an *exhaustive* listing of
possibilities, is shot down by the 6th dash, explaining that one can
reinterpret something as

• §3.10/10-6 “an aggregate or union type that includes one of the
aforementioned types among its elements or non-static data members
(including, recursively, an element or non-static data member of a
subaggregate or contained union),”

First, regarding whether the list is exhaustive, this dash permits only
one-way reinterpretation from type A to aggregate or union type B, while
§9.2/20 supports two-way reinterpretation for the special case where A
is first member of POD class type B,

• §9.2/20 “A pointer to a standard-layout struct object, suitably
converted using a reinterpret_cast, points to its initial member (or if
that member is a bit-field, then to the unit in which it resides) and
vice versa”

So, it's not exhaustive.

Secondly, the vague language about *any* aggregate or union that just
includes, somewhere, an element with compatible type, is decidedly not
formal. One has to bring practical sound judgement to the table in order
to not conclude that reinterpreting a `double` as a `struct { int a;
double b; };` is valid. For that's what the 6th dash literally says as a
formal statement.

So, it's not formal either: it's just a vague, broad outline.

But it's what we have.

Then, using it, with the above caveats (not exhaustive, not formal) in
mind, the second dash says that an object can be reinterpreted as

• §3.10/10-6 “a cv-qualified version of the dynamic type of the object”

And this means that via §9.2/20 the non-`const` member `pair` can be
reinterpreted as a `string` (the first member), which via 3.10/10-6 in
turn can be reinterpreted as a `string const`, which via §9.2/20 or via
§3.10/10-6 can be reinterpreted as a `pair<string const, string>`.

Then, still at issue is the second item of the pair. But here 3.10/10-6
applies /directly/. So also this part is OK.

Of course it's much easier to just reason about whether the
reinterpretation makes sense :-), as I did earlier in the thread,
because that's the goal that the standard's rules are designed to allow.

> so you shouldn't do it all.

On the contrary, it can be argued that one should do this
reinterpretation as a matter of course, so as not to incur needless
copying and very inefficient dynamic allocations.

[Chris Vine]

§9.2/20 would only make §3.10/10 non-exhaustive if it permits
aliasing that §3.10/10 does not. I do not believe that is the case.

You give the example of a standard layout struct of type B having a
first member of type A, and make the point that the sixth bullet of
§3.10/10 allows one way conversion but §9.2/20 allows two way
conversion.

However, to cast from the B-type object to address its A-type member
object you are covered (so far as concerns §3.10/10) by the first
bullet, because both objects in fact exist. If the struct of type B is
fully constructed than _all_ its members, including the member of type
A, must also be fully constructed. If you cast a pointer to the B-type
object to a pointer of type A*, and then access the first member by
dereferencing that pointer of type A*, you are in fact accessing a
_real_ object (the first member) via a pointer to its own dynamic
type. Ditto if you make a cast in the opposite direction. There is no
type punning involved.

The sixth bullet point of §3.10/10 covers real type punning,
particularly (but obviously not exclusively) through unions, to pretend
that an object of one type is actually, for limited purposes, of another
type.

Chris

[Mr Flibble]

On 09/08/2016 06:45, Alf P. Steinbach wrote:
> On 08.08.2016 21:38, Mr Flibble wrote:
>> On 08/08/2016 20:27, Daniel wrote:
>>> On Monday, August 8, 2016 at 4:53:28 AM UTC-4, Alf P. Steinbach wrote:
>>>> On 08.08.2016 00:10, Daniel wrote:
>>>
>>>>> std::pair<const std::string, T>;
>>>>> std::pair<std::string, T>
>>>
>>>> The classes have the same layout and the cast just adds `const`-ness.
>>>
>>> Are we sure they have the same layout, though? I found a discussion
>>> about that
>>> here.
>>>
>>> http://stackoverflow.com/questions/14272141/is-casting-stdpairt1-t2-const-to-stdpairt1-const-t2-const-safe
>>>
>>>
>>
>> Who cares? Formally it is undefined behaviour
>
> No.
>
> But this isn't super-obvious.

Wrong.

std::pair<const std::string, T> and std::pair<std::string, T> are two
UNRELATED non-POD types. One type is NOT a cv-qualified version of the
other. What you are trying to do is undefined behaviour: don't do it.

[snip]

/Flibble

[Alf P. Steinbach]

On 09.08.2016 18:33, Mr Flibble wrote:
> On 09/08/2016 06:45, Alf P. Steinbach wrote:
>> On 08.08.2016 21:38, Mr Flibble wrote:
>>> On 08/08/2016 20:27, Daniel wrote:
>>>> On Monday, August 8, 2016 at 4:53:28 AM UTC-4, Alf P. Steinbach wrote:
>>>>> On 08.08.2016 00:10, Daniel wrote:
>>>>
>>>>>> std::pair<const std::string, T>;
>>>>>> std::pair<std::string, T>
>>>>
>>>>> The classes have the same layout and the cast just adds `const`-ness.
>>>>
>>>> Are we sure they have the same layout, though? I found a discussion
>>>> about that
>>>> here.
>>>>
>>>> http://stackoverflow.com/questions/14272141/is-casting-stdpairt1-t2-const-to-stdpairt1-const-t2-const-safe
>>>>
>>>>
>>>>
>>>
>>> Who cares? Formally it is undefined behaviour
>>
>> No.
>>
>> But this isn't super-obvious.
>
> Wrong.
>
> std::pair<const std::string, T> and std::pair<std::string, T> are two
> UNRELATED non-POD types.

No, the standard specifies the members, i.e. the layout.

That's all that was used in the derivation of correctness of the cast.

> One type is NOT a cv-qualified version of the
> other.

That's pretty irrelevant, considering the derivation that you snipped
did not rely on that fact.

>What you are trying to do is undefined behaviour:

No, it's not me, and second, as you have seen proved, but snipped, it's
not UB.


> don't do it.

Well, that's your original advice, and you can't back down from that,
can you?

Have you considered that standard library implementations necessarily do
this?

[Mr Flibble]

On 09/08/2016 18:39, Alf P. Steinbach wrote:
[snip]

>
> Have you considered that standard library implementations necessarily do
> this?

No I haven't because they don't.

/Flibble

[Daniel]

Do a global search for reinterpret_cast in, say, Microsoft Visual Studio 14.0\VC\include. You'll find them all over the place, e.g.

typedef typename const _Value_type value_type;

const _Value_type& operator() (const index<_Rank>& _Index) const __GPU
{
void * _Ptr = _Access(_Read_access, _Index);
return *reinterpret_cast<value_type*>(_Ptr);
}

[Mr Flibble]

That is something else entirely. I didn't say don't use
reinterpret_cast; I said this particular use of reinterpret_cast was
undefined behaviour.

/Flibble

[Chris Vine]

What "do this" are you addressing? reinterpret_casts are essential for
some uses, and the standard describes what aliasing is allowed when
using them. The issue you first raised however was that of casting a
non-const pair with non-const members to a non-const pair with a const
first member, which is a very interesting question. Your extract
from Microsoft's code does not help a great deal with that: there are
numerous reasons why a reinterpret_cast may have been preferred by the
library writer to a static_cast here, and we do not know if it covers
your use case. And in writing their standard library, Microsoft can do
anything that their compiler will accept, irrespective of whether the
code in question complies with the standard or not.

Alf's reasoning was imperfect for the reasons I have mentioned but I
think his conclusion would still be right if std::pair is an aggregate,
for the reasons he has given. However, std::pair has a user defined
constructor so it is not an aggregate. Will you get away with it?
Probably; my intuition is that you will since it seems so innocuous.
It seems pathetic to reject the code simply because std::pair is not
an aggregate, and it is difficult to believe a compiler would do so. Is
it standard conforming? Dunno, but I suspect not.

Chris

[Daniel]

On Tuesday, August 9, 2016 at 3:41:11 PM UTC-4, Chris Vine wrote:
>
> Alf's reasoning was imperfect for the reasons I have mentioned but I
> think his conclusion would still be right if std::pair is an aggregate,
> for the reasons he has given. However, std::pair has a user defined
> constructor so it is not an aggregate. Will you get away with it?
> Probably; my intuition is that you will since it seems so innocuous.
> It seems pathetic to reject the code simply because std::pair is not
> an aggregate, and it is difficult to believe a compiler would do so. Is
> it standard conforming? Dunno, but I suspect not.
>

Thanks, appreciate your thoughtful remarks.

It seems to me that the more pessimistic conclusion is most likely to be
correct.

I do wish the standard associative containers hadn't dictated that value_type
must be std::pair<const key, mapped_type>, it was unnecessary to do that,
they could have allowed any type that supported key and value accessors and
value modifier. As a result it looks like a broad class of associative
container implementations cannot be made compatible with standard library
associative container iterators, such as the Google C++ btree (which
attempts to do so with the cast), stx-btree (which, requiring copying, can't
support modifying values through iterators), and (my immediate interest)
sorted arrays of pairs.

Best regards,
Daniel

[Mr Flibble]

On 09/08/2016 23:16, Daniel wrote:
> On Tuesday, August 9, 2016 at 3:41:11 PM UTC-4, Chris Vine wrote:
>>
>> Alf's reasoning was imperfect for the reasons I have mentioned but I
>> think his conclusion would still be right if std::pair is an aggregate,
>> for the reasons he has given. However, std::pair has a user defined
>> constructor so it is not an aggregate. Will you get away with it?
>> Probably; my intuition is that you will since it seems so innocuous.
>> It seems pathetic to reject the code simply because std::pair is not
>> an aggregate, and it is difficult to believe a compiler would do so. Is
>> it standard conforming? Dunno, but I suspect not.
>>
> Thanks, appreciate your thoughtful remarks.
>
> It seems to me that the more pessimistic conclusion is most likely to be
> correct.
>
> I do wish the standard associative containers hadn't dictated that value_type
> must be std::pair<const key, mapped_type>, it was unnecessary to do that,

It was necessary to do that to ensure that a key cannot be changed once
added to the binary search tree.

/Flibble

[Daniel]

No. That's an interface issue, not an implementation issue.

There is no problem if value_type is defined as a type having a key() accessor
that is non-modifying.

That's assuming it's the user of the class that you're worried about, who
might change the key. If it's a perverse class implementer you're worried
about, well, he could always remove a tree node and replace it with a new one
with a different key, const key or not.

Anyway, this is, while regrettable, unable to be changed.

Best regards,
Daniel

[Mr Flibble]

On 10/08/2016 00:02, Daniel wrote:
> On Tuesday, August 9, 2016 at 6:26:48 PM UTC-4, Mr Flibble wrote:
>> On 09/08/2016 23:16, Daniel wrote:
>>>
>>> I do wish the standard associative containers hadn't dictated that value_type
>>> must be std::pair<const key, mapped_type>, it was unnecessary to do that,
>>
>> It was necessary to do that to ensure that a key cannot be changed once
>> added to the binary search tree.
>>
> No. That's an interface issue, not an implementation issue.

It is both.

>
> There is no problem if value_type is defined as a type having a key() accessor
> that is non-modifying.

You cannot allow the key to be changed by allowing access to it hence it
must be const.

>
> That's assuming it's the user of the class that you're worried about, who
> might change the key. If it's a perverse class implementer you're worried
> about, well, he could always remove a tree node and replace it with a new one
> with a different key, const key or not.

You don't get it: if a key in a binary search tree is changed the tree
can become corrupt and invalid.

>
> Anyway, this is, while regrettable, unable to be changed.

It isn't regrettable as it is the correct design.

/Flibble

[Daniel]

On Tuesday, August 9, 2016 at 7:23:42 PM UTC-4, Mr Flibble wrote:

>
> if a key in a binary search tree is changed the tree
> can become corrupt and invalid.
>

Obviously. Nobody has suggested otherwise. In fact, that's true of
associative containers generally.

> >
> It isn't regrettable as it is the correct design.
>

What you're saying is that the standard requirement for associate containers, that they _must_ store key value pairs in std::pair<const Key,mapped_typed> value types, and allow no other internal physical representation, is the correct design. That doesn't work for btrees, where value types have to be shuffled between blocks when re-balancing, and it doesn't work for b+ trees, where keys and values are stored separately, and it doesn't work for sequences of key value pairs.

All of these associative data structures have the logical requirement that the
key doesn't change, but a whole class of them can't use std::pair<const
Key,mapped_typed> for physical storage. The interface for associative
containers shouldn't dictate that they must. The fact that it does is
regrettable, because a whole class of associative containers that have
desirable characteristics can't participate in generic algorithms.

And it was unnecessary.

Best regards,
Daniel

[Mr Flibble]

It was not unnecessary for map as it is the correct design for map.

/Flibble

[Daniel]

On Tuesday, August 9, 2016 at 8:13:24 PM UTC-4, Mr Flibble wrote:
>
> It was not unnecessary for map as it is the correct design for map.
>

I don't think so :-)

iterator and const_iterator are not required to be particular types, just types that have certain properties. Similarly, there was no reason to require that value_type be a particular type (std::pair<const key_type,mapped_type>), as with the iterator types, it would have been enough to specify that it have certain properties (an accessor for a key, an accessor and a modifier for a value.)

That would have allowed a larger class of map-like containers to be introduced and be used interchangeably, much as it is already possible to use a wide class of sequence containers interchangeably.

Best regards,
Daniel