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

[Nico Weber]

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


> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20140415/b9f72e1c/attachment.html>