[cfe-dev] [libc++] Implementation of std::map::erase() in libc++ doesn't match that in libstdc++

[Richard Smith]

On Tue, Apr 15, 2014 at 10:38 AM, Nico Weber <thakis at chromium.org> wrote:

> On Tue, Apr 15, 2014 at 7:50 AM, Marshall Clow <mclow.lists at gmail.com>wrote:
>
>>
>> On Apr 11, 2014, at 9:35 AM, Nico Weber <thakis at chromium.org> wrote:
>>
>> On Fri, Apr 11, 2014 at 1:29 AM, Marshall Clow <mclow.lists at gmail.com>wrote:
>>
>>> On Apr 8, 2014, at 1:47 PM, Alexander Potapenko <glider at google.com>
>>> wrote:
>>>
>>> > Hi all,
>>> >
>>> > We've encountered an incompatibility between libc++ and libstdc++: for
>>> > std::map::erase(pos) libstdc++ (and MSVS as well) first removes the
>>> > item from a map (a) and then calls its destructor (b), while libc++
>>> > calls the destructor before changing the map structure.
>>> >
>>> > This results in a crash described at
>>> > https://code.google.com/p/chromium/issues/detail?id=358707: the item
>>> > that's being erased from the map queries that map in the destructor
>>> > calls some methods for the elements it finds. With libc++ that item
>>> > manages to find itself (in an inconsistent state, since it's in the
>>> > destructor already) and crashes.
>>> >
>>> > Does the standard specify the order of (a) and (b), or it's incorrect
>>> > to rely on the order provided by some of the libraries?
>>>
>>> My belief is that the correct answer is (b).
>>>
>>> As far as I can tell, the standard makes no mention of this.
>>> [ map::erase has no special requirements, and the general container
>>> requirements don’t say anything. ]
>>>
>>> However, libc++’s behavior seems a bit odd to me, too.
>>> I committed revision 206024 to change this.
>>>
>>
>> Speaking of spec-compliant-but-odd things: libc++'s std::random_shuffle
>> walks the array backwards, while libstdc++ and msvs's implementation walk
>> forward. We used to have code that called random_shuffle with a fixed
>> generator and relied on that producing always the same shuffle, but
>> libc++'s shuffle was different than the one produced by other standard
>> libraries. Maybe you want to change this too.
>>
>>
>> That seems … wrong to me.
>>
>> The only guarantee you get from random_shuffle is that any output is as
>> likely to occur as any other output.
>>
>
> Sure, but in practice there really are only two ways one could write
> Fisher-Yates :-) (But keeping this the code as-is is certainly fine.)
>

The libc++ algorithm is Fisher-Yates; the libstdc++ algorithm is not.
Fisher-Yates incrementally builds a random sequence by repeatedly appending
a randomly-selected element from the unchosen set, and that's what libc++
does. The libstdc++ algorithm incrementally builds a random sequence by
repeatedly swapping the next element of the unchosen set into a random
position within the already-built random sequence (this is a time-reversal
of Fisher-Yates).

I suspect (but the standard doesn’t require, as far as I can tell), if you
>> give it the same inputs, and a RNG that spits out the same random sequence,
>> you should get the same output each time, but there’s nothing about a
>> “correct” result.
>>
>>
>> (Not required for spec compliance, but it'd make libc++ less surprising.
>> In Chromium, we've stopped using random_shuffle in this case since if we
>> need this property and the spec doesn't guarantee it, relying on it seems
>> like a pretty bad idea!
>>
>>
>> Exactly correct.
>>
>> But it might be nice for other projects.)
>>
>>
>> I’m less inclined to change this, since:
>> 1) There’s nothing in the standard that says anything about order of
>> operations.
>>  2) random_shuffle is deprecated in C++14.
>>
>> — Marshall
>>
>>
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20140415/6ddc1ea6/attachment.html>