[cfe-dev] libc++ std::map self-assignment bug

[Ahmed Charles]

----------------------------------------
> Date: Thu, 27 Feb 2014 21:36:50 -0800
> Subject: Re: [cfe-dev] libc++ std::map self-assignment bug
> From: james.dennett at gmail.com
> To: acharles at outlook.com
> CC: silvas at purdue.edu; howard.hinnant at gmail.com; cfe-dev at cs.uiuc.edu; mclow.lists at gmail.com
>
> On Thu, Feb 27, 2014 at 9:09 PM, Ahmed Charles <acharles at outlook.com> wrote:
>> ----------------------------------------
>>> Date: Thu, 27 Feb 2014 00:09:51 -0800
>>> Subject: Re: [cfe-dev] libc++ std::map self-assignment bug
>>> From: james.dennett at gmail.com
>>> To: acharles at outlook.com
>>> CC: silvas at purdue.edu; howard.hinnant at gmail.com; cfe-dev at cs.uiuc.edu
>>>
>>> On Wed, Feb 26, 2014 at 11:43 PM, Ahmed Charles <acharles at outlook.com> wrote:
>>>> I just got around to reading my backlog of cfe-dev mail and noticed this. So, forgive me for replying but obscure is awesome.
>>>>
>>>> I think the following paragraph makes the standard require rebalancing, (which suggests that the container requirements are wrong, since rebalancing isn't linear time.
>>>>
>>>> 23.2.4 [associative.reqmts]/p11
>>>>
>>>> When an associative container is constructed by passing a comparison object the container shall not store a pointer or reference to the passed object, even if that object is passed by reference. When an associative container is copied, either through a copy constructor or an assignment operator, the target container shall then use the comparison object from the container being copied, as if that comparison object had been passed to the target container in its constructor.
>>>>
>>>> This suggests that your implementation below isn't conforming, since assigning the comparison object below doesn't behave the same way as passing it to the target container's constructor. But, this would be conforming:
>>>>
>>>> template <class T>
>>>> class my_compare
>>>> {
>>>> bool reversed_ = false;
>>>> public:
>>>> my_compare() = default;
>>>> my_compare(bool r) : reversed_(r) {}
>>>> my_compare(const my_compare& o) : reversed_(!o.reversed_) {}
>>>> my_compare& operator=(const my_compare& o) {
>>>> reversed_ = !o.reversed_;
>>>> return *this;
>>>> }
>>>> bool operator()(const T& x, const T& y) const
>>>> {
>>>> if (reversed_)
>>>> return y < x;
>>>> return x < y;
>>>> }
>>>> };
>>>>
>>>> Note, the important thing is that both copy operations do the same thing, consistently.
>>>
>>> But what they do is not copying; they violate the CopyConstructible
>>> requirement that the associative containers' constructors place on
>>> their Compare type (when a comparator is passed, at least... there may
>>> be a gap in the wording, where the standard should say that copying an
>>> associative container requires that its comparator be
>>> CopyConstructible).
>>
>> I tried to find the place in the standard the describes the requirements on the comparison type, but I wasn't able to. Granted, I didn't spend too much time on this. If you can point to the section, that would be great.
>
> The table of associative container requirements has some rows
> describing various required constructors, and those require that the
> comparator be CopyConstructible if one is passed in.
>
> (The small defect that I think is present is that the copy operations
> of the associative container itself don't appear to have this
> requirement.)
>
>> It's also not obvious that CopyConstructible is related to EqualityComparable either.
>
> Indeed, it's not so closely related. CopyConstructible doesn't imply
> EqualityComparable; a copy is not required to compare equal to the
> original, it's required to be "equivalent" to it, in some ill-defined
> sense.
>
>> I've never seen a place in the standard that says that copying needs to maintain the same value, though it does allow elision to occur, which means that your program can't usefully rely on the side effects of the copy actually having happened.
>
> The CopyConstructible requirements are where you want to look, I
> think. (Table 21 in my draft of C++14.) I quoted them in my original
> message (still quoted below), though maybe not very explicitly so:
>
>>> Note that CopyConstructible is not a merely syntactic requirement: it
>>> implied that for after copying a value v, "the value of v is unchanged
>>> and is equivalent to [the copy]".
>
> Hope this helps,


Thanks, I just read the sections you mention and I agree with the conclusion. Equivalence is probably not explicitly defined but it's not ambiguous what it means, especially in the context of a comparison type.

So, the extension would seem to be non-conformant if it doesn't exhibit linear complexity when the requirements are met. Marshall, would you be able to look into this or should I or perhaps someone else?

The standard doesn't have a defect since the copy operations are defined in terms of the constructor which takes a comparison object, which requires CopyConstructible. That is here, which I quoted before: 23.2.4 [associative.reqmts]/p11

When an associative container is constructed by passing a comparison 
object the container shall not store a pointer or reference to the 
passed object, even if that object is passed by reference. When an 
associative container is copied, either through a copy constructor or an
 assignment operator, the target container shall then use the comparison
 object from the container being copied, as if that comparison object 
had been passed to the target container in its constructor.